MIT6006 Problem Set 5 Solution

Please write your solutions in the LATEX and Python tem-plates provided. Aim for concise solutions; convoluted and obtuse descriptions might receive low marks, even when they are correct.

Problem 5-1. [15 points] Graph Practice (a) [3 points] Draw the undirected graph described on
1 # 0 1 2 3 4 5 the right by adjacency matrix Adj: a direct access
2 Adj = [[0, 0, 1, 0, 0, 0], # 0
array Set mapping each vertex u ∈ {0, . . . , 5} to an 3 [0, 0, 0, 1, 1, 1], # 1 adjacency list Adj[u], where each adjacency list is 4 [1, 0, 0, 1, 1, 0], # 2
also implemented using a direct access array Set such 5 [0, 1, 1, 0, 0, 0], # 3 that Adj[u][v] = 1 if and only if vertices u and v 6 [0, 1, 1, 0, 0, 1], # 4
7 [0, 1, 0, 0, 1, 0]] # 5
are connected by an edge.
(b) [3 points] Write down the adjacency list representation of the graph on the right: where a Python Dictionary maps each vertex v to its adjacency list Adj[v], and each adjacency list is a Python List containing v’s outgoing neighbors listed in alphabetical order.
(c) [6 points] Run both BFS and DFS on the graph from part (b), starting from node A. While performing each search, visit the outgoing neighbors of a vertex in alphabetical order. For each search, draw the resulting tree and list vertices in the order in which they were first visited.
(d) [3 points] It is possible to remove a single edge from the graph in (b) to make it a DAG. State every edge with this property, and for each, state a topological sort order of the resulting DAG.
Problem 5-2. [10 points] Power Plants
2 Problem Set 5
Problem 5-3. [10 points] Short-Circuitry
Star-crossed androids Romie-0 and Julie-8 are planning an engagement party and want to invite all their robotic friends. Unfortunately, many pairs of their friends can’t be in the same room without short-circuiting. Romie-0 has an idea to throw two parties instead: inviting some friends to the first party, and the rest to the second. Ideally, everyone would get invited to a party, but nobody would go to the same party as someone that would make them short-circuit. Julie-8 points out to Romie-0 that this might not be possible, for example if they have three friends who all make each other short-circuit. Given the n short-circuiting pairs of friends, describe an O(n)-time algorithm to determine whether Romie-0 and Julie-8 can invite all of their friends to two peaceful parties, without anyone short-circuiting.
Problem 5-4. [10 points] Ancient Avenue
The ancient kingdom of Pesomotamia was a fertile land near the Euphris and Tigrates rivers. Newlydiscovered clay tablets show a map of the kingdom on an n × n square grid, with each square either:
• part of a river, labeled as ’euphris’ or ’tigrates’; or
• not part of a river, labeled with a string: the name of the farmer who owned the square plot of land.
The tablets accompanying the map state that ancient merchants built a trade route connecting the two rivers: a path along edges of the grid from some grid intersection adjacent to a ’euphris’ square to a grid intersection adjacent to a ’tigrates’ square. The tablets also state that the route:
• did not use any edge between two squares owned by the same farmer (so as not to trample crops); and
• was the shortest such path between the rivers (assume a shortest such path is unique).
Given the labeled map, describe an O(n2)-time algorithm to determine path of the ancient trade route.
Problem 5-5. [15 points] Statum Quest
Liza Pover is a hero on a quest for free pizza in the Statum Center, a large labyrinth with some of the best free food in the entire Technological Institute of Mathachusetts. Many unsuspecting victims have ventured into the labyrinth in search of free food, but few have escaped victorious. Luckily, Liza has downloaded a map from bplansc.tim.edu consisting of locations L (including rooms, hallways, staircases, and elevators ) and doors D which connect pairs of locations. One location e ∈ L is marked as the entrance/exit: Liza’s path must begin and end here. A subset Π ⊂ L of locations each contain a free pizza. Liza’s goal is to enter the maze, grab one pizza, and leave as quickly as possible.
Describe an O(|L| + |D|)-time algorithm to find a viable path from e to e that collects at least one pizza from Π (and possibly some of the key cards along the way to open some doors), and minimizes the number of times that Liza has to walk through a door.
Problem Set 5 3
Problem 5-6. [40 points] 6.006 Tilt
6.006 Tilt is a puzzle game played on a Tilt board: an n × n square grid, where grid square contains either a fixed obstacle, a movable slider, or neither (the grid square is empty).
A Tilt move consists of tilting a board in any of the four cardinal directions (up, left, down or right), causing each slider to slide maximally in that direction until it hits either: the edge of the board, an obstacle, or another slider that cannot slide any further. A Tilt move results in a new Tilt board configuration.
Given a Tilt board B with one grid square t labeled as the target, a sequence of k Tilt moves solves 6.006 Tilt puzzle (B, t) if applying the moves in sequence to B results in a Tilt board configuration B0 that contains a slider in square t.
The figure below shows a small 6.006 Tilt puzzle and a solution using the fewest possible moves k = 8. Obstacles are shown in black, movable sliders are circles, and the target square is shaded gray.

We represent an n × n board configuration B using a length-n tuple of length-n tuples, each representing a row of the configuration, where the grid square in row y (from the top) and column x (from the left) is B[y][x], equal to either character ’#’ (an obstacle), ’o’ (a slider), or ’.’ (neither). We represent the target square by a tuple t = (xt, yt) where the puzzle is solved when B[yt][xt] = ’o’. Your code template has a function move(B, d) which computes a move from board B in direction d in O(n2) time.
(a) [2 points] Given a Tilt puzzle with starting n × n board B containing b fixed obstacles and s movable sliders, argue that the number of board configurations reachable from B is at most
.
(c) [10 points] Given a 6.006 Tilt puzzle (B, t), describe an algorithm to return a move sequence that solves the puzzle in the fewest moves, or return that no such move sequence exists. If the puzzle’s shortest solution uses k moves ( k = ∞ if the puzzle is not solvable), your algorithm should run in O(n2 min{rk , C (n, b, s)}) time.
(d) [25 points] Write a Python function solve tilt(B, t) that implements your algorithm from part (d) using the template code provided. You can download the code template and some test cases from the website.
MIT OpenCourseWare
https://ocw.mit.edu
For information about citing these materials or our Terms of Use, visit: https://ocw.mit.edu/terms