Exercises A#

Note

You must complete these exercises by Wednesday of W12.

Exercise 6.1.1#

Give several data structures that can be used to represent an undirected graph \(G\) with \(n\) vertices (nodes) and \(m\) edges.

What are the time complexities of the elementary operations Iterable<Integer> adj(int v) and addEdge(int v, int w) for each?

Exercise 6.1.2#

A graph is bipartite if its vertices can be partitioned into two disjoint sets such that no edge connects two vertices of the same set.

Propose an algorithm to test whether a graph is bipartite and, if so, find such a partition. What is the time complexity of your algorithm? Hint: Use DFS.

Exercise 6.1.3#

Prove that every connected graph has a vertex whose removal (along with its incident edges) does not disconnect the graph. Write an algorithm that finds such a vertex. Hint: Use DFS and vertex marking.

Exercise 6.1.4 (INGInious: Maze)#

Consider an unweighted, undirected graph \(G\) whose edges represent valid moves for a robot in a maze between positions (nodes). Given a starting position and a destination node, implement a method to find a path to the exit that minimizes the number of moves: Maze. What is the time complexity of your method? Does it depend on the graph representation (for example, adjacency lists vs. adjacency matrix)?

Exercise 6.1.5#

The EPL course syllabus lists prerequisites for each course. You want to verify that all courses can be taken, i.e., that there is no circular dependency between courses.

What algorithm do you propose to perform this check? What is the time complexity of your method?

Exercise 6.1.6#

Develop (write the code for) a topological sorting algorithm for a directed graph that maintains an array of size \(V\) where each entry corresponds to the in-degree of a vertex. Your algorithm should also maintain a queue of sources (vertices with an in-degree of 0). Initialize these two structures in a single pass over all edges. Then, repeat the following steps until the source queue is empty:

  • Remove a source from the queue and add it to the topological order.

  • Decrement the in-degree of each neighbor of that vertex.

  • If the in-degree of a neighbor becomes 0, insert it into the source queue.

How can you detect whether the topological sort is unique? What is the time complexity of your algorithm?

Exercise 6.1.7#

Let \(G = (V,E)\) be an edge-weighted undirected graph for which a minimum spanning tree (MST) has already been computed. Suppose \(k\) edges are removed from this MST. Write a method to reconstruct an MST from the remaining \(|V|-1-k\) edges. The final MST does not need to be identical to the original one, but it must contain the \(|V|-1-k\) preserved edges.

On what fundamental property (or properties) of MSTs is your algorithm based? What is the time complexity of your method?

Exercise 6.1.8#

Let \(G = (V,E)\) be an edge-weighted undirected graph for which an MST has already been computed. Suppose an edge \(e \in E\) with weight \(w\) is not part of this MST. How can you compute a new MST that is constrained to include \(e\) by adapting the original MST? Describe your algorithm. What is the time complexity? Hint: Use DFS on the original MST.

Exercise 6.1.9#

Could java.util.PriorityQueue be used to efficiently implement Dijkstra’s algorithm? If not, why not? What would the time complexity be if you used this priority queue?

Exercise 6.1.10#

Explain why Dijkstra’s algorithm (DijkstraSP) does not support edges with negative weights. Would the computed distances be incorrect, or would the time complexity guarantee no longer hold? Provide an example graph illustrating the problem.

Exercise 6.1.11#

Let \(G\) be a directed graph with potentially negative edge weights, but without any negative cycles. Suppose we want to find the shortest path between a vertex \(u\) and a vertex \(v\). We only have access to an implementation of Dijkstra’s algorithm that does not support negative weights. A proposed heuristic is to add a constant to all edge weights equal to the absolute value of the most negative weight (making all weights non-negative), and then run Dijkstra’s algorithm on this modified graph. Is this method valid? If so, prove it. If not, provide a counterexample.

Exercise 6.1.12#

Let \(G\) be a directed graph with positive edge weights. We want to find the longest path between vertex \(u\) and vertex \(v\). Suppose we have an implementation of the Bellman-Ford algorithm (which supports negative weights). Can we simply negate all edge weights and compute the shortest path using Bellman-Ford? Is this method valid? If not, can you propose an algorithm to find the longest simple path? Does your method apply to all graphs? If not, what specific class of graphs can it handle?

Exercise 6.1.13 (INGInious)#

Implement a Digraph Data Structure

Exercise 6.1.14 (INGInious)#

Implement an algorithm for finding a path (its length does not matter) between a source node and a destination using Depth First Search

Exercise 6.1.15 (INGInious)#

Implement the computation of the number of connected components in a Graph: ConnectedComponents

Exercise 6.1.16 (INGInious)#

A programming exercise on finding which contacts to prohibit in a network to satisfy Belgian COVID-19 bubble regulations: Covid bubbles

Exercise 6.1.17 (INGInious)#

A programming exercise on BFS to find the shortest path from multiple possible sources to a destination node: BFS multiple sources

Exercise 6.1.18 (INGInious)#

A programming exercise on shortest path in an implicit graph: Global Warming Path

Exercise 6.1.19 (INGInious)#

Revisit the computation of the number of islands, this time using DFS rather than union-find: Global Warming Island