Description
Question 1. (10 points) Exercise 2 from Chapter 3, page 107 of the textbook. You may assume
that the input graph is given to you as an adjacency list.
Question 2. (10 points) Exercise 7 from Chapter 3, pages 108-109 of the textbook.
Question 3. (10 points) Consider the pseudocode for BFS given in the slides of Lecture 6. How
would the running time of this algorithm change if the input graph is represented as an adjacency
matrix? Justify your answer.
Question 4. (10 points) Suppose we have three containers whose sizes are 10, 7, and 4 gallons,
respectively. The 7-gallon and 4-gallon containers start out full of water, while the 10-gallon
container starts out empty. We are allowed one type of operation: pouring the contents of one
container into another, stopping only when the source container is empty or the destination container is full. We would like to figure out if there is a sequence of such operations that leaves
exactly 2 gallons in the 7- or 4-gallon container. Show how to model this problem as a graph
problem: give a precise definition of the graph involved and state the specific question about this
graph that needs to be answered to solve the original problem. Justify your answer. (Hint: You
may think of possible container configurations as vertices).
Question 5. (10 points) Exercise 12 from Chapter 3, page 112 of the textbook. (Hint: you may
use vertices to represent dates, i.e., (unknown) birth and death dates for each person.)