December 15 2008 6 006 Fall 2008 Final Examination Introduction to Algorithms Massachusetts Institute of Technology Professors Ronald L Rivest and Sivan Toledo Final Examination Do not open this quiz booklet until directed to do so Read all the instructions on this page When the quiz begins write your name on every page of this quiz booklet You have 180 minutes to earn 200 points Do not spend too much time on any one problem Read them all through first and attack them in the order that allows you to make the most progress This quiz booklet contains 15 pages including this one Two extra sheets of scratch paper are attached Please detach them before turning in your quiz at the end of the exam period 00 This quiz is closed book You may use three 8 21 1100 or A4 crib sheets both sides No calculators or programmable devices are permitted No cell phones or other communications devices are permitted Write your solutions in the space provided If you need more space write on the back of the sheet containing the problem Do not put part of the answer to one problem on the back of the sheet for another problem since the pages may be separated for grading Do not waste time and paper rederiving facts that we have studied It is sufficient to cite known results Show your work as partial credit will be given You will be graded not only on the correctness of your answer but also on the clarity with which you express it Be neat Good luck Problem Parts Points Grade Grader Problem Parts Points Grade 1 6 18 6 1 25 2 6 18 7 2 30 3 4 24 8 3 30 4 1 15 9 1 20 5 1 20 Total Name 200 Grader 6 006 Final Examination Name 2 Problem 1 Miscellaneous True False 18 points 6 parts For each of the following questions circle either T True or F False Explain your choice No credit if no explanation given a T F If the load factor of a hash table is less than 1 then there are no collisions Explain b T F If SAT P A then A is NP hard Explain c T F The longest common subsequence problem can be solved using an algorithm for finding the longest path in a weighted DAG Explain 6 006 Final Examination Name d T F Applying a Givens rotation to a matrix changes at most one row of the matrix Explain e T F The problem of finding the shortest path from s to t in a directed weighted graph exhibits optimal substructure Explain f T F A single rotation is sufficient to restore the AVL invariant after an insertion into an AVL tree Explain 3 6 006 Final Examination Name 4 Problem 2 More True False 18 points 6 parts For each of the following questions circle either T True or F False Explain your choice No credit if no explanation given a T F Using hashing we can create a sorting algorithm similar to COUNTING SORT that sorts a set of n unrestricted integers in linear time The algorithm works the same as COUNTING SORT except it uses the hash of each integer as the index into the counting sort table Explain b T F There exists a comparison based algorithm to construct a BST from an unordered list of n elements in O n time Explain c T F It is possible for a DFS on a directed graph with a positive number of edges to produce no tree edges Explain 6 006 Final Examination Name d T F A max heap can support both the tions in lg n time Explain 5 INCREASE KEY and DECREASE KEY opera e T F In a top down approach to dynamic programming the larger subproblems are solved before the smaller ones Explain f T F Running a DFS on an undirected graph G V E always produces the same number of cross edges no matter what order the vertex list V is in and no matter what order the adjacency lists for each vertex are in Explain 6 006 Final Examination Name Problem 3 Miscellaneous Short Answer 24 points 4 parts You should be able to answer each question in no more than a few sentences a Two binary search trees t1 and t2 are equivalent if they contain exactly the same elements That is for all x t1 x t2 and for all y t2 y t1 Devise an efficient algorithm to determine if BSTs t1 and t2 are equivalent What is the running time of your algorithm assuming t1 t2 n b You are given a very long n letter string S containing transcripts of phone calls obtained from a wiretap of a prominent politician Describe at a high level an efficient algorithm for finding the 4 letter substring that appears most frequently within S 6 6 006 Final Examination Name c A word ladder is a sequence of words such that each word is an English word and each pair of consecutive words differs by replacing exactly one letter with another Here is a simple example TREE FREE FRET FRAT FEAT HEAT HEAP Assume that you are supplied with a function GET WORDS w that returns in 1 time a list of all English words that differ from w by exactly one letter perhaps using a preprocessed lookup table Describe an efficient algorithm that finds a word ladder beginning at w1 and ending at w2 of minimum length d What procedure would you use to find a longest path from a given vertex s to a given vertex t in a weighted directed acyclic graph when negative edge weights are present 7 6 006 Final Examination Name 8 Problem 4 Changing Colors 15 points Consider a directed graph G where each edge u v E has both a weight w u v not necessarily positive as well as a color color u v red blue The weight of a path p v1 v2 vk is equal to the sum of the weights of the edges plus 5 for each pair of adjacent edges that are not the same color That is when traversing a path it costs an additional 5 units to switch from one edge to another of a different color Give an efficient algorithm to find a lowest cost path between two vertices s and t and analyze its running time You may assume that there exists such a path For full credit your algorithm should have a running time of O V E but partial credit will be awarded for slower solutions 6 006 Final Examination Name 9 Problem 5 DAG Paths 20 points Consider two vertices s and t in some directed acyclic graph G V E Give an efficient algorithm to determine whether the number of paths in G from s to t is odd or even Analyze its running time in terms of V and E 6 006 Final Examination Name 10 Problem 6 Square Depth 25 points Imagine starting with the given number n and repeatedly chopping …
View Full Document
Unlocking...