Homework 1

Asymptotic Analysis and Priority Queues

Due: Friday, Oct 17, beginning of class

This assignment is designed to give you practice with the mathematical concepts behind algorithmic analysis as well as to introduce working with various implementations of priority queues, which will be useful in the next programming project.

Note: This is a written assignment, so late homework will not be accepted. There is no electronic turn-in. Problem numbers refer to the Weiss textbook.

Total: 100 points. 10 points for each problem.

  1. [Basic math] Problem 1.8, parts (a), (b)

  2. [Basic math] Problem 1.12, parts (a) and (b). Hint: Use induction for part (b); also possible with (a).

  3. [Big-O notation] Simplify the following expressions as much as possible using the Big-O notation, expressing each as big-O of some function of n, e.g. 3 n + log n = O(n). You don't need to give the constants c and n0 for this problem, but for practice, try finding them for some of your answers. 
      a. n3 + 100 n

  b. 2 n2 - n + 2100

  c. 3 log log n + log2 n

  d. 10 n2 - 5 n + n3 log n

  e. 2.5n + n100

  4. [Program analysis] Problem 2.7, part (a), fragments (2) to (4). Briefly justify your answer.

  5. [Recursive equations] Estimate the running times of the following functions using the Big-O notation. Make sure to state the recursive equation for running time, and solve it using your favorite method (such as expansion, induction). 
    int fun_a(int n) {
  if (n<=1) return 100;
  else return 2*fun_a(n-1);
}

int fun_b(int n) {
  if (n<=1) return 100;
  else return fun_b(n/2) * fun_b(n/2 - 1);
}

  6. [d-Heaps] Problem 6.14. Also indicate the index of the array that contains (a) the root, (b) the next available location for insert. Assume, as in the lectures, that location zero stores the size of the d-heap.

  7. [Leftist Heaps] Problem 6.19

  8. [Leftist Heaps] Problem 6.25

  9. [Skew Heaps] Problem 6.27. Show the result for the intermediate skew heap resulting after adding 1-3 and 1-6, and the final heap after adding 1-15. (You may show all 15 heaps if it's easier; we will look at only the above 3 for grading.)

  10. [Binomial Qs] Problem 6.32