COSC 336 Assignment 10

COSC 336

Assignment 10
Instructions.
1. Due Dec 2.
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 2 files. The first file should be a .pdf file with the solutions
of Exercise 1 and Exercise 2, and also with a short description in English or in pseudocode
of the algorithm for the programming task and the results that you are required to report.
File 2 will contain the java codes of the program.
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
Exercise 1. Exercise 22.3 -2, page 610 in the textbook.
Notes:
• Read first the version of the DFS algorithm in the textbook on page 604 (it is also in Notes
10- graph traversals). This DFS traversal for directed graphs (called DFS with timing) assigns
two numbers to each vertex: d (which is the discovery time) and f (which is called the finishing
time). For the classification of edges you can use the information in Exercise 22.3.-5 (you don’t
have to solve this exercise, just use the given relations).
• Take into account the stipulations about processing vertices in alphabetical order (when you
have to choose between two vertices). Otherwise I cannot grade your solution. Draw the graph
(do it by hand if you have a hard time using tikz for this) and the d and f numbers next to
each vertex. For the classification of all edges, make a table with two columns in which in the
first column you write the edge and in the second column you indicate the type of the edge (tree,
forward, back, or cross).
Exercise 2. Describe an algorithm that computes the shortest path from a given node s
(called the source) to all the other nodes in an undirected graph G in which the edges can have
the weights 1 or 2. Your algorithm should have runtime O(n + m). Hint: you can use an idea
that I said is bad in Notes 11, but which actually works fine for this set of weights. Describe your
algorithm in plain English in a clear and concise way.
Programming Task.
In a weighted directed graph G = (V, E), the eccentricity of a vertex v ∈ V is defined by
ecc(v) = max{δ(v, u) | u ∈ V },
where δ(v, u) is the weight of a shortest path from v to u (in other words ecc(v) is the smallest
distance to the vertex u that is the furthest from v).
Write a Java program that computes the eccentricity of every vertex. Describe the method
you are using.
The graph is given in a file that has two lines. The first line has n (the number of nodes, which
are labeled 0, 1, . . . , n − 1) and the second line has a list of n
2 numbers w0, w1, . . . , wn2−1
, where
wk is the weight of the edge (i, j) for i = k/n and j = k (mod n) (if wk = −1, then there is no
edge from i to j). Your program should read the file, build the adjacency matrix representation
of G, and then compute with your method the eccentricities of all vertices.
Test your program on the graphs given in the files indicated and report the eccentricities.
input-10.1
input-10.2
2