CS 3510: Advanced Algorithms/Data Structures
Spring 2018 Assignment 6
Problems due as noted.
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.
Due Apr 6
- 6.1 - contiguous subsequence
- 6.8 - longest common substring (contiguous)
Due Apr 9
- 6.2 - trip planner
- 6.22 - sum exists?
Due Apr 11
- 6.7 - palindromic (not contiguous)
- 6.11 - longest common subsequence (not contiguous)
Due Apr 13
- 6.9 - string cutting
- 6.17 - making change
- Write a program to calculate the edit distance of two words. The program should read a file with two words per line, separated by whitespace. The program should output the edit distance for each pair of words. Each number should be displayed on a line by itself. 5 points
Due Apr 16
- 6.18 - making change
- Correct solutions for sample files of edit distance words. Problems in words.tgz or words.zip. Answers to -1 problems in answers-1.txt. The numbers displayed are the sum of all edit distances for the file in question. 5 points
Due Apr 18
- Runtime graph of edit distance as a function of the length of the words. 5 points
- For the written work, at the beginning of class, on the due dates, submit paper copies of your solutions.
- For the experimental determination, at the beginning of class on the due date, submit paper copies of the edit distances and/or runtime graphs.
Last Updated 04/01/2018