CSE 431/531: Algorithm Analysis and Design Spring 2020
Programming Homework
Instructor: Shi Li Deadline: May 8
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 subse-
quence 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, an O(n2 +m)-time algorithm is sufficient to pass
all test cases.
Input You need to read the input from the console. In the first line of the input, 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 ≤ 1000 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 console. The first line of the output 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