Computer Science 220S2C (2018) Assignment 3 (Graph Algorithms)

This assignment tests your understanding of graph optimization problems. To get marks for this assignment you need to submit three programs for the following tasks to http://www.cs.auckland.ac.nz/automated-marker twice. Note this marker runs on a linux box so no Microsoft speciﬁc code should be used; read the help/FAQ for more details. Each program will have an easy test case (2 marks) and harder test case (1 mark). Please use the suﬃx E of your program basename to denote ‘E’asy (test data) and H to denote ‘H’ arder (test data). For Task 1, name your source code mstE.ext and mstH.ext, where ext denotes one of {java, cpp, py, cs} to indicate a java/c++/python/c#(mono) program. For Task 2, name your source code named maxpathE.ext and maxpathH.ext, respectively. For Task 3, please submit source code named snakeE.ext and snakeH.ext, respectively. An excessive number of submissions (over 10) for a particular problem will accrue a 20% penalty per that problem if you eventually solve it.

For this warm-up task you are to implement any eﬃcient minimum spanning tree algorithm that takes a sequence of edge-weighted graphs and outputs the minimum cost weight of a spanning tree of each.

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 ﬁrst 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 0 1 3 1 0 2 3 2 0 4 0 2 7 0 2 0 5 1 7 5 0 3 0 1 3 0 6 0 1 0 4 0 0 1 0 3 0 3 0 0 3 0 0 0 2 4 0 0 0 2 0 0 3 0 2 0 1 0 0 2 0 1 0 0

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

A developer has designed a subdivision within a city such that all roads connect at intersections in a treelike design. This is to prevent all petrol-head hooligans from disturbing the residences by not having any road loops for races. Only the entering intersection is connected to the rest of the city. The developer is selling oﬀ land alongside roads between adjacent intersections. A real estate agent has produced a green book indicating the expected dollar proﬁt (positive, zero or negative) that can be obtained by purchasing the land alongside each road. Potential buyers want to maximize their proﬁt, but prefer to buy a contiguous stretch of land alongside a simple road chain that connects two intersections of the subdivision. Your task is to write a program to determine the maximum non-negative proﬁt that can be obtained this way. As an example, consider the following representation of a subdivision, where road labels represent expected proﬁts. In this scenario, the maximum non-negative proﬁt is 5, and can be obtained alongside the emphasized roads:

Input for this problem consists of a sequence of one or more scenarios, taken from the keyboard/stdin. Each scenario contains two or more lines. • The ﬁrst line contains an integer n, 1 ≤ n ≤ 500000, indicating the number of intersections, including the entrance intersection, implicitly labelled 0. • This is then followed by one or more lines, containing n−1 pairs of integers. All integers are separated by single spaces or newlines. The y-th intersection is deﬁned by the y-th pair of integers ‘x p’, where 1 ≤ y < n, 0 ≤ x < y, −1000 ≤ p ≤ 1000. This pair indicates that a road is added between y and a previously deﬁned intersection, x, with a green book proﬁt value given by p.

The input will be terminated by a line consisting of one zero (0). This line should not be processed. Some sample input scenarios follows.

5 0 -1 1 3 0 2 1 2 5 0 1 1 -3 0 -2 1 -2 5 0 -1 1 -3 0 -2 1 -2 10 0 -1 0 -1 0 0 1 3 1 4 2 4 2 2 3 3 3 3 0

Output will be a sequence of lines, one for each input scenario. Each line will contain an integer, indicating the maximum non-negative proﬁt sum, over all possible simple road chains connecting two intersections of the subdivision. Write zero (0) if no proﬁt can be obtained. The output for the previous sample input follows.

5

1

0

7

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) 6∈ 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 largest snake of a graph.

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 ﬁrst 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 0 3 1 5 1 4 0 2 1 3 4 2 4 0 2 3 0

Output will be just one integer per line sent to the console (e.g. System.out). 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

Assignment Writing Help

- Science Assignment Help
- Math Assignment Help
- Chemistry Assignment Help
- Physics Assignment Help
- Biology Assignment Help
- Psychology Assignment Help
- History Assignment Help
- Geography Assignment Help
- English Assignment Help
- Humanities Assignment Help
- Nursing Assignment Help
- Social Science Assignment Help
- Arts and Architecture Help
- Statistics Assignment Help
- Law Assignment Help
- Computational Mathematics Assignment Help

Engineering Assignment Services

- Programming Assignment Help
- Database Help
- Data Structure Assignment Help
- Operating Systems Assignment Help
- Computer Network Assignment Help
- UML Diagram Assignment Help
- IT Assignment Help
- Game Programming Help
- Computer Science Assignment Help
- Information Systems Assignment Help
- Chemical Engineering Assignment Help
- Civil Engineering Assignment Help
- Electrical, Electronics Help
- Mechanical Engineering Assignment Help
- Petroleum Engineering Assignment Help
- Biochemical and Biotechnology Help

Do My Assignment Help

- Accounting Assignment Help
- Finance Assignment Help
- Economics Assignment Help
- Marketing Assignment Help
- Human Resources Assignment Help
- Operations Management Assignment Help
- Strategy and Planning Help
- Project Management Help
- Case Studies Writing Help
- Political science
- Referencing Help
- Assignment Help Websites
- Online Assignment Help
- Do My Assignment
- Do My Homework

Write My Essay Services

- Essay Writing Help
- Business Essay Writing Help
- Assignment Writing Services
- Plagiarism Free Essay Writing
- Essay Editing Service
- Dissertation Writing Services
- Thesis Writing Help
- Custom Writing Help
- Write My Essay
- Write My Paper
- Paper Writing Service
- Academic help
- College Essay Writing
- Cheap Essay Writing