Introduction to Algorithms 6 006 Massachusetts Institute of Technology Professors Erik Demaine Piotr Indyk and Manolis Kellis March 1st 2011 Problem Set 3 Problem Set 3 This problem set is divided into two parts Part A problems are theory questions and Part B problems are programming tasks Both Part A and Part B questions are due Monday March 7th at 11 59PM Solutions should be turned in through the course website Your solution to Part A should be in PDF format using LATEX Your solution to Part B should be a valid Python file A template for writing up solutions in LATEX is available on the course website Remember your goal is to communicate Full credit will be given only to a correct solution which is described clearly Convoluted and obtuse descriptions might receive low marks even when they are correct Also aim for concise solutions as it will save you time spent on write ups and also help you conceptualize the key idea of the problem Part A Problem 3 1 25 points Recurrences Solve the following recurrences a 5 points T n 2T n2 n log n b 5 points T n 3T n4 n c 5 points T n T n2 T n4 n2 Hint Calculate upper and lower bounds on T n by converting the problem into recurrences you can solve using the Master Theorem Merge sort typically divides an array in half forming two recursive subproblems recursively sorts the two subproblems and then merges the two solutions Consider the c merge sort algorithm which divides the array into c roughly equal length parts recursively sorts these c subproblems and then merges the c solutions To merge c sorted lists the algorithm uses a min heap initialized with the first element of each list and repeatedly removes the minimum element from the heap appends that minimum element to the merged list and then inserts the minimum element s successor from its source list into the heap until all the elements are appended to the merged list d 5 points Write the recurrence relation for c merge sort on a list of n integers Solve it to determine the running time for some constant c e 5 points What happens to the running time if c is not a constant but rather some function of n Problem 3 2 25 points d ary Heaps In class we ve seen binary heaps where each node has at most two children A d ary heap is a heap in which each non leaf node except perhaps one has exactly d children For example this is a 3 ary max heap 2 Problem Set 3 95 56 54 10 78 7 61 8 28 42 21 a 2 points Suppose that we implement a d ary heap using an array A similarly to how we implement binary heaps That is the root is in A 0 its children are in A 1 d and so on How do we implement the PARENT i function which computes the index of the parent of the ith node for a d ary heap b 2 points Now that there might be more than two children L EFT and R IGHT are no longer sufficient How do we implement the C HILD i k function which computes the index of the kth child of the ith node 0 k d c 5 points Express in asymptotic notation the height of a d ary heap containing n elements in terms of n and d d 5 points Give the asymptotic running times in terms of n and d of the H EAPIFY and I NCREASE K EY operations for a d ary heap containing n elements e 6 points Let s suppose that when we build our d ary heap we choose d based on the size of the input array n What is the height of the resulting heap in terms of n if we choose d 1 What if d log n What about d n n This might simplify your expressions a little Hint remember that logd n log log d f 5 points What are the running times of H EAPIFY and I NCREASE K EY for the three choices of d above Do the running times increase or decrease when you increase d If your program calls H EAPIFY and I NCREASE K EY the same number of times what would be your choice for d and why Problem Set 3 3 Part B Problem 3 3 50 points Pset Scheduling Ben Bitdiddle is behind on his problem sets In fact he is already late on N different problem sets 1 N 100 000 Fortunately for Ben all of his classes accept late homework with a grade penalty for each day late unlike 6 006 Suppose that problem set i where 1 i N has a penalty of Pi points per day late and takes one full day to complete There is no limit to the number of penalty points Ben can accrue Ben s penalty adjusted score can become negative Ben is required to finish each problem set You should implement a function best score penalties which takes as input the list of daily point penalties Pi and returns the minimum number of penalties points it is possible for Ben to be assigned As part of your program you will need to do some sorting You should write your own implementation of heap sort for this problem Your implementation of heap sort should have the signature heap sort list where list is the list to sort Your function should sort list in descending order using the default Python ordering defined by and This means for instance that heap sort 5 1 4 0 should return 5 4 1 0 Using this function specification will allow us to better test your code if you have a bug and give you more partial credit Sample Input 1 5 2 3 Sample Output 21 Sample Explanation In the sample above Ben works on pset 2 on the first day pset 4 the next day pset 3 the third day and pset 1 the last day In total he accrues 5 1 3 2 2 3 1 4 21 penalty points
View Full Document
Unlocking...