# 7.25. Exercises¶

1. Draw the graph corresponding to the following adjacency matrix.

1. Draw the graph corresponding to the following list of edges.

from

to

cost

1

2

10

1

3

15

1

6

5

2

3

7

3

4

7

3

6

10

4

5

7

6

4

5

5

6

13

2. Ignoring the weights, perform a breadth-first search on the graph drawn for question 1 or 2.

1. What is the Big-O running time of the build_graph function?

1. Derive the Big-O running time for the topological sort algorithm.

1. Derive the Big-O running time for the strongly connected components algorithm.

2. Show each step in applying Dijkstra’s algorithm to the graph drawn for question 1 or 2.

3. Using Prim’s algorithm, find the minimum weight spanning tree for the graph drawn for question 1 or 2.

1. Draw a dependency graph illustrating the steps needed to send an email. Perform a topological sort on your graph.

2. Express branching factor $$k$$ as a function of the board size $$n$$.

3. Derive an expression for the base of the exponent used in expressing the

running time of the knights tour.

1. Explain why the general DFS algorithm is not suitable for solving

the knight’s tour problem.

1. What is the Big-O running time for Prim’s minimum

spanning tree algorithm?

2. Modify the depth-first search function to produce a topological sort.

3. Modify the depth-first search to produce strongly connected components.

4. Write the transpose method for the Graph class.

5. Using breadth-first search write an algorithm that can determine the shortest path from each vertex to every other vertex. This is called the “all pairs shortest path problem.”

6. Using breadth-first search revise the maze program from the Chapter 4 (Recursion) to find the shortest path out of a maze.

7. Write a program to solve the following problem: you have two jugs, a 4-gallon and a 3-gallon. Neither of the jugs has any markings. There is a pump that can be used to fill the jugs with water. How can you get exactly two gallons of water in the 4-gallon jug?

8. Generalize the problem above so that the parameters to your solution include the size of each jug and the final amount of water to be left in the larger jug.

9. Write a program that solves the following problem: three missionaries and three cannibals come to a river and find a boat that holds two people. Everyone must get across the river to continue on the journey. However, if the cannibals ever outnumber the missionaries on either bank, the missionaries will be eaten. Find a series of crossings that will get everyone safely to the other side of the river.