Due Friday April 7, 2000
My copy of the C++ book hasn't arrived yet, so for this first assignment I will enter the text of the book problems for those of you who don't have the C book.
1. Problem 2.4. See the book for the meaning of little-oh.
Prove that for any constant, k, logk N = o(N).
2. Problem 2.7, parts a,b,e. For part a, only prove that all permutations are legal, not that they are equally likely.
Suppose you need to generate a random permutation of the first N integers. For example, {4, 3, 1, 5, 2} and {3, 1, 4, 2, 5} are legal permutations, but {5, 4, 1, 2, 1} isnot, because one number (1) is dupliated and another (3) is missing. This routine is often used in simulation of algorithms. We assume the existence of a random number generator, RandInt(i,j), which generates integers between i and j with equal probability. Here are three algorithms:
a) Prove that all three algorithms generate only legal permutations and
that all permutations are equally likely.
b) Give as accurate (Big-Oh) an analysis as you can of the expected running time of each algorithm.
e) What is the worst-case running time of each algorithm?
3. Problem 2.19, parts a,b,c,d.
A majority element in an array, A, of size N is an element that appears more than N/2 times (thus, there is at most one). For example, the array
3, 3, 4, 2, 4, 4, 2, 4, 4
has a majority element (4), whereas the array
3, 3, 4, 2, 4, 4, 2, 4
does not. If there is no majority element, your program should indicate this. Here is a sketch of an algorithm to solve the problem:
First, a candidate majority element is found (this is the harder part). This candidate is the only element that could possibly be the majority element. The second step determines if this candidate is actually the majority. This is just a sequential search through the array. To find a candidate in the array, A, form a second array, B. Then compare A1 and A2. If they are equal, add one of these to B, otherwise do nothing. Then compare A3 and A4. Again, if they are equal, add one of these to B; otherwise do nothing. Continue in this fashion until the entire array is read. Then recursively find a candidate for B; this is the candidate for A (why?).
a) How does the recursion terminate?
b) How is the case where N is odd handled?
c) What is the running time of the algorithm?
d) How can we avoid using an extra array B?
4. Drawing a ruler (not in the book). Suppose you have a function draw_mark(double x_position, double mark_height) which will draw a vertical mark at the specified horizontal position on the screen. You want to use this function to draw a ruler with subdivisions, each subdivision being one unit smaller than the last. So, if the outer marks are height 10, the half mark would be height 9, the quarter marks height 8, and so on.
This picture shows a ruler that has been subdivided 4 times (once for the half, once for quarters, etc.). Your function should have the following signature.
void draw_ruler(double x_left, double x_right, double start_height, int
num_subdivisions);
The picture, if we say it extends from x=0.0 to x=100.0, with outer marks at
height 10.0, would have been drawn by a call to: draw_ruler(0.0, 100.0,
10.0, 4);
a) Give a recursive implementation.
b) Give an iterative implementation that draws the marks from left to right. Hint: first figure out how many marks need to be drawn. I suggest treating the two marks on the ends as special cases. For each mark, you need to figure out the correct height. Take a look at the binary representation of the mark number (0,1,2,3,...) and see if there's a pattern you can use.
5. (not graded) How many hours did this assignment take you? On a scale from 1 to 10, would you rate it too easy (1), just right (5), too hard (10)?