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

workshop group such that submissions can get marked. Please upload your solutions as

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

Add paragraph text here.