Introduction to Algorithms: 6.006Massachusetts Institute of Technology March 2nd, 2010Professors Piotr Indyk and David Karger Problem Set 3Problem Set 3This problem set is divided into two parts: Part A problems are theory questions, and Part Bproblems 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 inPDF form using LATEX or scanned handwritten solutions. Your solution to Part B should be a validPython 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 solutionwhich is described clearly. Convoluted and obtuse descriptions might receive low marks, evenwhen 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 16th1. (25 points) d-ary HeapsIn class, we’ve seen binary heaps, where each node has at most two children. A d-ary heapis a heap in which each non-leaf node (except perhaps one) has exactly d children. Forexample, this is a 3-ary heap:(a) (2 points) Suppose that we implement a d-ary heap using an array A, similarly to howwe implement binary heaps. That is, the root is contained in A[0], its children arecontained 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, LEFT and RIGHT are nolonger sufficient. How do we implement the CHILD(i, k) function, which computes theindex 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 nelements in terms of n and d.(d) (5 points) Give the asymptotic running times (in terms of n and d) of the HEAPIFY andINCREASE-KEY 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 thesize of the input array, n. What is the height of the resulting heap (in terms of n) if wechoose d = Θ(1)? What if d = Θ(log n)? What about d = Θ(n)?(HINT: remember that logdn =log nlog d. This might simplify your expressions a little.)(f) (5 points) What are the running times of HEAPIFY and INCREASE-KEY for the threechoices of d above? Do the running times increase or decrease when you increase d?If your program calls HEAPIFY and INCREASE-KEY the same number of times, whatwould be your choice for d and why?2. (25 points) Monotone Priority QueuesA “monotone priority queue” (MPQ) is a (max) priority queue that only allows monotoni-cally 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 beenextracted, returns ∞. This does not modify the MPQ.• Extract Max(Q): Removes and returns the maximum node currently in Q, andupdates 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 theMPQ is not modified.When asked to “describe an implementation”, you may start with something already provenin 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] forsome fixed integer value k. Describe an implementation of such a monotone priorityqueue 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 3Part B: Due Thursday, March 18th(50 points) Pset SchedulingBen 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 gradepenalty for each day late.Suppose that problem set i, where i is in {1 . . . N}, takes Didays to complete and has a penaltyof Pipoints per day late. There is no limit to the number of penalty points Ben can accrue. (Ben’spenalty 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 inorder to minimize the total number of penalty points Ben receives on all of his assignments. Yourprogram will be run from the command line. (Note that when a Python program is run from thecommand line, the test name == ’ main ’ will return True.) Your program shouldread the input from the file ps3b.in and write the correct output to ps3b.out. After writingthe output, your program should exit. The input and output formats are given below. Failure tocorrectly implement this specification will lose you points.As part of your program, you will need to do some sorting. You should write your own implemen-tation 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 defaultPython 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 usingthis function, one approach is to put them in a tuple. Python will then sort the tuples by their firstelements, breaking ties by second element etc.) Using this function specification will allow us tobetter 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 containstwo integers, Diand Pi, separated with a single space.Sample Input44 12 51 22 34 Problem Set 3Output Format (file ps3b.out)Line 1: A single integer which is the minimum possible number of penalty points Ben canreceive. (Note that a floating point answer, such as 40.0, will receive fewer points.)Sample Output40Sample ExplanationIn the sample above, Ben first spends 2 days finishing pset #2, accruing 10 penalty points.He
View Full Document
Unlocking...