COSC 336 Assignment 9

COSC 336

Assignment 9
Instructions.
1. Due Nov 23.
2. This is a team assignment. Work in teams of 3-4 students. Submit one assignment
per team, with the names of all students making the team.
3. Your programs must be written in Java.
4. Write your programs neatly - imagine yourself grading your program and see if it is
easy to read and understand. At the very beginning present your algorithm in plain
English or in pseudo-code (or both). Comment your programs reasonably: there is
no need to comment lines like ”i++” but do include brief comments describing the
main purpose of a specific block of lines.
5. You will submit on Blackboard 3 files. The first file should be a .pdf file with the
short descriptions in English or in pseudocode of the algorithms for the programming
tasks you are required to do and the results that you are required to report. Files 2
and 3 will contain the java codes of the program for task1 and the program for task
2.
For editing the above document with Latex, see the template posted on the course
website.
assignment-template.tex and
assignment-template.pdf
To append in the latex file a pdf file, place it in the same folder and then include them
in the latex file with
\includepdf[pages=-,pagecommand={},width=\textwidth]{file.pdf}
To append in the latex file a .jpg file (for a photo), use
\includegraphics[width=\linewidth]{file.jpg}
1
Programming Task 1. This is related to Exercise 22.1-5, page 593 in the textbook.
Part (a). Write a program that computes the adjacency list of the directed graph G2
(defined in the exercise; this is called the square of G), given the adjacency list of the
directed graph G. The graph G2 has the same nodes as G, and (u, v) is an edge of G2
if
and only if there is path of length 1 or 2 from u to v.
For example if G is the graph on the left, then G2
is the graph on the right.
0 1
2
0 1
2
For the adjacency list, you must use the Java class Adj List Graph given in the file
Adj List Graph.java (see Test Adj.java for a very simple example of using this class).
You will read the input graph G from a file which contains 2 lines. The first line contains
the number n of vertices of the graph. The second line contains a sequence of n
2 bits (values
0 and 1). The n nodes are labeled 0, 1, . . . , n − 1. If the i × n + j-th bit in the sequence is
1, then there is an edge from node i to node j, and if the i × n + j-th bit in the sequence is
0, then there is no edge from node i to node j.
The program has to create the adjacency list of the graph G2 and then use the printGraph
function of the class Adj List Graph to print the edges of G2
.
Run your program on two data sets from the files
input-9.1
input-9.2
Describe briefly your program and report the results in the .pdf file.
Programming Task 2.
Write the program that modifies Breadth First Search (see for example the basic version
of BFS in Notes 10) in such a way that given an undirected connected graph G, and a
starting node s, it will print for every node v the length of the shortest path from s to v
and also the number of shortest paths from s to v. Thus, you’ll have two arrays dist and
npath, and for each vertex v, at the end of the program, dist[v] will be equal to the length
of a shortest path from s to v, and npath[v] will be equal to the number of shortest paths
from s to v.
(For example, if G1 is the first graph below, the length of a shortest path from 1 to 7 is
3, and there are three shortest paths from 1 to 7, namely
1 - 2 - 5 - 7,
1 - 3 - 5 - 7 and
1 - 4 - 6 -7).
So, dist[7] = 3, and npath[7] = 3.
Test your program on the graphs G1 and G2 (see the figures) using 1 as the starting node
and report the results you have obtained for these two graphs. You must use the adjacency
list representation of a graph. As in the other programming task, for the adjacency list, you
must use the Java class Adj List Graph given in the file Adj List Graph.java (see Test Adj.java
for a very simple example of using this class).
2
graph G1
1
2 3 4
5 6
7
graph G2:
1
2 3 4 5 6
7
3