Introduction to Algorithms: 6.006Massachusetts Institute of Technology March 17, 2009Professors Sivan Toledo and Alan Edelman Handout 6Problem Set 4This problem set is divided into two parts: Part A problems are programming tasks, and Part Bproblems are theory questions.Part A questions are due Tuesday, April 7th at 11:59PM.Part B questions are due Thursday, April 9th at 11:59PM.Solutions should be turned in through the course website in PDF form using LATEX or scannedhandwritten solutions.A template for writing up solutions in LATEX is 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.Exercises are for extra practice and should not be turned in.Exercises:• CLRS 22.2-3 (page 539)• CLRS 22.2-8 (page 539)• CLRS 22.3-9 (page 548)• CLRS 22.3-10 (page 549)Part A: Due Tuesday, April 7th1. (50 points) 2 × 2 × 2 Rubik’s CubeWe say that a configuration of the cube is k levels from the solved position if you can reachthe configuration in exactly k twists, but cannot reach the it in any fewer twists.Download ps4 rubik.zip from the class website. We also provide a GUI representationof the Rubik’s cube in ps4 rubik GUI.zip, courtesy of two 6.006 students last year.(a) (20 points) For this problem, we will use breadth-first search to recreate the column la-beled f in the chart seen at http://en.wikipedia.org/wiki/Pocket Cube.Write a function positions at level in level.py that takes a nonnegativeinteger argument level, and returns the number of configurations that are level2 Handout 6: Problem Set 4levels from the solved configuration (rubik.I), using both quarter twists and halftwists (twisting the cube by 90 or 180 degrees).The code in rubik.py only defines the rubik.quarter twists move set, soyou should start by defining a new move set that includes half twists as well. Do notmodify rubik.quarter twists because you will need it for the next part of thisproblem.Test your code using test level.py, and submit it to the class website. Testcasesabove level 8 are commented out, since they may require more memory than manycomputers have.(b) (30 points) Now we will solve the Rubik’s cube puzzle by finding the shortest pathbetween two configurations (the start and goal). For this part of the problem, we willlimit the move set to only allow quarter twists (half twists are not allowed).Your code from part (a) could easily be modified to find shortest paths, but a BFS thatgoes as deep as 14 levels will take a few minutes (not to mention the memory needed).A few minutes might be fine for creating a Wikipedia page, but we want to solve thecube fast!Instead, we will take advantage of a property of the graph that we can see in the chart.In particular, the number of nodes at level 7 (half the diameter) is much smaller thanhalf the total number of nodes.With this in mind, we can instead do a two-way BFS, starting from each end at thesame time, and meeting in the middle. At each step, expand one level from the startposition, and one level from the end position, and then check to see whether any of thenew nodes have been discovered in both searches. If there is such a node, we can justread off parent pointers (in the correct order) to return the shortest path.Write a function shortest path in solver.py that takes two positions, and re-turns a list of moves that is a shortest path between the two positions.Test your code using test solver.py. Check that your code runs at close to thesame speed as level 7 from part(a) in the worst case, after modifying it to use just thequater twist move set.Submit your code to the class website. No written part is required for any part of thisproblem, but you should make sure your code is adequately documented so that we canunderstand it.(c) (Optional) Go out and impress your friends with new 2x2x2 Rubik’s Cube solver youjust created! You can test your code using rubik solver GUI.py, which will askyou to input the starting configuration and show you the shortest path solution. You willneed to copy your solver.py file into the directory where the GUI is located.If you have any feedback, bug reports, or suggestions for improvement on the GUI,please send it to the TAs.Handout 6: Problem Set 4 3Part B: Due Thursday, April 9th1. (16 points) Eliminating Cycles by Removing One EdgeFor each of the following statements, prove the statement or give a small counter exampleto show that it is false. You may use LATEX to draw counter-example graphs if necessary (thesolution template contains a drawing of the following graph to get you started).r r rr r rr r r-6(a) (8 points) If DFS on a graph G produces exactly one back edge, then it is possible toremove an edge from G to make the graph acyclic. (Please recall that self-loops areback edges.)(b) (8 points) If G is cyclic but can be made acyclic by removing one edge, then DFS willencounter exactly one back edge.2. (8 points) Bipartite graphsAn undirected graph is called bipartite if its nodes can each be assigned a color, either redor blue, such that no red node is adjacent to another red node, and no blue node is adjacentto another blue node. Give an efficient algorithm to determine if a graph is bipartite. Whatis its running time?3. (26 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) (12 points) You are given a graph G = (V, E), and you are told that every vertex isreachable from vertex s. You want to determine whether the graph has any cycles.Ben Bitdiddle proposes the following algorithm. Perform a BFS from s. If, during thesearch, you ever reach a node that you have already seen before, then declare that Ghas a cycle. If you never reach the same node twice, declare that there is no cycle.i. Show that Ben’s algorithm works for undirected graphs.ii. Show that Ben’s algorithm does not work for directed graphs.(c) (7 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
View Full Document
Unlocking...