Exercises B#

Note

You must complete these exercises by Wednesday of W13.

Theoretical & conceptualINGInious coding & grading

Dijkstra Revisited#

We are interested in the implementation of Dijkstra’s algorithm on page 655.

  • What is the time complexity of this algorithm?

  • Rewrite this algorithm using only auxiliary collections from java.util. Specifically, replace IndexMinPQ with a standard collection from java.util.

String of Fairy Lights#

The INGI department has acquired a string of fairy lights for Christmas to decorate the Réaumur building. The lights form a graph with a lamp at each vertex. When turned on, an initial lamp is chosen at random, and every second thereafter, all lamps adjacent to currently lit lamps are switched on in turn. Implement the minTime method answering the following question: What is the minimum number of seconds required for the entire string of lights to be fully illuminated, given an optimal starting lamp?

Here is the method signature:

public int minTime(Graph G);

You may assume the Graph API as described in the textbook. Assume that the graph \(G\) is connected.

  • What is the time complexity of your algorithm?

Maximizing the Minimum Edge Weight#

Let \(G\) be an undirected graph with positive edge weights. Given a source vertex \(S\), we want to find a path to each vertex that maximizes the minimum edge weight on that path.

Graph example

For example, in this graph, \(S-F-B-A-C-D\) is such a path, with a bottleneck edge weight of 2.

Can you adapt an algorithm seen in class to find such paths to each vertex?

Hint: Consider the properties of the weights. How does this compare to shortest path algorithms (or MST algorithms)?

Mine Climbing#

A programming exercise on shortest paths with implicit graphs (exam 2018): MineClimbing.

Train Network#

A challenging shortest-path problem in a public transport network (exam 2019): Trains.

Word Transformation#

A string transformation problem modeled as a shortest-path problem on a graph: Words.

Galaxy Path#

Help humanity discover a new habitable galaxy by solving a hyperspace shortest-path problem (exam 2021): GalaxyPath.

Task Scheduler#

A topological sorting problem to verify whether a course programme complies with university prerequisite constraints (exam 2022): TaskScheduler.

Olympic Evacuation#

Help Olympic organizers plan efficient evacuation routes: Evacuation.

Wildfire Spread#

Help firefighters model the spread of a forest fire (exam 2022): Wildfire.