CS252- Winter 2003- Assignment 1

First assignment--CS252--Winter 2003

Date: January 16, 2003.
Due: January 23, 2003, 2:30pm.

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	Recursions. Consider a 19-ary tree with a number of levels of nodes, each of which has 19 children. The last level consists of nodes with no children. Let n be the total number of nodes in the tree. Color each node red except the youngest child in each set of 19 siblings, which is colored blue. Then color all nodes in each subtree of a blue node also blue. Express the number of red nodes in "Theta" notation as a function of n. Prove your claim.
Question 3	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.
Question 4	Algorithm design. Given are two linked lists with n elements in all. They are joined at a point, that is, list one consists of x_1,...,x_k,y_1,...,y_m, and list two of z_1,...,z_r, y_1,...,y_m, with the sizes k, r, m unknown (note that r+k+m=n). We are given two pointers to the heads of the lists, and storage for two more pointers. The lists cannot be cut, moved, changed or destroyed. We would like to locate the first joint element in the lists (in our notation, y_1) in time O(n). Please describe such an algorithm, and prove your claim.