CS575 Design and Analysis of Algorithms
Fall 2023
Programming Assignment 3
Assigned: October 28, 2023
Due: Midnight Friday, November 10, 2023
1. [45%] Implement the longest common subsequence (LCS) algorithm using the dynamic
programming method that was discussed in class. (No credit will be given if you implement
a brute force algorithm, which does exhaustive comparisons between two input strings, or
any other algorithm unless you prove your algorithm is correct and more efficient than the
LCS algorithm described in Chapter 7.) Save your source code in a file and name the file as
lcs.cpp or lcs.java.
Make sure that your program can take any two input strings in the Linux command line and
print the LCS found between the two input strings. (Assume that a string consists of at most
100 alphabetic characters.) For example, if we type “lcs abc afgbhcd” in the command line
to find the LCS between string “abc” and string “afgbhcd”. Again, your program should
work for arbitrary two input strings. No credit will be given, if your program only works for
some specific strings, but fails to find the LCS for other strings.
Program Usage
Your program should be invoked as follows.
$> ./lcs <input-string1> <input-string2>
A sample run of your program appears below.
$> ./lcs ABCDEfghi AcbDedghaq
A sample output is as follows (standard output in the terminal)
Length of LCS: 4
LCS: ADgh
2. [45%] Write a program floyd.cpp or floyd.java to find all pairs shortest paths using Floyd’s
algorithm for several undirected complete graphs, which are saved in a file called
output.txt. Print all pairs shortest paths and their lengths.
Program Usage
Your program should be invoked as follows
$> floyd <graph-file>
Graph File: <graph-file> is the name of a file that includes more than one problem. The linesthat
correspond to problem j will contains an integer n (between 5 and 10) that indicates how many cities
and n x n adjacency matrix A (that is, the distance between n cities, between 1 to 10), in the next n
rows. Note that no infinity will appear in the matrix A.
A sample graph file appears below.
Problem 1: n = 7
0 6 5 4 6 3 6
6 0 6 4 5 5 3
5 6 0 3 1 4 6
4 4 3 0 4 1 4
6 5 1 4 0 5 5
3 5 4 1 5 0 3
6 3 6 4 5 3 0
Problem 2: n = 6
0 1 2 1 3 4
1 0 3 2 2 3
2 3 0 3 3 6
1 2 3 0 3 5
3 2 3 3 0 5
4 3 6 5 5 0
Output File
Output the solution of problem 1 first, then problem 2, and etc. The solution of problem j should
start with an integer n (the number cities) and the n x n Pointer Array P (in the next n rows). The
shortestpathsshouldthenfollow,oneperline.OutputtheshortestpathsfromC1toall
othercities,thenC2toallothercities,andCntoallothercities.
Asampleoutputfile:
Problem 1:n=7 P matrix:
0006306
0050040
0500005
6000306
3003030
0400300
6056000
V1-Vj: shortestpathandlength
V1V1:0
V1V2:6
V1V3:5
V1V6V4:4
V1V3V5:6
V1V6:3
V1V6V7:6
V2-Vj: shortestpathandlength
V2V1:6
V2V2:0
V2V5V3:6
V2V4:4
V2V5:5
V2V4V6:5
V2V7:3
V3-Vj: shortestpathandlength
V3V1:5
V3V5V2:6
V3V3:0
V3V4:3
V3V5:1
V3V6:4
V3V5V7:6
V4-Vj: shortestpathandlength
V4V6V1:4
V4V2:4
V4V3:3
V4V4:0
V4V3V5:4
V4V6:1
V4V6V7:4
V5-Vj: shortestpathandlength
V5V3V1:6
V5V2:5
V5V3:1
V5V3V4:4
V5V5:0
V5V3V6:5
V5V7:5
V6-Vj: shortestpathandlength
V6V1:3
V6V4V2:5
V6V3:4
V6V4:1
V6V3V5:5
V6V6:0
V6V7:3
V7-Vj: shortestpathandlength
V7V6V1:6
V7V2:3
V7V5V3:6
V7V6V4:4
V7V5:5
V7V6:3
V7V7:0
Problem 2:n=6
P matrix:
000022
001100
010102
011002
200002
202220
V1-Vj:shortestpathandlength
V1V1:0
V1V2:1
V1V3:2
V1V4:1
V1V2V5:3
V1V2V6:4
V2-Vj:shortestpathandlength
V2V1:1
V2V2:0
V2V1V3:3
V2V1V4:2
V2V5:2
V2V6:3
V3-Vj:shortestpathandlength
V3V1:2
V3V1V2:3
V3V3:0
V3V1V4:3
V3V5:3
V3V1V2V6:6
V4-Vj:shortestpathandlength
V4V1:1
V4V1V2:2
V4V1V3:3
V4V4:0
V4V5:3
V4V1V2V6:5
V5-Vj:shortestpathandlength
V5V2V1:3
V5V2:2
V5V3:3
V5V4:3
V5V5:0
V5V2V6:5
V6-Vj:shortestpathandlength
V6V2V1:4
V6V2:3
V6V2V1V3:6
V6V2V1V4:5
V6V2V5:5
V6V6:0