University of Nevada Las Vegas
Howard R. Hughes
College of Engineering
Department of Computer Science
My Home Page
Computer Science 477/677
Analysis of Algorithms
Fall 2013
Assignments
Revised December 17, 2013
-
Background.
It is important to have a good background in algorithms and data
structures at the level of CSC 302.
There is background material in your textbook.
Wednesday September 4, 2013.
Turn in Assignment 1 at the beginning of class today.
Wednesday September 11, 2013.
Turn in Assignment 2 at the beginning of class today.
The lecture topic today will be sorting. A major part of the examination
on Monday will be on that subject.
-
Lower Bound on Sorting in the Comparison Model of Computation.
-
Sorting algorithms we will go over:
-
Selection sort.
-
Insertion sort.
-
Bubblesort.
-
Mergesort.
-
Quicksort.
-
Polyphase mergesort.
-
Binary tree sort, which is actually a fast implentation of insertion sort.
-
Heapsort, which actually a fast implementation of selection sort.
-
Shell sort, named after Donald Shell. Very ancient.
Hardly anyone understands it.
Donald Shell probably didn't, since he implemented it in the worst of
all possible ways.
-
Radix or bucket sort, the only sorting algorithm in this list which does not
use the comparison model of computation.
-
When I (personally) need to write a sorting algorithm in a program, I usually
pick one of my four favorites. Which do you think they are?
Monday September 16, 2013.
Examination today.
Practice examination in postscript format.
Practice examination in portable document format.
Highest score: 180
75 percentile score: 155
Median score: 135
25 percentile score: 120
Mean score: 138
Wednesday September 25, 2013.
Turn in Assignment 3 at the beginning of class today.
Wednesday October 2, 2013.
Turn in Assignment 4 at the beginning of class today.
Wednesday October 9, 2013.
Turn in Assignment 5 at the beginning of class today.
Additional examples
added to help you check your work.
Solution to the monotone subsequence problem
Monday October 14, 2013.
Examination today.
Some problems
Highest score: 215
75 percentile score: 165
Median score: 130
25 percentile score: 110
Mean score: 139
Wednesday October 16, 2013.
The examination is not yet graded. I came to the realization that
my first linear time solution to problem 7. (maximum weight independent
subsequence) is incorrect. At least one of the students gave a
correct, but quadratic time, solution.
I changed my solution so that is both correct and linear time.
Fortunately, that solution, together with my
solution to the second problem of Assignment 5,
lead directly to the next topic, namely
range queries.
Wednesday October 23, 2013.
Turn in Assignment 6 at the beginning of class today.
Assignment 6 is canceled.
Wednesday October 30, 2013.
Turn in Assignment 7 at the beginning of class today.
The handout has been updated.
Postscript format.
Let there be no confusion: pages 4 and 5
of the handout are not part of Assignment 7.
Monday November 4, 2013.
Memoization, a top-down form of dynamic programming.
Wednesday November 6, 2013.
Turn in Assignment 8 at the beginning of class today.
The stable marriage problem.
An application: assigning interns to hospitals.
(I first heard of an algorithm to solve the intern/hospital
assignment problem in 1952 or 1953, from
Peter Franken.
When I asked Peter how it was done, he only told me that the computer first
matched first choices. I then forgot about the problem for the next
thirty years.)
The stable roommate problem is unsolvable.
Graham Scan. We use amortized analysis to prove that it takes O(n log n) time.
Divide and Conquer algorithm for finding the
closest pair out of a finite
set of points in the plane.
The Traveler's problem.
Wednesday November 13, 2013.
Examination today.
Practice examination in postscript format.
Updated Tue Nov 12 14:43:30 PST 2013
Practice examination in portable document format.
There will also be a problem in dynamic programming.
Answer to Question 7
Highest score: 235
75 percentile score: 190
Median score: 150
25 percentile score: 115
Mean score: 149
Wednesday, November 20, 2013.
Using neighbor lists to topologically sort an acyclic directed graph
in O(m) time.
Closest pair of points in a plane.
Balanced search structures.
-
Treap:
a randomized search structure, which is balanced in the
Las Vegas sense.
What is the meaning of the phrase "Las Vegas time complexity"?
What is the difference between a Las Vegas algorithm and a
Monte Carlo algorithm?
-
Red black tree, which is deterministically balanced.
-
2-3 tree, which is deterministically balanced.
Monday, November 25, 2013.
Semigroups.
-
Range queries.
-
Applications in minimum path finding.
-
Application to
adding two n-digit numerals in O(log n) time with n/log n processors.
Multi-core Computing.
-
Minding a maximum, minimum, or sum of n values in O(log n) time
with n processors. Can you do it with fewer processors?
-
Adding two n-digit numerals in O(log n) time with n/log n processors.
-
Can the
Boolean circuit problem
be solved efficiently with a multi-core computer?
Wednesday, November 27, 2013.
Turn in Assignment 9 at the beginning of class today.
Wednesday, December 5, 2013.
-
The way to solve the recurrence is to make the substitution
F(n) = n G(n).
Thus, G(√ n ) =
√ n
F(√ n ).
Starting with the original recurrence, making the substitution, and then
dividing both sides by n, we obtain:
-
F(n) =
√ n
F(√ n )+n
-
n G(n) =
√ n
√ n
G(√ n )+n
-
n G(n) = n
G(√ n )+n
-
G(n) = G(√ n )+1
Solving this recurrence and then substituting back, we obtain:
-
G(n) = Θ(log log n)
-
n G(n) = Θ(n log log n)
-
F(n) = Θ(n log log n)
The sorting, median finding, and coin weighing problems can by anayzed using
information theory.
How many comparisons does it take to:
-
Sort 5 items?
Ans: 7
-
Find the median of 5 items?
Ans: 6
What about 7 items?
-
Since 7! = 5040, it must take at least 13 comparisons to sort 7 items.
Is that enough? Ans: Yes. It's actually quite easy,
given that you can sort 5 items in 7 comparisons.
-
There are 7 possible medians, and a certificate consists of three items
smaller than the median and three larger. Thus, the number of certificates
for each choice of median is 6 choose 3, which is 20. Thus,
any comparison model algorithm for finding the median must have at least
log2140 comparisons in the worst case. Since that must be
an integer, you need at least 8 comparisons. Is that enough?
-
After just one comparison, the number of remaining possibilities is 90,
which does not exceed 27. So far, so good, but you're
far from done.
Balance puzzles involve weighing items on a balance scale,
where you can weigh two sets of items,
and the scale will tip to the left, or to the right, or will be balanced.
-
One classic problem is that there are N coins, one of which is
counterfeit. All the genuine coins weight the same, but the counterfeit
coin has a slightly different weight. The problems is to locate the
counterfeit coin, and to determine whether it is too heavy
or too light, in K weighings with the balance scale,
The problem is impossible if the number of possible situations answers,
which is 2N, exceeds 3K.
-
Peter gave
me this problem for N=12 and K=3
while he was living with us during the year 1952-53.
There are 24 possible situations, which does not exceed 33.
It took me about three days, and I was very proud of myself for finding
the solution. (However, Peter had given me a big hint.)
-
In 1958, the textbood used for the Freshman math course
at Tulane University had the problem
for N=13, k=3. Note that 26 < 33, so it looks possible.
-
But it isn't possible, because in the first weighing, you have to put an
equal number of coins on each side. If that number is 4 or less, and the
scale balances, the number of answers remaining is at least 10, which
is greater than 32, and you can't finish. On the other hand,
if you put 5 or more on each side, and the scale does not balance, the
number of answers remaining is again at least 10, and you can't finish.
-
Strangely, the mathematics faculty and students never thought of
using
information-theory-analysis.
They eventually figured out that it was impossible anyway.
-
You can get a solution if you assume there is a 14th coin which
we know is not counterfeit. In this case, there are still 26 possible
answers, but the extra coin allows you to get a solution.
Can you do it? You will find a solution much faster if you
use information theory to guide you.
Wednesday, December 11, 2013.
Final Examination.
The final examination is scheduled for 3:10 - 5:10 PM.
The examination will be comprehensive.
Practice final
in
postscript form
Practice final in
pdf form
Topics to study in preparation for the final exam.
There may be questions on some of these topics that are not represented
on the practice final.
Tuesday, December 17, 2013.
I have submitted the grades, finally.
Back to
Course Page