CS251- Winter 2000- Assignment 1

First assignment--CS251--Winter 2000

These are exercises on recurrences and the big Oh notation.

Question 1	Linear congruential sequences. Random-looking sequences of integers are often generated as follows: let M be a big integer; given are x(1), a and b, integers taking values between 0 and M-1 inclusive. A sequence is defined by the recursion x(n+1) = (ax(n) + b) mod (M). Here the mod(.) operation gives the remainder after division by M. The sequence x(1), x(2), x(3), ... is called a linear congruential sequence. For some choices of a, b and x(1), it may appear "random" to the untrained observer. Almost all built-in random number generators use it. Assume we have a RAM-model computer with uniform time cost for the standard operations on integers: comparison, multiplication, integer division, addition, subtraction, mod(.). Show how you can compute x(n) in time O(log n).
Question 2	Symbolic multiplication of polynomials. Assume that a polynomial a(0) + a(1) x^1 + ... + a(n) x^n is stored symbolically by placing (a(0), a(1), ..., a(n)) in an array, where the a(i)'s are real numbers. let (b(0), b(1), ..., b(n)) represent another polynomial. In a RAM model with uniformly bounded computation times, how would you multiply these polynomials and compute the resulting polynomial represented by (c(0), c(1), ..., c(2n))? What is the complexity of your algorithm as a function of n?
Question 3	Linear time selection. Consider a computational model in which one comparison takes one time unit. Let T(n) be the worst-case time of the median-of-3 algorithm for finding the k-th smallest of n elements. Deduce a recurrence for T(n). Draw the recursion tree. Use it to derive a "Theta" expression for T(n).
Question 4	Recursions. Draw a square on a piece of paper. Now, divide the square by a vertical line into two rectangles. Cut each rectangle separately by a horizontal line segment into two rectangles (note: there is one segment per rectangle). By alternating vertical and horizontal cuts, you will end up with 2^k rectangles after k rounds of cutting. Next, draw an infinite horizontal line that meets the square, but does not contain any of the horizontal segments you have drawn thus far. Let T(k) be the number of rectangles visited by this horizontal line. By using the master theorem, determine the order of growth of T(k) with respect to k in "Theta" notation.
Question 5	Algorithm design. Given are two sorted arrays A and B, each containing n integer-valued elements. Give an algorithm to find the median (n-th smallest) of the 2n elements in union (A,B). Your algorithm should require no more than O(log n) comparisons. Show why you can achieve O(log n) time.