COMPSCI 320 - Applied Algorithmics - Assignment 1: Graph Algorithms
Computer Science 320S2C (2022)
Assignment 1 (Graph Algorithms) Due date August 1, 2022, 11.59pm
Introduction
This warm-up assignment tests your pre-requisite skills from CS220 on graph optimization problems. You need to submit two programs for the following tasks to https://www.automarker.cs.auckland.ac.nz/ to get marks for this assignment. Most common programming languages will be available to do the assignment. Note this marker runs on a linux box so no Microsoft specific code should be used; read the help/FAQ for more details. Input is from keyboard/stdin and output is to console/stdout.
Task 1 is worth 2 marks and you can implement any standard solution. Tasks 2 is worth 3 marks, where some algorithm design thinking is required. Both problems will contain easy and harder input cases on the automarker.
An excessive number of submissions (over 10) for a particular problem will accrue a 20% penalty per that problem if you eventually solve it.
Task 1: Minimum Spanning Trees
For this warm-up task you are to implement any efficient minimum spanning tree algorithm that takes a sequence of edge-weighted graphs and outputs the minimum cost weight of a spanning tree of each.
Input Format
For this assignment we use adjacency matrices with positive integer weights. Here a zero entry at row i and column j indicates that no edge ij exists in the graph. The first line consists of an integer n ≤ 1000 denoting the order of the graph. This is then followed by n lines of n white-space separated integers denoting edge weights. The sequence of graphs is terminated by a value n = 0, which is not processed.
3
013
102
320
4
0270
2051
7503
0130
6
010400
103030
030002
400020
030201
002010
0
Output Format
Output should be one line for each input graph indicating the minimum cost weighted tree. The sample output for the previous input cases is as follows.
3 6 9
Task 2: Snakes in a Graph
For a graph G = (V,E), a snake (also called an induced path) is a path v1,v2,...,vk such that for all j −i > 1 (vi,vj) ̸∈ E. That is, it is a sequence of vertices in G such that each two adjacent vertices in the sequence are connected by an edge in G, and each two nonadjacent vertices in the sequence are not connected by any edge in G.
For this task, our goal is to determine the longest snake of a graph.
Input Format
Input for this problem consist of a sequence of one or more (undirected) graphs taken from the keyboard. Each graph is represented by an adjacency list. The first line is an integer n indicating the order of the graph. This is followed by n white space separated lists of adjacencies for nodes labeled 0 to n − 1. The input will be terminated by a line consisting of one zero (0). This line should not be processed. Two sample input graphs are listed below. The easy (harder) test cases are graphs of order at most 10 (50).
4
1
03
1
5
14
02
134
24
023
0
Output Format
Output will be just one integer per line. For the above, input we would output the following two integers denoting the longest snake of the two graphs. Recall that the length of a path is the number of edges.
2 3
