1.
Where do skip lists get their name?
Section 8.9 Advanced Topics: Exercises
Exercises Exercises
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 octree 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 octree node are calculated starting with the most significant bit and going to the least significant bit.
7.
Draw the nodes in an octree, 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 mismatched links for the pattern ATC.
10.
Create a KMP graph for the pattern ATCCAT.
11.
Implement the following methods for the
ArrayList class and then analyze their performance.remove: Delete the item at the given index from the list.pop: Implement the pop method with and without a positional parameter.index: Search for a given value in theArrayList. Return its position in the list if it is found and -1 if the item is not present.
12.
Modify
encrypt method of the Caesar cipher (Listing 8.3.1) to accept a parameter that specifies the encryption key.13.
Implement the
delete method for a skip list. You can assume that the key is present.14.
Implement methods for a 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.
15.
Implement the
getItem() and the setItem() methods for a skip list.16.
Modify the
Octree class to improve the performance of the reduce method by using a more efficient data structure for keeping track of the leaf nodes.17.
Add two methods to the
Octree class, one to write a quantized image to a disk file and one to read a file of the same format you wrote.18.
Some versions of
Octree 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 Octree implementation to use this method of node selection for reducing the tree.19.
Implement a version of the simple pattern-matcher that will locate all occurrences of the pattern in the text.
20.
Modify the graph implementation from Chapter 7 so that it can be used to represent KMP graphs. Using the
mismatchedLinks 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.
