Homework #1 Solution



  1. Arrange the following in increasing order of asymptotic growth rate (i.e., O( )). For full credit it is enough to just give the order. [.75 points]

      1. f1(n) = n3

      1. f2(n) = 1000n5=2

      2. f4(n) = n(log n)1000

      3. f5(n) = 2n log n


    1. f3(n) = 23 n

    2. f6(n) = 2(log n)0:9

  1. Use Karatsuba’s algorithm to multiply the following two binary integers: 10110100 and 10111101. Your entire calculations should be in binary and show all your work. [.75 points]

  1. Solve the following recurrences by the Master theorem: [.75 points]

    1. T (n) = 4T (n=5) + n.

    1. T (n) = 6T (n=3) + n.

    1. T (n) = 16T (n=4) + n2.

4* We have a list A of n integers, for some n = 2k 1, each written in binary. Every number in the range 0 to n is in the list exactly once, except for one. However, we cannot directly access the value of integer A[i] (for any i); instead, we can only access the j’th bit of i: A[i][j]. Our goal is to nd the missing number.

Give an algorithm to nd the missing integer that uses O(n) bit accesses. Prove that your algorithm runs in O(n) time. Note that a brute force solution that accesses every bit will take time (n log n). [.75 points]

Additional Problems. DO NOT turn in answers for the following problems – they are meant for your curiosity and understanding.

  1. Call an array of n numbers B[0]; B[1]; : : : ; B[n 1] L-regular if for any index i 2 f0; : : : ; n 1g, B[i] occurs within L places of its actual location in the sorted ordering. For example, any array of size n is n-regular and the array [1; 3; 2; 5; 4] is 1-regular.

Give an algorithm which takes as input L and a L-regular array B of size n and sorts the elements of B in O(n(log L))-time. You don’t need to analyze the running time or prove correctness of your algorithm (but for full-credit, your algorithm must be correct and run in time O(n(log L)).

[Hint: One way is to adapt merge sort. Beware that proving correctness for this problem is quite tricky and there are several tempting `wrong’ proofs!]

  1. Problems 2.8, 5.1, 5.4 from text.