CS 3510: Algorithms

Assignment 6

Assignment

Problems identified by x.y(z) denote the problem “y”, in chapter “x” of the textbook, with part “z”. If “z” is not noted, then the entire problem is required.

Assignment 6a

6.1 - contiguous subsequence
Write a function to calculate the edit distance of two strings.

Assignment 6b

6.8 - longest common substring (contiguous)
Create a program to read pairs of words from a file. The filename will be given on the command line. Each line will contain a pair of space separated words. Feed each pair of words to the edit distance function. Display the edit distance, with one number per line.

Assignment 6c

6.2 - trip planner
6.7 - palindromic (not contiguous)
Sample input files for edit distance are available at /usr/citlocal/cs3510/words on the department computers. Modify your code to sum the edit distances for the pairs of words in the file, and only print this sum. Submit a table of the edit distances for words-*-3.txt.

Assignment 6d

6.22 - sum exists?
6.11 - longest common subsequence (not contiguous)
Add timing functions to the edit distance program. Measure the average amount of time per call to edit distance for each word length. Fill in a table of these times.

Assignment 6e

6.17 - making change
Chart the measured run time of the edit distance algorithm, along with the usual set of theoretical run time curves, properly normalized.

Assignment 6f

6.9 - string cutting
6.18 - making change

Assignment 6z, Due Never

Other problems from the chapter

Submission

Submit you solutions by the due date and time. For written problems, your work and answers as a PDF to Canvas. For code, submit the source code to the class git repository. For tables and graphs, submit a PDF to Canvas.

Last Updated 01/09/2023