Introduction to Algorithms 6 006 Massachusetts Institute of Technology Professors Piotr Indyk and David Karger March 2nd 2010 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 Part A questions are due Tuesday March 16th at 11 59PM Part B questions are due Thursday March 18th at 11 59PM Solutions should be turned in through the course website Your solution to Part A should be in PDF form using LATEX or scanned handwritten solutions Your solution to Part B should be a valid Python file which runs from the command line 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 the 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 Due Tuesday March 16th 1 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 heap 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 contained in A 0 its children are contained 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 2 Problem Set 3 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 2 25 points Monotone Priority Queues A monotone priority queue MPQ is a max priority queue that only allows monotonically decreasing elements to be extracted It supports the following operations Max Q Returns the key of the most recently extracted node If no nodes have been extracted returns This does not modify the MPQ Extract Max Q Removes and returns the maximum node currently in Q and updates Max Q If Q is empty returns Max Q Insert Q x Inserts x into Q given that x Max Q If x Max Q then the MPQ is not modified When asked to describe an implementation you may start with something already proven in class or in the book and simply describe modifications to that a 10 points Describe an implementation of a monotone priority queue that takes O m log m time to perform m operations starting with an empty data structure b 15 points Now suppose that every inserted key x is an integer in the range 0 k for some fixed integer value k Describe an implementation of such a monotone priority queue that takes O m k time to perform m total operations Hint Use an idea from Counting Sort Warning Be careful about the case when the queue becomes empty Problem Set 3 3 Part B Due Thursday March 18th 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 Suppose that problem set i where i is in 1 N takes Di days to complete and has a penalty of Pi points per day late 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 Help Ben by writing a program to determine the order in which Ben should do his problem sets in order to minimize the total number of penalty points Ben receives on all of his assignments Your program will be run from the command line Note that when a Python program is run from the name main will return True Your program should command line the test read the input from the file ps3b in and write the correct output to ps3b out After writing the output your program should exit The input and output formats are given below Failure to correctly implement this specification will lose you points 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 def heap sort list where list is the list to sort Your function should sort list in ascending order using the default Python ordering defined by and This means for instance that heap sort 5 1 4 0 should return 0 1 4 5 If you wish to sort more complicated objects than numbers using this function one approach is to put them in a tuple Python will then sort the tuples by their first elements breaking ties by second element etc Using this function specification will allow us to better test your code if you have a bug and give you more partial credit Input Format file ps3b in Line 1 The single integer N Lines 2 N 1 The i 1 st line describes the Ben s i th problem set and contains two integers Di and Pi separated with a single space Sample Input 4 4 2 1 2 1 5 2 3 4 Problem Set 3 Output Format file ps3b out Line 1 A single integer which is the minimum possible number of penalty points Ben can receive Note that a floating point answer such as 40 0 will receive fewer points Sample Output 40 Sample …
View Full Document
Unlocking...