CS 306 Quiz 3

CS 306, Computer Algorithms II

Quiz 3, 14 October 2008

Describe the solution-candidate generation part of standard, two-part exhaustive-search implementation of string searching.

A candidate solution for the string searching problem is a character in the text string that identifies the part of the text string that matches the pattern string. The character is usually the left-most (or first) character in the substring that matches, although it can be any part of the text string as long as its relation to the match is indicated.

Assuming the character is the left-most matched character, the set of candidates would be all possible indices in the text string that could match, which would be the set { 0, 1, ..., T - 1 }, where T is the size of the text string in characters. If you assume only a complete pattern-string match is acceptable, the upper bound can be reduced to T - P where P is the size of the pattern string in characters.
The file-packing problem discussed in class had an intractable exact solution. Which of the following variants are also intractable? Carefully explain each answer.
1. Store all files on the minimum number of CDs necessary; files can be split across CDs.
2. Store as many files as possible on a single CD. The name of any file stored should alphabetically precede the name of any file not stored.
3. Store as many files as possible on a single CD, leaving the smallest amount of unused space possible.
1: All files can be just spooled to the CDs in any order, which takes linear effort. Tractable.

2: Sort the files and spool them to the CD until it’s full. The sort takes O(n log n) and the spool is linear. Tractable.

3: This is the original problem. Examine all possible file subsets to find the largest subset that fits. Intractable.
In the algorithm for finding minimal perfect hash functions, key characters were mapped to a smaller range of values. Does it make sense to perform a similar mapping on the key lengths? Explain your answer.
It does. In particular, if none of the keys collide in their first and last letters, there's no need to consider key size and any key size can be mapped to 0. More generally, if a subset of i keys collide on the chosen characters, the key sizes ks = { s₀, …, s_j } for j ≤ i can possibly be mapped to { 0, …, j - 1 }, which, if j < max(ks) - min(ks), would result in a smaller scatter table.
A colleague thinks it's better to make important decisions last rather than first because delaying important decisions lets you gather more information to make better decisions. What do you think of your colleague's opinion? Explain your answer.
It may be useful on occasion for exhaustive search, but probably won't be consistency useful. A decision problem stops after it finds a solution, so delaying decisions (quality solution choices) until later won't be that helpful. Making good decisions early or late doesn't may not have a big effect on an optimization problem because it must examine all possible solutions. To the extent that decision time has an effect, having quality solutions early allows for better (earlier and more stringent) pruning.