Algorithm Analysis and Design Homework

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