This assignment is due on May 13 and should be submitted on Gradescope.

All submitted work must be done individually without consulting someone else’s solutions in accordance with the University’s “Academic Dishonesty and Plagia– rism” policies.

Before you read any further, go to the last page of this document and read the Written Assignment Guidelines section.

Problem 1. (20 points)

Let G = (V, E) be an arbitrary connected graph with weighted edges.

m = |E| is the number of edges in the graph, and n = |V| is the number of vertices.

a) Prove or disprove:  The minimum spanning tree of G includes the mini– mum weight edge in every cycle in G.

b) If the graph edge weights are distinct, then obviously the minimum span– ning tree will be unique.  But is the inverse also true?  Prove or disprove: If a graph has two edges with the same weight value, multiple minimum spanning trees must exist.

c) Describe  an  O(m log n) time  algorithm to  determine whether  or not  a graph has a unique minimum spanning tree, or if multiple minimum span– ning trees exist.

d) Prove the correctness of your algorithm.

e) Analyse the time complexity of your algorithm.

Problem 2. (20 points)

Vector Raceris a game where players take turns to move racecars around a track. Each car starts with initial velocity (0, 0) representing the velocity in the x and y directions (the change in position).  On each turn, the player may choose to increment or decrement by 1 any component of their velocity, or both, and then their racecar moves to the next position by that vector from its current position.

You are given the layout of the race track as an n × n boolean matrix where each cell track[i][j] is True if that position is part of the track, or False if it is out of bounds. If your car goes out of bounds, it will crash.

Figure 1: An example race sequence.  Note that this may not be the path with the least steps.

The starting area is the first column on the matrix, and the finish line is the last column of the matrix. The goal is to be the first to cross the finish line, while always maintaining your car’s position within the track.

Note:

• Multiple cars can share the same position, so you don’t need to consider the presence or absence of other racers.

• A car can jump over out of bounds if its velocity vector would still end up on a cell within the track.

• You must land on the finish line, overshooting the finish line counts as crashing.

Your task is to:

a) Design an efficient algorithm that will compute the minimum number of turns required to reach the finish line from the starting area, without crash– ing out of bounds.

b) Argue the correctness of your algorithm.

c) Analyse the time complexity of your algorithm.

Problem 3. (20 points)

Helen is planning a road trip from Sydney to Tamworth and she has a large map which is a road network modelled as a simple undirected connected graph G  =  (V, E) with vertices representing towns  or cities, and edge lengths l(e) representing the length of roads between them. She plans her journey originally as P, the shortest path between Sydney and Tamworth where |P| is the number of edges in it.

However, Helen knows there are planned roadworks occurring, where ex– actly one road might be closed, but at the time she is planning her trip she doesn’t know what it is.  She plans to check online just before she departs, but for the time being she would like to know the shortest distances from Sydney to Tamworth in every case – that is, what is the shortest path in G′ \ {e} for every edge e ∈ P where G′ = (V′, E′) is a subgraph induced from the vertices in the original shortest path.

In other words, Helen doesn’t want to take any detours to cities or towns that would otherwise not have been visited at any point in her original journey.

a) Design an algorithm to solve this problem that runs in O(|E|log |V|) time. Your result should be a list of |P| distances, one for each case where an edge e ∈ P was removed from the graph.

b) Prove the correctness of your algorithm.

c) Analyse the time complexity.