COMP9024 19T3
Week 6 Problem Set
Minimum Spanning Trees, Shortest Paths, Maximum Flows
Data Structures and Algorithms
Please note:
The contents of this weeks lecture and homework will not be covered by the midterm test.
Because of the midterm test on Monday, October 28, the deadline for this weeks programs will be on the day of the next lecture: Wednesday, October 30th.
1.Graph representations
a.Consider the following graphs, where bidirectional edges are depicted as twoway arrows rather than having two separate edges going in opposite directions: For each of the graphs show the concrete data structures if the graph was implemented via:
1.adjacency matrix representation assume full VV matrix
2.adjacency list representation if nondirectional, include both v,w and w,v
b.Consider the following map of streets in the Sydney CBD: Represent this as a directed graph, where intersections are vertices and the connecting streets are edges. Ensure that the directions on the edges correctly reflect any oneway streets this is a driving map, not a walking map. You only need to make a graph which includes the intersections marked with red letters. Some things that dont show on the map: Castlereagh St is oneway heading south and Curtin Pl is a little laneway that you cant drive down. For each of the following pairs of intersections, indicate whether there is a path from the first to the second. Show a simple path if there is one. If there is more than one simple path, show two different paths.
1.from intersection D on Margaret St to insersection L on Pitt St
2.from intersection J to the corner of Margaret St and York St intersection A
3.from intersection P on Castlereagh St to the corner of Margaret St and Wynyard Ln C
4.from the intersection of Castlereagh St and Hunter St M to intersection H at Wynyard Park
2.
3.Warshalls algorithm Apply Warshalls algorithm to compute the transitive closure of your graph from exercise 1b. Choose vertices in alphabetical order. Show the reachability matrix:
after the initialisation
after the 1st iteration vertex A of the outermost loop
after the 6th iteration vertex F of the outermost loop
at the end.
4.Interpret the values in each of these matrices: Which connections between vertices do the different matrices encode?
5.Minimum spanning trees
a.Show how Kruskals algorithm would construct the MST for the following graph: How many edges do you have to consider?
b.For a graph GV,E, what is the least number of edges that might need to be considered by Kruskals algorithm, and what is the most number of edges? Add one vertex and edge to the above graph to force Kruskals algorithm to the worst case.
c.Trace the execution of Prims algorithm to compute a minimum spanning tree on the following graph:Choose a random vertex to start with. Draw the resulting minimum spanning tree.
6.
7.Priority queue for Dijkstras algorithmAssume that a priority queue for Dijkstras algorithm is represented by a global variable PQueue of the following structure: define MAXNODES 1000
8.typedef struct
9. int itemMAXNODES; array of vertices currently in queue
10. int length;values currently stored in item array
11. PQueueT;
12.
13.static PQueueT PQueue;defines the Priority Queue Object
14.Further assume that vertices are stored in the item array in the priority queue in no particular order. Rather, the item array acts like a set, and the priority is determined by reference to a priority0..nV1 array. If the priority queue PQueue is initialised by:set up empty priority queue
15.void PQueueInit
16. PQueue.length0;
17.
18.and new elements are added as follows:insert vertex v into priority queue
19. no effect if v is already in the queue
20.void joinPQueueVertex v
21. assertPQueue.lengthMAXNODES; ensure queue ADO is not full
22. int i0;
23. while iPQueue.lengthPQueue.itemi ! v check if v already in queue
24.i;
25. if iPQueue.length v not foundadd it at the end
26.PQueue.itemPQueue.lengthv;
27.PQueue.length;
28.
29.
30.then give the implementation of the following functions in C for a priority queue ADO:remove the highest priority vertex from PQueue
31. remember: highest prioritylowest value priorityv
32. returns the removed vertex
33.Vertex leavePQueueint priority
34.
35.
36.
37. check if priority queue PQueue is empty
38.bool PQueueIsEmpty
39.
40.
41.Download the ADO header PQueue.h and the incomplete implementation file PQueue.c to get you started, along with the Weighted Graph ADT WGraph.h, WGraph.c from the lecture. Do not change the header files or the weighted graph ADT. Here is a simple client program to demonstrate the functionality of the priority queue:PQueue client COMP9024 19T3
42.include stdio.h
43.include PQueue.h
44.
45.int mainvoid
46. int distance2 90, 24 ;
47.
48. PQueueInit;
49. joinPQueue0;vertex 0 distance90 joins the queue
50. joinPQueue1;vertex 1 distance24 joins the queue
51.
52. while !PQueueIsEmpty
53.printfDequeueing d.n, leavePQueuedistance;
54.
55. return 0;
56.
57.The expected output is: .PQueueClient
58.Dequeuing 1.
59.Dequeuing 0.
60.We have created a script that can automatically test your program. To run this test you can execute the dryrun program that corresponds to this exercise. It expects to find a file named PQueue.c in the current directory that provides an implementation of a priority queue ADO with the four functions shown abovePQueueInit, JoinPQueue, LeavePQueue, PQueueIsEmpty. You can use dryrun as follows:9024 dryrun PQueue
61.
62.Dijkstras algorithm
a.Consider the following graph: What is the shortest path from vertex 0 to vertex 3? From vertex 0 to vertex 7? How did you determine these?
b.Trace the execution of Dijkstras algorithm on the graph from the previous question to compute the minimum distances from source node 0 to all other vertices. Show the values of vSet, dist and pred after each iteration.
c.Download and complete the incomplete implementation dijkstra.c of Dijkstras algorithm that uses your priority queue for exercise 4 and the Weighted Graph ADT WGraph.h, WGraph.c from the lecture. The program:
prompts the user for the number of nodes in a graph,
prompts the user for a source node,
builds a weighted undirected graph from user input adds every input edge in both directions,
uses the priority ADO to compute and output the distance and a shortest path from the source to every vertex of the graph needs to be implemented.
d.An example of the program executing is shown below. The input graph consists of a simple triangle along with a fourth, disconnected node. .dijkstra
e.Enter the number of vertices: 4
f.Enter the source node: 0
g.Enter an edge from: 0
h.Enter an edge to: 1
i.Enter the weight: 42
j.Enter an edge from: 0
k.Enter an edge to: 2
l.Enter the weight: 25
m.Enter an edge from: 1
n.Enter an edge to: 2
o.Enter the weight: 14
p.Enter an edge from: done
q.Done.
r.0: distance0, shortest path: 0
s.1: distance39, shortest path: 021
t.2: distance25, shortest path: 02
u.3: no path
v.Note that any nonnumeric data can be used to finish the interaction. Test your algorithm with the graph from exercise 5a. To test your program you can execute the dryrun program that corresponds to this exercise. It expects to find two programs in the current directory:
dijkstra.cyour solution to this exercise
PQueue.cyour solution to Exercise 4
w.You can use dryrun as follows:9024 dryrun dijkstra
x.Note: Please ensure that your output follows exactly the format shown above.
63.
64.Allpair shortest paths
a.In the graph from exercise 5a, what is the shortest path from vertex 3 to vertex 6? From vertex 6 to vertex 3? How did you determine these?
b.Trace the execution of Floyds algorithm on the graph from exercise 5a to compute the shortests paths between all pairs of vertices.
65.
66.Maximum flow
a.Identify a maximum flow from source0 to sink5 in the following network without applying the algorithm from the lecture: What approach did you use in finding the maxflow?
b.Show how Edmonds and Karps algorithm would construct a maximum flow from 0 to 5 for the above network. How many augmenting paths do you have to consider?
67.
68.Challenge Exercise Consider a machine with four wheels. Each wheel has the digits 09 printed clockwise on it. The current state of the machine is given by the four topmost digits abcd, e.g. 8056 in the picture below. Each wheel can be controlled by two buttons: Pressing the button labelled withturns the corresponding wheel clockwise one digit ahead, whereas presssingturns it anticlockwise one digit back. Write a Cprogram to determine the minimum number of button presses required to transform
a given initial state, abcd
to a given goal state, efgh
without passing through any of n0 given forbidden states, forbiddenw1x1y1z1,,wnxnynzn.
69.For example, the state 8056 as depicted can be transformed into 0056 in 2 steps if forbidden, whereas a minimum of 4 steps is needed for the same task if forbidden9056. Why? Use your program to compute the least number of button presses required to transform 8056 to 7012 if
a.there are no forbidden states
b.you are not permitted to pass through any state 70558055 i.e., 7055, 7056, , 8055 all are forbidden
c.you are not permitted to pass through any state 00000999 or 70558055
70.
Assessment
Group submissions will not be allowed. Your program must be entirely your own work. Plagiarism detection software will be used to compare all submissions pairwise.
Submit your solutions to Exercise 4 and 5 using the following give command:
give cs9024 week6 PQueue.c dijkstra.c
Make sure you spell the filenames correctly. You can run give multiple times. Only your last submission will be marked.
The deadline for submission is Wednesday, 30 October 11:00:00am.
Each program is worth 1 mark. Total marks2. Automarking will be run by the lecturer several days after the submission deadline using different test cases than dryrun does.
Hints:
Programs will not be manually marked.
It is important that the output of your program follows exactly the format shown above, otherwise automarking will result in 0 marks.
Ensure that your program compiles on a CSE machine with the standard options Wall Werror stdc11. Programs that do not compile will receive 0 marks.
dryrun and automarking also check the correct usage of dynamic memory allocation and pointers as well as the absence of memory leaks.
Do your own testing in addition to running dryrun.
Reviews
There are no reviews yet.