Introduction to Algorithms: 6.006Massachusetts Institute of Technology October 23, 2007Professors Ron Rivest and Srini Devadas Handout 13Problem Set 4This problem set is due November 6 at 11:59PM.Solutions should be turned in through the course website in PS or PDF form using LATEX or scannedhandwritten solutions, or they may be handwritten and turned in to a member of the 6.006 coursestaff on or before the due date. Hand-drawn diagrams may also be referenced in your LATEX writeupand turned in at the next day’s recitation.A template for writing up solutions in LATEX is available on the course website.Exercises are for extra practice and should not be turned in.Exercises:• Exercise 6.1-3 from CLRS.• Exercise 6.2-1 from CLRS.• Exercise 6.3-1 from CLRS.• Exercise 6.4-1 from CLRS.• Exercise 6.4-3 from CLRS.• Exercise 6.5-4 from CLRS.• Exercise 8.2-2 from CLRS.• Exercise 8.4-1 from CLRS.1. (12 points) Heap DeleteThe operation HEAP-DELETE(A, i) deletes the item in node i from heap A. Give a pseu-docode implementation of HEAP-DELETE that runs in O(lg n) time for an n-element max-heap, using notation similar to p. 140 of CLRS; you may choose to use Python syntax.2. Monotone Priority QueuesA “monotone priority queue” (MPQ) is a data structure that supports the following opera-tions:• MAX(Q) - Returns the maximum element in Q. The maximum of a new, empty MPQis initially ∞. Otherwise, the maximum of an empty MPQ is the last element to havebeen deleted. Note that MAX(Q) leaves the elements of Q unchanged.2 Handout 13: Problem Set 4• DELETE-MAX(Q) - If Q is empty, returns MAX(Q). Otherwise, removes and returnsMAX(Q). If the queue is empty after the operation, the last deleted value remains themaximum. In other words, MAX(Q) is monotonically decreasing and does not resetwhen the MPQ is empty.• INSERT (Q, x) - Inserts x into Q given that x ≤ MAX(Q). If x > MAX(Q), then theMPQ is not modified.For this problem, assume that x is an integer in the range [0, k] for some fixed integer valuek.(a) (9 points) Give 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) (9 points) Give an implementation of a monotone priority queue that takes O(m + k)time to perform m total operations. Hint: Use an idea from COUNTING-SORT.3. Gas SimulationIn this problem, we consider a simulation of n bouncing balls in two dimensions inside asquare box. Each ball has a mass and radius, as well as a position (x, y) and velocity vector,which they follow until they collide with another ball or a wall. Collisions between ballsconserve energy and momentum. This model can be used to simulate how the moleculesof a gas behave, fo r example. The box is 8192 by 8192 units wide, and each ball has amaximum radius of 128 units.The initial code, featuring an interactive graphical simulation, is given to you athttp://courses.csail.mit.edu/6.006/fall07/source/gas.py. You may need to install the pygamemodule (available from http://pygame.org) for graphics if you don’t already have it.You may notice that performance, indicated by the simulation steps per second rate, slowsdown significantly as you increase the number of balls. Your goal is to improve the runningtime of the detect collisions function, which computes whether pairs of balls collide(two balls are said to collide if they overlap) and dispatches to the handle collisionfunction to compute the new ball velocities. You do not need to worry about handle collision.For this problem, there is no single right answer. We’d like you to explore the techniqueswe’ve introduced in class to improve the running time of the simulation.(a) (3 points) What is the running time of detect collisions in terms of n, thenumber of balls? Do not include the time used by handle collision.(b) (15 points) Write a more efficient detect collisions routine. To be correct, itmust still detect any collisions. The code provided does correctly calculate whetherballs collide, so you can use it to compare against your results.Submit your version of gas.py, containing an improved detect collisions rou-tine. You may find the option to automatically pause after a certain number of timestepsuseful, as well as the count of total collisions to spot if something is wrong.Handout 13: Problem Set 4 3(c) (9 points) Explain how your detect collisions algorithm is asymptotically fasterthan the original implementation. We do not expect a formal proof here, but give justifi-cations where you can. Again, do not include the time used by handle collision.(d) (3 points) After 2048 timesteps, what is the ratio of the increase in simulation stepsper second of your version compared to the given code for n = 100? n = 200? Howmany total collisions are counted in each case? (For this problem, use the interface atthe starting screen to set the number of balls and to pause at 2048
View Full Document
Unlocking...