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 5
- 6.2 - trip planner (NOT ASSIGNED. COVERED IN CLASS)
Due Apr 11
- 6.1 - contiguous subsequence
- 6.8 - longest common substring (contiguous)
Due Apr 13
- 6.11 - longest common subsequence (not contiguous)
- 6.7 - palindromic (not contiguous)
- 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.
Due Apr 18
- 6.18 - making change
- 6.9 - string cutting
- 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.
Due Apr 20
- Runtime graph of edit distance as a function of the length of the words.
- 6.22 - sum exists?
- 6.16 - garage sale
- 6.19 - making change
- 6.26 - sequence alignment
- 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 01/11/2018