COMP9024 19T3 Week 6 Problem Set Data Structures and Algorithms
Minimum Spanning Trees, Shortest Paths, Maximum Flows
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. 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.
Interpret the values in each of these matrices: Which connections between vertices do the different matrices encode?
3. 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.
4. Priority queue for Dijkstras algorithm
Assume that a priority queue for Dijkstras algorithm is represented by a global variable PQueue of the following structure:
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:
and new elements are added as follows:
insert vertex v into priority queue
no effect if v is already in the queue
void joinPQueueVertex v
assertPQueue.lengthMAXNODES;
int i0;
while iPQueue.lengthPQueue.itemi ! v check if v already in queue
set up empty priority queue
void PQueueInit
PQueue.length0;
i;
if iPQueue.length
PQueue.itemPQueue.lengthv;
PQueue.length;
v not foundadd it at the end
ensure queue ADO is not full
then give the implementation of the following functions in C for a priority queue ADO:
remove the highest priority vertex from PQueue
remember: highest prioritylowest value priorityv
returns the removed vertex
Vertex leavePQueueint priority
check if priority queue PQueue is empty
bool PQueueIsEmpty
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
include stdio.h
include PQueue.h
int mainvoid
int distance2 90, 24 ;
PQueueInit;
joinPQueue0;vertex 0 distance90 joins the queue
joinPQueue1;vertex 1 distance24 joins the queue
while !PQueueIsEmpty
printfDequeueing d.n, leavePQueuedistance;
return 0;
The expected output is:
define MAXNODES 1000
typedef struct
int itemMAXNODES; array of vertices currently in queue
int length;values currently stored in item array
PQueueT;
static PQueueT PQueue;defines the Priority Queue Object
prompt
.PQueueClient
Dequeuing 1.
Dequeuing 0.
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:
5. 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.
An example of the program executing is shown below. The input graph consists of a simple triangle along with a fourth, disconnected node.
Enter the number of vertices: 4 Enter the source node: 0
Enter an edge from: 0
Enter an edge to: 1
Enter the weight: 42
Enter an edge from: 0
Enter an edge to: 2
Enter the weight: 25
Enter an edge from: 1
Enter an edge to: 2
Enter the weight: 14
Enter an edge from: done
Done.
0: distance0, shortest path: 0
1: distance39, shortest path: 021
prompt
9024 dryrun PQueue
prompt
.dijkstra
2: distance25, shortest path: 02
3: no path
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
You can use dryrun as follows:
Note: Please ensure that your output follows exactly the format shown above.
6. 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.
7. 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?
8. 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.
prompt
9024 dryrun dijkstra
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.
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
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:
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:
prompt
give cs9024 week6 PQueue.c dijkstra.c
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.