This programming assignment is to help you practice with graph data structure and graph search algorithms.
Problem 1. Diehard. The following is a classical puzzle made famous by its inclusion in the movie series DieHard. An instance of the problem is as follows. You are given 3 containers of sizes 10 litres, 7 litres and 4 litres respectively. You are also given an initial condition, for example, say that the 7 and 4 litre containers start out full of water but the 10 litre container is initially empty. You are allowed only two types of operations: (a) pour the contents of one container into another, stopping only when the source container is empty or the destination container is full, or (b) pour out the contents of any container completely to the ground. The problem is to give a sequence of pourings that leaves exactly 2 liters in the 7 liter or 10 liter.
The input gives three numbers L1; L2 and L3, as the capacities of the 3 containers and S1; S2 and S3 to be the initial volumes of water in each of the three containers. You are given a set of possible desirable states, for example, in the above instance, the desirable states are S2 = 2 or S3 = 2. Formulate the problem as a graph theoretic problem. For each instance, that is, an initial state and the set of nal states, give a sequence of steps that realizes any one of the nal states or states that no such sequence is possible.
Problem 2. Given an undirected graph G in adjacency list form with n vertices numbered 1 to n. You are also given an edge e of the graph. You have to answer the following question: Is it a bridge or not. A bridge is an edge which if removed disconnects the graph. Equivalently, an edge is not a bridge i it lies on some cycle. So the problem is equivalently: does e lie on a cycle in G.
1
