Introduction to Algorithms 6 006 Massachusetts Institute of Technology Professors Konstantinos Daskalakis and Patrick Jaillet October 19 2010 Handout 4 Problem Set 4 This problem set is divided into two parts Part A problems are theory questions and Part B problems 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 in PDF form using LATEX or scanned handwritten solutions Your solution to Part B should be a valid Python file together with one PDF file containing your solutions to the two theoretical questions in 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 solution which is described clearly Convoluted and obtuse descriptions might receive low marks even when 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 2nd 1 15 points Word Ladders A common word game is to take two English words w1 and w2 of the same length and try to traverse a word ladder from w1 to w2 by changing one letter at a time The challenge of the 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 is HEAP HEAT PEAT PERT PORT SORT There 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 and that w can reach at most W other words For two words w1 and w2 let Lw1 w2 be the number of words in the shortest word ladder between w1 and w2 a 10 points Given two words of the same length w1 and w2 give an algorithm for finding a word ladder it need not be the shortest word ladder between w1 and w2 or declaring that one does not exist You may assume that you have access to a function I S W ORD that runs in constant time and takes any string and returns TRUE if that string is 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 w1 and w2 and returns the length of the shortest word ladder from w1 to w2 Explain how 2 Handout 4 Problem Set 4 Figure 1 The connected clusters of a graph The connected clusters are shown in gray The cluster graph 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 what is now the running time of the algorithm in terms of Lw1 w2 e and W 2 15 points Cycle Detection A 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 an algorithm 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 on DFS that determines in O V E time whether there is a cycle in G 3 20 points Clustering Given directed graph G V E a connected cluster of the graph is a set of vertices U V such that each vertex u U can reach all other vertices in U For example a cycle is a connected cluster The connected clusters of a graph G are a set of connected clusters c1 c2 cn where each 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 still have a connected cluster In other words a cluster c is maximally sized if there exists no two vertices v c and u 6 c such that v can reach u and u can reach v An example of the connected 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 the connected clusters are just each vertex individually a 10 points The transpose of a directed graph G V E is the graph GT V E T where E T is the edge set E with the directions of each edge flipped GT has the same connected clusters as G Specifically if and only if a vertex v can reach a vertex u in G and in GT v and u are in the same connected cluster Use this fact you do not need to prove it to write an algorithm for finding the connected clusters of a directed graph Handout 4 Problem Set 4 3 represented using adjacency lists in O V E time You should give a running time analysis for your algorithm and a proof of correctness b 5 points Once we have identified the connected clusters of the graph we can create another graph the cluster graph G V E from these clusters The vertices of G are the connected clusters of G so that each vertex of G is a set of the vertices of G We draw an edge from a cluster c1 V to a cluster c2 V if in G there is a directed edge from a vertex v1 c1 to a vertex v2 c2 In other words we draw a directed edge from c1 to c2 if some vertex in c1 can reach some vertex in c2 An example of a cluster graph is shown in Figure 1 Show how to modify your algorithm from Part 3a to output the cluster graph G rather than just the connected clusters of G You are already computing V so you just need to show 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 4 2 6 6 6 6 6 6 6 6 6 6 6 6 6 4 W W W W W W W W W W W W W W W W W W W W W O W O W B O O W W W O W O W O W W W W W O O O O O W O W W W O W W W O W O W W W O W O O O O E W W W O W W W O W O W W W O O O W O W O …
View Full Document
Unlocking...