cs 220 Assignment 4

COMPSCI 220 
Assignment 4 
There are 4 problems listed below. To get full marks for this assignment you need to complete all of them!
The marks for this assignment are worth 7.5% of your course grade. The due date is firm in that there are
no penalty options available for late submissions (except zero marks).
Please submit a single PDF file with your solutions to Questions 1-3 to Canvas. A (scanned) handwritten
report is fine as long as it is neat. Show all working; if you do not show your work marks will be reduced.
Your answer to Question 4 must be submitted via the automated marker system at
https://www.automarker.cs.auckland.ac.nz

1. A graph-theoretic problem.
The computer science department plans to schedule the classes Programming (P), Data Science (D),
Artificial Intelligence (A), Machine Learning (M), Complexity (C) and Vision (V) in the following
semester. Ten students (see below) have indicated the courses that they plan to take. What is the
minimum number of time periods per week that are needed to offer these courses so that every two
classes having a student in common are taught at different times during a day. Of course, two classes
having no student in common can be taught at the same time. For simplicity, you may assume that
each course consists of a single 50 min lecture per week.
Anden: A, D Brynn: V, A, C Chase: V, C, A Denise: C, A, M
Everett: M, A, D Francoise: C, M Greg: P, V, A Harper: A, P, D
Irene: M, D, A Jenny: P, D
To get full marks, your answer to this question should be clear and detailed. In particular, you are
asked to explain which graph-theoretic concept can be used to model the above situation, apply this
concept to the situation, and explain how the resulting graph can be exploited to answer the question.
(5 marks)
2. Connectivity.
Let D be a digraph, and let G be a graph. Recall that the underlying graph of D is obtained by
removing all directions from the arcs of D and replacing any resulting pair of parallel edges by a single
edge. Moreover, an edge-cut of G is a set S of edges of G such that G−S is disconnected, where G−S
denotes the graph obtained from G by deleting all edges in S.
Now, let D be a digraph with at least two nodes. Prove that D is strongly connected if and only if for
every edge-cut S of the underlying graph G of D that separates V (G − S) into exactly two sets A
and B, there is an arc in D directed from a node in A to a node in B and an arc in D directed from
a node in B to a node in A.
Be as detailed and precise as possible in writing up your proof!
(5 marks)
3. A property of Dijkstra’s algorithm?
Prove or disprove the following claim for a weighted graph (G, c) with G = (V, E), V = {v0, v1, . . . , vn−1}
and E = {e1, e2, . . . , em} such that c(e1) < c(ei) for all i ∈ {2, 3, . . . , m}. If Dijkstra’s algorithm is
applied to G and the shortest path from v0 to vi
is computed for each i ∈ {1, 2, . . . , n − 1}, then there
exists a node vj ∈ V \ {v0} such that e1 is an edge on the shortest path from from v0 to vj .
(3 marks)
4. Longest paths.
Write an algorithm that finds the length of a longest path starting from node 0 in a DAG.
Input format. The input consists of a sequence of one or more DAGs. Each DAG D is represented
by an adjacency list. The first line is an integer n that indicates the order of D. This is followed by n
white space separated lists of adjacencies for nodes labeled 0 to n − 1. The input is terminated by a
line consisting of a single zero. This line should not be processed. Each input DAG may contain up
to 5000 nodes and up to 10000 arcs. An example input that contains two DAGs is shown next.
Computer Science 220 S1 (2012)
Assignment 4 (Graph Algorithms)
Due dates: May 30 and June 2 (2012)
Please read the entire assignment before starting.
Goals
In this assignment we want you to write simple graph algorithms for directed acyclic graphs (DAGs). There are
three algorithmic tasks. Each task should be coded up in a separate program.
1. Determine the number of components.
2. Find the length of the longest path starting from node 0.
3. Count the number1 of di↵erent paths from node 0 to node n  1.
Input Format
Input for this problem consists of a sequence of one or more acyclic digraphs (DAGs) taken from the keyboard
(e.g. System.in). Each digraph is represented by an adjacency list. The first line is an integer n indicating
the order of the digraph. This is followed by n white space separated lists of adjacencies for nodes labeled 0 to
n1. The input will be terminated by a line consisting of one zero (0). This line should not be processed. Two
sample input digraphs are listed below.
6
123
2
3 5
4
5
6
3 5
2
4
4
0
0 1
3 2
4
0 1
3 2
5 4
DAG 1 DAG 2
5
1You may assume this integer count will fit into a ‘long’ data type of 64 bits.
Output format. The output is a sequence of lines, one for each input DAG. Each line contains a
single integer indicating the length of the longest path starting from vertex 0.
Submit your source code to the automated marker https://www.automarker.cs.auckland.ac.nz.
A set of test cases is provided on Canvas (the two text files test-cases.in and test-cases.out) but you
are strongly encouraged to write your own (boundary) test cases and test your code before submitting
to the automated marker. As in previous assignments, note that the automated marker reads input
from stdin. Your program should be efficient, i.e. it must complete with the correct answer within 10
seconds for any feasible type of input! You get 3 marks for passing the first (small) test case, 2 marks
for passing the second (medium size) test case, and 2 marks for passing the third (large size) test case.
For this assignment, no marks will be awarded or subtracted for adding or omitting comments.
• Supported languages are Java, C,C++, PyPy, Python, Go, C#, Rust, F#, Javascript.
• A sample input and output file for the question is available from Canvas.
• You have an unlimited number of submissions.
• If you submit more than 10 times, there is a penalty of 25%.
• If you submit more than 20 times, there is a penalty of 50%.
(7 marks)