9.8. Key Terms

amortized analysis

deterministic finite automaton (DFA)

DFA graph

dictionary

dithering

DNA string

greedy method

KMP graph

Knuth-Morris-Pratt (KMP)

level

map

octtree

pixel

public key encryption

quantization

RSA algorithm

skip list

substring

tower

9.9. Discussion Questions

  1. Where do skip lists get their name?

  2. Compare the notion of a perfectly balanced binary search tree and a skip list. Can you draw pictures to describe these notions?

  3. What would it mean if all towers in a skip list were one level high?

  4. Given a set of 20 keys, is it possible that one of the towers could have a height of 20?

  5. Run the OctTree quantization program on an image of your choice. Try some different settings for the maximum depth of the tree as well as the final number of colors.

  6. Explain why the indices for an OctTree node are calculated starting with the most significant bit and going to the least significant bit.

  7. Draw the nodes in an OctTree, down to level 5, after inserting the following two colors: (174, 145, 229) and (92, 145, 85).

  8. Draw a DFA graph for the pattern ATC.

  9. Compute the mismatch links for the pattern ATC.

  10. Create a KMP graph for the pattern ATCCAT.

9.10. Programming Exercises

  1. Implement the following methods for the ArayList class and then analyze their performance.

    • del, delete the item at the given index from the list.

    • verb|pop|, implement the pop method with and without a positional parameter.

    • index search for a given value in the ArrayList. Return its position in the list if it is found and -1 if the item is not present.

    • Make the ArrayList iterable.

  2. The Python list supports both concatenation and repetition. Add support for the + and * operators to the ArrayList.

  3. Implement the delete method for a skip list. You can assume that the key is present.

  4. Implement methods for skip list that will allow the map to perform the following operations:

    • __contains__() will return a boolean result as to whether a key is present in the map

    • keys() will return a list of keys in the map

    • values() will return a list of values in the map

  5. Implement __getItem__() and __setItem__() methods for skip lists.

  6. Modify the OctTree class to improve the performance of the reduce method by using a more efficient data structure for keeping track of the leaf nodes.

  7. Add two methods to the OctTree class, one to write a quantized image to a disk file and one to read a file of the same format you wrote.

  8. Some versions of OctTree quantization look at the total count for all the children of a node and use that information to decide which nodes to reduce. Modify the OctTree implementation to use this method of node selection for reducing the tree.

  9. Implement a version of the simple pattern-matcher that will locate all occurrences of the pattern in the text.

  10. Modify the graph implementation from Chapter [graphs] so that it can be used to represent KMP graphs. Using the mismatch_links method, write a method that will take a pattern and create the complete KMP graph. With the graph complete, write a program that will run an arbitrary text against the KMP graph and return whether a match exists.

You have attempted of activities on this page