DOC PREVIEW
MIT 6 006 - Problem Set #4

This preview shows page 1-2 out of 6 pages.

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

Unformatted text preview:

Introduction to Algorithms: 6.006Massachusetts Institute of Technology October 19, 2010Professors Konstantinos Daskalakis and Patrick Jaillet Handout 4Problem Set 4This 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, November 2nd at 11:59PM.Part B questions are due Thursday, November 4th 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, November 2nd1. (15 points) Word LaddersA common word game is to take two English words, w1and w2, of the same length and tryto traverse a “word ladder” from w1to w2by changing one letter at a time. The challenge ofthe game is to ensure that each time you change a letter, you still have a valid English word.For example, a word ladder from HEAP to SORT isHEAP, HEAT, PEAT, PERT, PORT, SORTThere may be many or no word ladders for some words.For any word w, we assume that there are at most e English words within one letter of w andthat w can reach at most W other words. For two words w1and w2, let Lw1,w2be the numberof words in the shortest word ladder between w1and w2.(a) (10 points) Given two words of the same length, w1and w2, give an algorithm forfinding a word ladder (it need not be the shortest word ladder) between w1and w2ordeclaring that one does not exist. You may assume that you have access to a functionISWORD that runs in constant time and takes any string and returns TRUE if that stringis a valid English word and FALSE otherwise. Do your runtime analysis in terms of e,W , and Lw1,w2.(b) (5 points) Now assume you are given access to the function D that takes two words w1and w2and returns the length of the shortest word ladder from w1to w2. Explain how2 Handout 4: Problem Set 4Figure 1: The connected clusters of a graph. The connected clusters are shown in gray. The clustergraph consists of the connected clusters and the edges shown by the thick dashed lines.to use D to speed up your algorithm. Assuming D(w1, w2) runs in constant time, whatis now the running time of the algorithm in terms of Lw1,w2, e, and W ?2. (15 points) Cycle DetectionA cycle is a path of edges from a node to itself.(a) (7 points) You are given a directed graph G = (V, E), and a special vertex v. Give analgorithm based on BFS that determines in O(V + E) time whether v is part of a cycle.(b) (8 points) You are given a directed graph G = (V, E). Give an algorithm based onDFS that determines in O(V + E) time whether there is a cycle in G.3. (20 points) ClusteringGiven directed graph G = (V, E), a connected cluster of the graph is a set of verticesU ⊆ V such that each vertex u ∈ U can reach all other vertices in U . For example, a cycleis a connected cluster.The connected clusters of a graph G are a set of connected clusters {c1, c2, ..., cn} whereeach vertex of the graph only belongs to one cluster and the clusters are maximally sized.A cluster is maximally sized if there is no other set of vertices we could add to it and stillhave a connected cluster. In other words, a cluster c is maximally sized if there exists notwo vertices v ∈ c and u 6∈ c such that v can reach u and u can reach v. An example of theconnected clusters of a directed graph is shown in Figure 1.We consider that a vertex can reach itself trivially so that for a graph with no edges, theconnected clusters are just each vertex individually.(a) (10 points) The transpose of a directed graph G = (V, E) is the graph GT= (V, ET)where ETis the edge set E with the directions of each edge flipped. GThas the sameconnected clusters as G. Specifically, if and only if a vertex v can reach a vertex u inG and in GT, v and u are in the same connected cluster. Use this fact (you do not needto prove it) to write an algorithm for finding the connected clusters of a directed graphHandout 4: Problem Set 4 3represented using adjacency lists in O(V + E) time. You should give a running timeanalysis for your algorithm and a proof of correctness.(b) (5 points) Once we have identified the connected clusters of the graph, we can createanother graph, the cluster graph, G = (V, E) from these clusters. The vertices of G arethe connected clusters of G so that each vertex of G is a set of the vertices of G. Wedraw an edge from a cluster c1∈ V to a cluster c2∈ V if, in G, there is a directed edgefrom a vertex v1∈ c1to a vertex v2∈ c2. In other words, we draw a directed edge fromc1to c2if some vertex in c1can reach some vertex in c2. An example of a cluster graphis shown in Figure 1Show how to modify your algorithm from Part 3a to output the cluster graph, G, ratherthan just the connected clusters of G. You are already computing V so you just need toshow how to find E. This should not change the running time of your algorithm.(c) (5 points) Argue that G is a DAG. (Hint: Argue by contradiction.)4 Handout 4: Problem Set 4266666666666664‘W’ ‘W’ ‘W’ ‘W’ ‘W’ ‘W’ ‘W’ ‘W’ ‘W’ ‘W’‘W’ ‘W’ ‘O’ ‘O’ ‘O’ ‘O’ ‘O’ ‘O’ ‘O’ ‘W’‘W’ ‘W’ ‘W’ ‘W’ ‘O’ ‘W’ ‘W’ ‘W’ ‘O’ ‘W’‘W’ ‘W’ ‘O’ ‘O’ ‘O’ ‘W’ ‘O’ ‘W’ ‘O’ ‘W’‘W’ ‘W’ ‘W’ ‘W’ ‘O’ ‘W’ ‘O’ ‘W’ ‘W’ ‘W’‘W’ ‘W’ ‘B’ ‘O’ ‘O’ ‘O’ ‘O’ ‘O’ ‘O’ ‘W’‘W’ ‘W’ ‘O’ ‘W’ ‘W’ ‘W’ ‘O’ ‘W’ ‘W’ ‘W’‘W’ ‘W’ ‘O’ ‘W’ ‘O’ ‘O’ ‘E’ ‘O’ ‘O’ ‘W’‘W’ ‘W’ ‘W’ ‘W’ ‘W’ ‘W’ ‘W’ ‘W’ ‘W’ ‘W’‘W’ ‘W’ ‘W’ ‘W’ ‘W’ ‘W’ ‘W’ ‘W’ ‘W’ ‘W’377777777777775Figure 2: A 10x10 maze created using DFS. The starting square is blue and the ending squaregreen. Its


View Full Document

MIT 6 006 - Problem Set #4

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 #4
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 #4 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 #4 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?