CS575Design and Analysis of Algorithms 辅导
日期：2023-11-12 07:54
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
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: 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
3. [10%] 10% of the grade will be based on good coding style and meaningful comments.
Allprogrammingmust be doneusing C or C++ or java in Linux (remote.cs.binghamton.edu)
where your code will be tested. Create a tar file thatincludes(1)source code files,(2)a
Makefileto produce anexecutable, and (3) a readme filethatclearly describes how to run
your code. Submitonlythe tar file through theBlackboard. Thename ofthetarfileshould
be yourlastname_yourfirstname _proj3.tar (Do notusespecial characterslike#,@,or&,
becausetheyhave causedBlackboardproblems in the past.)Supposethatyour assignment
filesareunder the directory of/your_userid/yourlastname_yourfirstname_proj3/andyou
areunder that directory right now.To create a tar fileunder /your_userid directory, do the
following inLinux commandline:
>cd..
>tarcvf yourlastname_yourfirstname_proj3.tar yourlastname_yourfirstname_proj3
Toview thecontentofthecreatedtarfile,dothefollowing inLinux commandline:
>tartvf yourlastname_yourfirstname_proj3.tar
Finally,readthefollowing policiescarefully:
? Allwork must represent each individualstudent’sowneffort.If you show your codeorany
other part ofyour work tosomebody else orcopy oradapt somebodyelse’s work found
online oroffline,youwillgetzeroandbepenalizedpertheWatsonSchoolAcademic
HonestyCode(http://www.binghamton.edu/watson/about/honesty-policy.pdf).
? Todetect software plagiarism,everybody’scode will becross-checkedusing anautomated
tool.
? Your code will be compiled and executed.If your codedoesnotcompileorproduceany
runtimeerrors such assegmentationfaultsorbuserrors,youwillgetzero.
? The instructor andTAs willnotreadordebugyourcode. The instructor andTAs willnot
takealookat an emailedcode.If you need general directions,show your codetoaTA
duringher office hours. TheTAs willnotdoprogrammingordebugging for you though.
TheTAs willonlyhelpyouunderstandalgorithmstobeimplementedandanswer basic
questions relatedto implementation.
