Introduction to Algorithms: 6.006Massachusetts Institute of Technology September 23, 2010Professors Konstantinos Daskalakis and Patrick Jaillet Handout 2Problem Set 2This 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 5th at 11:59PM.Part B questions are due Thursday, October 7th 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 5th1. (15 points) Building a Balanced Search Tree from a Sorted List(a) (5 points) Given a list of n numbers, we can build a binary search tree containingthese numbers by starting with an empty tree and inserting the numbers from the listone by one into the tree. By employing appropriate rebalancing procedures, e.g. as inAVL-trees, the total time needed to build this tree will be O(n log n).Now assume that the elements in this list of n numbers given to you are already sorted.Show how to construct in O(n) time a binary search tree containing these numbers.The tree should be roughly balanced (its height should be O(log n))(b) (5 points) Argue that your algorithm returns a tree of height O(log n). Note: It isprobably easier to prove an absolute bound (such as 1 + log n or 2 log n) than to useasymptotic notation in the argument.(c) (5 points) Argue that the algorithm runs in O(n) time (here it is hard to avoid theasymptotic notation, so use asymptotic notation).2. (20 points) Implementing the Runway Reservation System(a) (5 points) Explain how to implement the runway reservation system such that all oper-ations – checking whether a request to land at time t is valid, inserting a landing timeinto the system, and deleting a landing time from the system – take O(log n) time,2 Handout 2: Problem Set 2where n is the total number of scheduled landing times in the system before the oper-ation. Remember, a requested time t is valid if there are no scheduled landings within< 3 minutes of t. Give algorithms for the three operations and analyze their runningtime.(b) (5 points) Given two times t1and t2with t1< t2, give an algorithm that returns all thescheduled landing times that are (inclusively) between t1and t2. If the total number ofsuch landing times is k, then the running time of your algorithm should be O(k +log n).(c) (5 points) Given two times t1and t2with t1< t2, give an algorithm to count thenumber of scheduled landing times that are (inclusively) between t1and t2in O(log n)time, independent of the number of such landing times. You are allowed to augmentthe binary search tree nodes.(d) (5 points) Given a requested time t which is invalid, give an O(log n)-time algorithmto find the smallest time t2such that t2> t and t2is valid. You are allowed to augmentthe binary search tree nodes.3. (15 points) Collision ResolutionAssume simple uniform hashing in the entire problem.(a) (5 points) Consider a hash table with m slots that uses chaining for collision resolution.The table is initially empty. What is the probability that, after four keys are inserted,there is a chain of size exactly 3?(b) (5 points) Consider a hash table with m slots that uses open addressing with linearprobing. The table is initially empty. A key k1is inserted into the table, followed bykey k2, and then key k3. What is the probability that the total number of probes whileinserting these keys is at least 4?(c) (5 points) Suppose you have a hash table where the load-factor α is related to thenumber n of elements in the table by the following formula:α = 1 −1√n.If you resolve collisions by open addressing, what is the expected time for an unsuc-cessful search in terms of n?Part B: Due Thursday, October 7th(50 points) Remote Error CorrectionProf. Daskalakis went to Mordor to give a talk. He was planning to work on Problem Set 3 (PS3)for 6.006 during his visit. Unfortunately, his computer broke and corrupted the latest copy of PS3.Handout 2: Problem Set 2 3A small fraction of the lines of the file was affected. Prof. Daskalakis could just download the latestcopy of the file, but Mordor (The Land of Shady ISPs) is infamous for slow and pricey Internetaccess (2 magic rings per each transferred and received byte).Help Prof. Daskalakis //////////////////////////////////////destroy////////////////////the/////////////////////////ring recover the file and prepare PS3 on time! Design an in-teractive protocol for detecting and correcting corrupted characters that uses little communication.The file file_transfer_skeleton.py has three unimplemented functions. Your goal inthis problem is to implement them. (Feel free to add helper methods.)1. First, Prof. Daskalakis and Prof. Jaillet, who is in Cambridge, need a good hash functionwhich would compute a hash value for any contiguous subset of lines of a file.(5 points) Implement a division hash in the function hash_function, which returns thehash value of a string.(20 points)The function compute_node_values should use your function hash_functionto precompute all useful hash values for the old file and the new file. The hash values shouldbe kept in HashOldFile and HashNewFile, respectively. In order to compute these val-ues efficiently you should use the idea behind a rolling hash, i.e. instead of computing eachvalue from scratch, exploit the fact that if you know the hash values of two blocks of lines,then with a constant number of operations you can compute the hash of the concatenation ofthese two blocks of lines.2. (4 points) Suppose the two copies of the file differ in some number of consecutive lines.Let n be the total number of lines in the file. How can Prof. Daskalakis and Prof. Jaillet usebinary search to find the start and end of the corruption by exchanging only O(log n) hashvalues?(4 points) Let W be the number of corrupted lines
View Full Document
Unlocking...