DOC PREVIEW
MIT 6 006 - QUIZ -6 006

This preview shows page 1-2-3 out of 10 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 10 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 10 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 10 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 10 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Introduction to Algorithms April 14, 2010Massachusetts Institute of Technology 6.006 Spring 2010Professors Piotr Indyk and David Karger Quiz 2Quiz 2• 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 120 minutes to earn 120 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 is closed book. You may use two 81200× 1100or A4 crib sheet (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. Pages may be separated for grading.• Do not waste time and paper rederiving facts that we have studied. It is sufficient to citeknown results.• When writing an algorithm, a clear description in English will suffice. Pseudo-code is notrequired.• When asked for an algorithm, your algorithm should have the time complexity specified inthe problem with a correct analysis. If you cannot find such an algorithm, you will generallyreceive partial credit for a slower algorithm if you analyze your algorithm correctly.• 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 Grader1 10 302 1 203 3 154 1 155 1 206 1 20Total 120Name:FridayRecitation:Zuzana10 AMDebmalya11 AMNing12 PMMatthew1 PMAlina2 PMAlex3 PM6.006 Quiz 2 Name 2Problem 1. True or False [30 points] (10 parts)For each of the following questions, circle either T (True) or F (False). There is no penalty forincorrect answers.(a) T F [3 points] For all weighted graphs and all vertices s and t, Bellman-Ford startingat s will always return a shortest path to t.(b) T F [3 points] If all edges in a graph have distinct weights, then the shortest pathbetween two vertices is unique.(c) T F [3 points] For a directed graph, the absence of back edges with respect to a BFStree implies that the graph is acyclic.(d) T F [3 points] At the termination of the Bellman-Ford algorithm, even if the graphhas a negative length cycle, a correct shortest path is found for a vertex for whichshortest path is well-defined.(e) T F [3 points] The depth of any DFS tree rooted at a vertex is at least as much as thedepth of any BFS tree rooted at the same vertex.6.006 Quiz 2 Name 3(f) T F [3 points] In bidirectional Dijkstra, the first vertex to appear in both the for-ward and backward runs must be on the shortest path between the source and thedestination.(g) T F [3 points] There is no edge in an undirected graph that jumps more than one levelof any BFS tree of the graph.(h) T F [3 points] In an unweighted graph where the distance between any two verticesis at most T, any BFS tree has depth at most T , but a DFS tree might have largerdepth.(i) T F [3 points] BFS takes O(V + E) time irrespective of whether the graph is pre-sented with an adjacency list or with an adjacency matrix.(j) T F [3 points] An undirected graph is said to be Hamiltonian if it has a cycle con-taining all the vertices. Any DFS tree on a Hamiltonian graph must have depthV − 1.6.006 Quiz 2 Name 4Problem 2. Neighborhood Finding in Low-Degree Graphs [20 points]Suppose you are given an adjacency-list representation of an N-vertex graph undirected G withnon-negative edge weights in which every vertex has at most 5 incident edges. Give an algorithmthat will find the K closest vertices to some vertex v in O(K log K) time.6.006 Quiz 2 Name 5Problem 3. Word Chain [15 points] (3 parts)A word chain is a simple word game, the object of which is to change one word into anotherthrough the smallest possible number of steps. At each step a player may perform one of fourspecific actions upon the word in play — either add a letter, remove a letter or change a letterwithout switching the order of the letters in play, or create an anagram of the current word (ananagram is a word with exactly the same number of each letter). The trick is that each new stepmust create a valid, English-language word. A quick exaple would be FROG → FOG → FLOG→ GOLF.(a) [5 points] Give an O(L)-time algorithm for deciding if two English words of lengthL are anagrams.(b) [2 points] Give an O(L)-time algorithm for deciding whether two words differ by oneletter (added/removed/changed).(c) [8 points] Suppose you are given a dictionary containing N English words of lengthat most L and two particular words. Give an O(N2· L)-time algorithm for decidingwhether there is a word chain connecting the two words.6.006 Quiz 2 Name 6Problem 4. Approximate Diameter [15 points]The diameter of a weighted undirected graph G = (V, E) is the maximum distance between anytwo vertices in G, i.e. ∆(G) = maxu,v∈Vδ(u, v) where ∆(G) is the diameter of G and δ(u, v) isthe weight of a shortest path between vertices u and v in G. Assuming that all edge weights inG are non-negative, give an O(E + V log V )-time algorithm to find a value D that satisfies thefollowing relation: ∆(G)/2 ≤ D ≤ ∆(G). You must prove that the value of D output by youralgorithm indeed satisfies the above relation.Hint: For any arbitrary vertex u, what can you say about maxv∈Vδ(u, v)?6.006 Quiz 2 Name 7Problem 5. Triple Testing [20 points]Consider the following problem: given sets A,B,C, each comprising N integers in the range−Nk. . . Nkfor some constant k > 1, determine whether there is a triple a ∈ A, b ∈ B, c ∈ Csuch that a + b + c = 0. Give a deterministic (e.g. no hashing) algorithm for this problem that runsin time O(N2).6.006 Quiz 2 Name 8Problem 6. Number of Shortest Paths [20 points]You are at an airport in a foreign city and would like to choose a hotel that has the maximumnumber of shortest paths from the airport (so that you reduce the risk of getting lost). Suppose youare given a city map with unit distance between each pair of directly connected locations. Designan O(V +E)-time algorithm that finds the number of shortest paths between the airport (the sourcevertex s) and the hotel (the target vertex t).SCRATCH PAPERSCRATCH


View Full Document

MIT 6 006 - QUIZ -6 006

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 QUIZ -6 006
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 QUIZ -6 006 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 QUIZ -6 006 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?