Design and Analysis of Algorithms University of California, Irvine
Homework 2
Due on Monday, November 20, 2023 by midnight
(10 Points) Dijkstra or Not
November 6, 2023 EECS 215
Gladia has written a program that she claims implements Dijkstra’s algorithm. The program outputs two values, v.d and v.π, for each vertex v ∈ V. Give an O(V + E) time algorithm to check the output of Gladia’s program. This algorithm should determine whether the d and π values match those of some shortest-paths tree. You may assume that all edge weights are nonnegative.
(10 Points) Game of Perfect Moves
Daneel Olivaw and Elijah Baley decide to play a game on a directed acyclic graph G, which has one source s and one sink t. Each player has a token on one of the vertices of G. At the start of the game, Daneel’s token is on the source vertex s, and Elijah’s token is on the sink vertex t. The players alternate turns, with Daneel moving first. On each of his turns, Daneel moves his token forward along a directed edge; on each of his turns, Elijah moves his token backward along a directed edge. If the two tokens ever meet on the same vertex, Elijah wins the game. If Daneel’s token reaches t or Elijah’s token reaches s before the two tokens meet, then Daneel wins the game.
Describe and analyze an algorithm to determine who wins this game, assuming both players play perfectly. That is, if Daneel can win no matter how Elijah moves, then your algorithm should output “Daneel”, and if Elijah can win no matter how Daneel moves, your algorithm should output “Elijah”. (Why are these the only two possibilities?) The input to your algorithm is the graph G.
(20 Points) All-pairs Shortest Paths
Often we want to compute shortest paths between all pairs of vertices in a graph G = (V, E). There are several ways to do this. One way is to run Dijkstras algorithm using each vertex as the start node. This takes O(VElgV) time, but does not work if there are negative weights. Here we explore one fix to that suggested by Edmonds and Karp.
(a) Give an example where Dijkstras algorithm fails if there are edges of negative weight even if there are no negative cycles.
(b) Let G = (V,E) be a directed graph with possibly-negative weights d(u,v) on the edges (but no negative cycles). Define a new graph G′ that is created from G by adding a new vertex s and edges of 0-weight from s to every node in V. Let dists(v) be the shortest path distance from s to v in G′ computed via Bellman-Ford. Define new weights on G as d′ (u, v) = d(u, v) + dists(u) − dists(v). Argue that d′ (u, v) defined in this way is always positive.
(c) Argue that any path is a shortest path in G using weights d′(u,v) if and only if it is a shortest path in G using weights d(u,v). (In other words, changing the weights to d′(u,v) preserves which paths are shortest paths.)
(d) Describe how to use (b) and (c) to compute all pairwise shortest paths in O(VElgV) time.
(40 Points) Building an Energy-Efficient Home (programming assignment)
You have embarked on a mission to set up a new, energy-efficient home. To save costs, you decide to handle the wiring yourself. In this eco-friendly home, there are several types of devices and junction points:
1. Main Power Source: This is the central node from which electricity is distributed. There is only one main power source in your home.
2. Light Switch: A light switch is a specialized node that can control the flow of electricity to certain lights. It can be turned off to disconnect power to lights downstream from it.
3. LED Light: An LED light is a device controlled by a light switch. You want to ensure that each LED light has a dedicated light switch to control it.
4. Power Outlet: Power outlets should be active all the time. Therefore, they must have a direct electrical connection to the main power source with no switches in between.
5. Junction Node: A junction node is a location that can connect multiple electrical wires, allowing you to distribute power to different parts of the house.
Given the layout of the different junction points and the cost of wiring them to each other, find the most cost-efficient way to wire your energy-efficient home while adhering to the following constraints:
• You must use Kruskal’s algorithm for this assignment, with a custom disjoint-set data structure that you implement.
• Your wiring must form a spanning tree, meaning there should be no cycles in the network.
• LED lights can be wired to one another if they have the same desired switch, provided that the switch is placed between them and the main power source.
• Every type of junction point (main power source, light switches, power outlets, junction boxes, etc.) must be connected in your wiring.
• Power outlets should never be positioned behind light switches in your spanning tree. Once your spanning tree reaches a light switch, only LED lights (potentially many) can be connected behind that switch.
Input: The input file will start with a line containing two integers, J and C, representing the number of junction points and the number of possible connections, respectively. The next J lines will specify the name of a junction point along with its type (main power source, light switch, LED light, power outlet, junction box). When a switch is listed, the lights that need to be behind that switch will be always listed next to indicate this dependency. There is only one main power source. The next C lines will specify the connections by providing the names of two junction points and the associated cost.
Output:
Output the cost of the minimum wiring for your energy-efficient home that adheres to all the constraints.
Sample Input:
m1 main
j1 junction s1 switch l1 light
l2 light
o1 outlet m1 j1 5
m1 o1 1
j1 s1 1
j1 o1 2
o1 l1 1
l1 l2 2
s1 l1 6
s1 l2 1
Sample Output:
