CS575编程代写、c/c++，Java程序代做

日期：2023-11-11 10:22

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

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.