# The University of Adelaide COMP SCI 2201 & 7201

## Algorithm and Data Structure Analysis

· 案例展示

COMP SCI 2201 & 7201 Algorithm and Data Structure Analysis Semester 2, 2020
Assignment 2: Graphs (worth 10% of the course)
Due date: 23:59, 18 September 2020
General Instructions
You have to do this assignment as a team of two students.
Submissions have to include coversheet including names, student ids, and your
a single pdf on MyUni by the deadline. Only 1 submission per group.
Exercise 1 (7+13 points) Proof Exercises
1. Prove the following by induction. Suppose G is a simple, undirected graph. If G is
a tree, then G contains exactly n - 1 edges.
2. A Eulerian cycle of a given connected undirected graph G=(V,E) is a cycle that
uses each edge e 2 E exactly once. A graph contains an Eulerian cycle if and only
if the degree of each vertex is even. Prove that this is the case. (Note: since this
is an if and only if statement, you need to prove both directions: i.e., prove that
a graph contains an Eulerian cycle if the degree of each vertex is even, and prove
that if a graph contains an Eulerian cycle, then the degree of each vertex is even.)
Exercise 2 (10+6+4 points) Single-source-shortest path problem in acyclic graphs
We consider the single-source-shortest path problem of a given directed graph G = (V; E)
with non-negative edge weights and a source node s. Furthermore, we assume that the
given graph G is acyclic, i. e. it does not contain a cycle.
• Give an algorithm (in pseudo-code) that solves the single-source-shortest path problem for a given acyclic graph in time O(m + n).
• Prove the correctness of your algorithm.
• Show that your algorithm runs in time O(m + n) by analysing its runtime.
1
COMP SCI 2201 & 7201 Algorithm and Data Structure Analysis Semester 2, 2020
Exercise 3 Dijkstra’s algorithm (20 points)
Consider the following graph:

Solve the single-source-shortest path problem for the start node v1 using Dijkstra’s algorithm. List for each iteration which nodes become scanned and which edges are relaxed.
Exercise 4 Kruskal’s Algorithm (20 points)
Compute a minimum spanning for the following graph using Kruskal’s algorithm. Show
the status of your partial minimum spanning tree after each edge insertion and indicate
for each edge whether it is included in the minimum spanning tree.
4
COMP SCI 2201 & 7201 Algorithm and Data Structure Analysis Semester 2, 2020
Exercise 5 AVL Trees (16+2+2 points) (Postgraduate students only)
• Draw a sequence of diagrams showing the insertion of the values:
[8,5,4,7,9,6,10]
into an empty AVL tree.
You must:
{ Show the resulting tree immediately after each insertion step (that is before
any balancing has taken place).
{ Indicate the node(s) at which each rotation is performed.
{ Where there is a double rotation, show the tree after each single rotation.
{ Show the resulting tree after balancing operation(s).
• Give the best possible upper bound on the worst-case height of an AVL-tree consisting of n elements.
• Give a best possible lower bound on the height of a binary search tree consisting of
n elements.
3