DOC PREVIEW
MIT 6 006 - Problem Set 3

This preview shows page 1 out of 4 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 4 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 4 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Introduction to Algorithms: 6.006Massachusetts Institute of Technology October 5th, 2010Professors Konstantinos Daskalakis and Patrick Jaillet Handout 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, October 19th at 11:59PM.Part B questions are due Thursday, October 21st 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, together with one PDF file containing your solutions to the two theoretical questionsin Part B.Templates for writing up solutions in LATEX are 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, October 19th1. (20 points) Finding the Largest i Elements in Sorted OrderGiven an array of n numbers, we want to find the i largest elements in sorted order. That is,we want to produce a list containing, in order, the largest element of the array, followed bythe 2nd largest, etc., until the ith largest. Assume that i is fixed beforehand, and all inputshave n > i.(a) (5 points) One idea is to mergesort the input array in descending order, and then listthe first i elements of the array. Analyze the running time of this algorithm in terms ofn and i.(b) (10 points) Describe an algorithm that achieves a faster asymptotic time bound thanthe one in Part (a). Analyze the running time of this algorithm in terms of n and i.(c) (5 points) Now suppose that the elements of the array are drawn, without replacement,from the set {1, 2, ..., 2n}. Give an algorithm that solves the problem, with this addi-tional information, and analyze its running time in terms of n and i.For parts (b) and (c), full credit will be awarded only for an asymptotically optimal solution,with partial credit given for solutions with slower asymptotic running times.2. (15 points) Dynamic MediansMarianne Midling needs a data structure “DM” for maintaining a set S of numbers, support-ing the following operations:2 Handout 3: Problem Set 3• CREATE( ): Create an empty set S• INSERT(x): Add a new given number x to S• MEDIAN( ): Return a median of S. (Note that if S has even size, there are two medians;either may be returned. A median of a set of n distinct elements is larger than or equalto exactly b(n + 1)/2c or d(n + 1)/2e elements.)(Assume no duplicates are added to S.)Marianne proposes to implement this “dynamic median” data structure DM using a max-heap A and a min-heap B, such that the following two properties always hold:1. Every element in A is less than every element in B, and2. the size of A equals the size of B, or is one less.To return a median of S, she proposes to return the minimum element of B.(a) (5 points) Argue that this is correct (i.e., that a median is returned).(b) (10 points) Explain how to implement INSERT(x), while maintaining the relevant prop-erties. Analyze the running time of your INSERT algorithm in terms of n, the numberof elements in S.3. (15 points) The Optimality of the Binary Search Tree ConstructionConsider a list of n numbers and a task of building a binary search tree that contains them.In Problem 2.1 (from Problem set 2) we outlined an algorithm that performs this task bystarting with an empty tree and inserting to it the elements of the list one by one. As wementioned, by employing appropriate rebalancing procedures, e.g. as in AVL-trees, the totalrunning time of this procedure is O(n log n).Prove that in the comparison-based model of computation this running time is asymptoticallyoptimal. Namely, show that there is no algorithm in the comparison-based model that givena list of n numbers constructs a binary search trees containing them in o(n log n) time.Hint: As a first step, show that given a binary search tree one can output a sorted list of allthe numbers it contains in O(n) time.Handout 3: Problem Set 3 3Part B: Due Thursday, October 21st(50 points) Job SchedulingIrene B. Matthews, a very smart MIT undergrad, constructed a large-scale quantum computer inher backyard. Although such a machine would allow her to break all the modern cryptography,she decided to become a billionaire through legal means. She founded a company that rents themachine time to the customers. It turned out, however, that the demand for such a service wasfar larger than Irene expected. In particular, after being flooded with a stream of hundreds ofthousands of offers, she realized her machine could handle only a tiny fraction of these requests.Thus, overwhelmed by the situation, she hired you to help her out in dealing with the problem.To formalize the task you are facing, let us divide time into one-hour-long steps. In each stepthere is a batch of offers (jobs) from clients arriving. Each offer consists of the reward (number ofdollars) the client is willing to pay for having his/her job completed, and of its running time, beingthe number of one-hour-long steps needed to complete this job on Irene’s machine. In our model,we assume that once the job is run on the machine it cannot be stopped until it finishes, and thatthe machine can process only one job at a time.1. (35 points) Your first task is to implement Scheduler, a data structure that facilitatesscheduling of the incoming jobs on the machine. This data structure should contain thecurrently processed job (together with amount of steps remaining till its completion), and thepool of yet not processed jobs. Scheduler is initialized by specifying a ranking functionrank – this function takes a job as an argument and assigns score to it. Once initialized, itstarts with an empty pool and is processing a job that has zero reward and running time ofone. Scheduler should support the following operations:• add(r,t) – adds a job having reward r and running time t to the pool of yet notprocessed jobs;• advance_time() – reduces the number of steps needed to complete the currentlyprocessed job by one. If this causes the job to finish, a job in the pool that maximizesthe value of rank function should begin being


View Full Document

MIT 6 006 - Problem Set 3

Documents in this Course
Quiz 1

Quiz 1

7 pages

Quiz 2

Quiz 2

12 pages

Quiz 2

Quiz 2

9 pages

Quiz 1

Quiz 1

10 pages

Quiz 2

Quiz 2

11 pages

Quiz 1

Quiz 1

12 pages

Graphs

Graphs

27 pages

Load more
Download Problem Set 3
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Problem Set 3 and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Problem Set 3 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?