Homework 1

Asymptotic Analysis and Priority Queues

Due: Wednesday, Jan 25, at the beginning of class

Please put your quiz section (AA, AB, BA, BB) at the top of your paper in addition to your name.

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: 80 points.

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

2) [Big-O notation] (10 points) 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 n₀ 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

3) [Program analysis] (10 points) Problem 2.7, part (a) only, fragments (2) to (6). Briefly justify your answer.

4) [Recursive equations] (5 points) Estimate the running time of the following function 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);
}
 

5) [Binary Min Heaps] (5 points total)

a) Show the result of inserting: 10,12,1,14,6,5,8,15,3,9,7,4,11,13,2 one at a time into an initially empty binary heap. Check your work!

b) Show the result of performing two deleteMin operations on the heap you created in part a).

6) [d-Heaps] (10 points) Problem 6.14. Also indicate the index of the array that contains (a) the root, (b) the next available location for insert. (Remember the root is stored in position 1)

7) [Leftist Heaps] (10 points) Problem 6.19

8) [Skew Heaps] (10 points) 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; although we will look at only the above 3 for grading.)

9) [Binomial Qs] (10 points) Problem 6.32