## Description

CSE 431/531: Algorithm Analysis and Design

Programming Homework

Problem 1 You need to implement the algorithm for counting inversions. You need to read from the

standard input (i.e, the terminal) and output to the standard output (i.e, the screen).

• Input format: The first line of the input contains one positive integers n, 1 ≤ n ≤ 106

. The next n

lines contain the n integers A[1], A[2], · · · , A[n]; every integer is between 0 and 108

.

• Output format: Just output 1 line, which is total number of inversions.

Example Input:

6

7

3

20

16

5

8

Example Output:

7

The pairs are (7, 3),(7, 5),(20, 16),(20, 5),(20, 8),

(16, 5),(16, 8).

Problem 2 You need to implement the dynamic programming algorithm for the longest common subsequence problem.

Input You need to read the input from the console. It contains two lines, each containing one string. You

can assume each string only contains upper and lower case letters and numbers; the length of each string is

at most 1000.

Output You need to output to the console. The first line of the file is an integer indicating the length

of the longest common subsequence between the two strings. The second line contains the longest common

subsequence (which may not be unique).

Example Input:

bacdca

adbcda

Example Output:

4

adca

Problem 3 You need to implement either the Kruskal’s algorithm or the Prim’s algorithm for the minimum

spanning tree problem. If you are using Prim’s algorithm, you can use the priority queue data structures

provided in standard libraries in your language. If you are using Kruskal’s algorithm, you need to implement

the Union-and-find data structure by yourself.

Input you need to read the input graph from the file “input.txt”. In the first line of the file, we have two

positive integers n and m. n is the number of vertices in the graph and m is the number of edges in the

graph. The vertices are indexed from 1 to n. You can assume that 1 ≤ n ≤ 10000 and 1 ≤ m ≤ 100000.

In the next m lines, each line contains 3 integers: u, v and w, with 1 ≤ u < v ≤ n and 1 ≤ w ≤ 106

. This

indicates that there is an edge (u, v) of weight w. You can also assume that the graph is connected and there

are no parallel edges.

1

Output You need to output to the file “output.txt”. The first line of the file is an integer indicating the

total weight of the minimum spanning tree. From line 2 to line n, you need to output the n-1 edges in the

minimum spanning tree. Each line contains 2 integers between 1 and n, indicating the two end-points of an

edge.

Example Input:

9 14

1 2 5

1 8 12

2 3 8

2 8 11

3 4 13

3 6 4

3 9 2

4 5 9

4 6 14

5 6 10

6 7 3

7 8 1

7 9 6

8 9 7

Example Output:

42

1 2

2 3

3 6

3 9

4 5

5 6

6 7

7 8

2