DOC PREVIEW
MIT 6 006 - Final Examination

This preview shows page 1-2-3-4-5-6 out of 17 pages.

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

Unformatted text preview:

Introduction to Algorithms December 15, 2008Massachusetts Institute of Technology 6.006 Fall 2008Professors Ronald L. Rivest and Sivan Toledo Final ExaminationFinal 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 mostprogress.• This quiz booklet contains 15 pages, including this one. Two extra sheets of scratch paperare attached. Please detach them before turning in your quiz at the end of the exam period.• This quiz is closed book. You may use three 81200× 1100or A4 crib sheets (both sides). Nocalculators or programmable devices are permitted. No cell phones or other communicationsdevices are permitted.• Write your solutions in the space provided. If you need more space, write on the back of thesheet containing the problem. Do not put part of the answer to one problem on the back ofthe 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 citeknown results.• Show your work, as partial credit will be given. You will be graded not only on the correct-ness 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 Grader1 6 18 6 1 252 6 18 7 2 303 4 24 8 3 304 1 15 9 1 205 1 20Total 200Name:6.006 Final Examination Name 2Problem 1. Miscellaneous True/False [18 points] (6 parts)For each of the following questions, circle either T (True) or F (False). Explain your choice. (Nocredit 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 ≤PA, then A is NP-hard.Explain:(c) T F The longest common subsequence problem can be solved using an algorithm forfinding the longest path in a weighted DAG.Explain:6.006 Final Examination Name 3(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 graphexhibits optimal substructure.Explain:(f) T F A single rotation is sufficient to restore the AVL invariant after an insertion intoan AVL tree.Explain:6.006 Final Examination Name 4Problem 2. More True/False [18 points] (6 parts)For each of the following questions, circle either T (True) or F (False). Explain your choice. (Nocredit if no explanation given.)(a) T F Using hashing, we can create a sorting algorithm similar to COUNTING-SORTthat sorts a set of n (unrestricted) integers in linear time. The algorithm worksthe same as COUNTING-SORT, except it uses the hash of each integer as the indexinto the counting sort table.Explain:(b) T F There exists a comparison-based algorithm to construct a BST from an unorderedlist 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 toproduce no tree edges.Explain:6.006 Final Examination Name 5(d) T F A max-heap can support both the INCREASE-KEY and DECREASE-KEY opera-tions in Θ(lg n) time.Explain:(e) T F In a top-down approach to dynamic programming, the larger subproblems aresolved before the smaller ones.Explain:(f) T F Running a DFS on an undirected graph G = (V, E) always produces the samenumber of cross edges, no matter what order the vertex list V is in and no matterwhat order the adjacency lists for each vertex are in.Explain:6.006 Final Examination Name 6Problem 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 t1and t2are equivalent if they contain exactly the same ele-ments. That is, for all x ∈ t1, x ∈ t2, and for all y ∈ t2, y ∈ t1. Devise an efficientalgorithm to determine if BSTs t1and t2are equivalent. What is the running time ofyour algorithm, assuming |t1| = |t2| = n?(b) You are given a very long n-letter string, S, containing transcripts of phone callsobtained from a wiretap of a prominent politician. Describe, at a high level, an efficientalgorithm for finding the 4-letter substring that appears most frequently within S.6.006 Final Examination Name 7(c) A word ladder is a sequence of words such that each word is an English word, andeach pair of consecutive words differs by replacing exactly one letter with another.Here is a simple example:TREE, FREE, FRET, FRAT, FEAT, HEAT, HEAPAssume 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 usinga preprocessed lookup table). Describe an efficient algorithm that finds a word ladder,beginning at w1and ending at w2, of minimum length.(d) What procedure would you use to find a longest path from a given vertex s to a givenvertex t in a weighted directed acyclic graph, when negative edge weights are present?6.006 Final Examination Name 8Problem 4. Changing Colors [15 points]Consider a directed graph G where each edge (u, v ) ∈ E has both a weight w(u, v) (not necessarilypositive) as well as a color color(u, v) ∈ {red, blue}.The weight of a path p = v1→ v2→ . . . → vkis 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 analyzeits running time. (You may assume that there exists such a path.) For full credit, your algorithmshould have a running time of O(V E), but partial credit will be awarded for slower solutions.6.006 Final Examination Name 9Problem 5. DAG Paths [20 points]Consider two vertices, s and t, in some directed acyclic graph G = (V, E). Give an efficientalgorithm to determine whether the number of paths in G from s to t is odd or even. Analyze itsrunning time in terms of |V | and |E|.6.006 Final Examination Name 10Problem 6. Square Depth [25 points]Imagine starting with the given number n, and repeatedly chopping off a digit from one end orthe other (your choice), until only one digit is left. The square-depth S(n) of n is


View Full Document

MIT 6 006 - Final Examination

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 Final Examination
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 Final Examination 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 Final Examination 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?