CS141 Homework 5
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
CS141 Homework 5
Problem 1: Pouring water. We have three containers whose sizes are 10 pints, 7 pints, and 4 pints, respectively. The 7-pint and 4-pint containers start out full of water, but the 10-pint container is initially 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 want to know if there is a sequence of pourings that leaves exactly 2 pints in the 7- or 4-pint container.
(a) Model this 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.
(b) What algorithm should be applied to solve the problem?
(c) Find the answer by applying the algorithm.
Problem 2: If there is ever a decision between multiple neighbor nodes in the BFS or DFS algorithms, assume we always choose the letter in alphabetical order.
a) Consider the following adjacency matrix.
|
|
A |
B |
C |
D |
E |
F |
G |
H |
I |
|
A |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
|
B |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
|
C |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
|
D |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
|
E |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
|
F |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
|
G |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
|
H |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
|
I |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
a.1) Draw the graph that is represented by the matrix.
a.2) In what order will the nodes be visited using Breadth First Search? In what order will the nodes be visited using Depth First Search?
b)If you have the 0/1 adjacency matrix of a graph, and you take the matrix to the Nth power, then the (i, j)th entry of the result tells how many paths of length N there are from vertex i to vertex j (here the length is measured in number of edges traversed). For example, in a) according to the adjacency matrix there is a path of length 1 edge between vertices A and B .
Let G = (V, E) be an undirected graph. A triangle in G is a cycle consisting of exactly three vertices (or, equivalently, three edges). Suppose that G is represented as an adjacency matrix. Give an algorithm to determine whether G contains any triangle in O(nlog2 7 ) worst-case time.
c) Using matrix multiplications, find all the triangles in the graph, represented by the following adjacency matrix.
Problem 3: You are given a directed graph G = (V, E), where V = {1, . . . , n}, i.e., the vertices are integers
|
|
A |
B |
C |
D |
E |
F |
G |
|
A |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
|
B |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
|
C |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
|
D |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
|
E |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
|
F |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
|
G |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
in the range 1 to n. For every vertex i we would like to compute the value m(i) defined as follows: m(i) is the smallest j such that vertex j is reachable from vertex i. (As a convention, we assume that i is reachable from i.) Show that the values m(1), . . . , m(n) can be computed in O(lV l + lEl) time.
Problem 4: You are given a set of cities, along with the pattern of highways between them, in the form of an undirected graph G = (V, E). Each stretch of highway e e E connects two of the cities, and you know its length in miles le . You want to get from city s to city t. There’s one problem: your car can only hold enough gas to cover L miles. There are gas stations in each city, but not between cities. Therefore, you can only take a route if every one of its edges has length le < L.
a) Given the limitation on your car’s fuel tank capacity, show how to determine in linear time whether there is a feasible route from s to t.
b) You are now planning to buy a new car, and you want to know the minimum fuel tank capacity that is needed to travel from s to t. Give an O((l V l + l E l) log l V l) algorithm to determine this.
Problem 5: (Extra credit) Consider the following adjacency matrix.
|
|
A |
B |
C |
D |
E |
|
A |
0 |
5 |
6 |
3 |
-4 |
|
B |
∞ |
0 |
∞ |
1 |
7 |
|
C |
∞ |
4 |
0 |
∞ |
∞ |
|
D |
∞ |
∞ |
-5 |
0 |
∞ |
|
E |
∞ |
∞ |
3 |
6 |
0 |
a) Draw the graph that is represented by the matrix.
b) Apply Bellman-Ford’s algorithm to the graph to find shortest paths from vertex A to all the other vertices. Show every iteration.
c) Does this graph have negative cycles?
2022-07-18