Topics, CPSC 331, Winter 2007

Introduction -  Correctness of Algorithms -  Analysis of Algorithms -  ADTs, Stacks, Queues -  Dictionaries -  Searching and Sorting -  Graph Algorithms

Dictionaries

Synopsis

The “Dictionary” Abstract Data Type

A “dictionary” is a set of elements of some type (so that elements are distinct, since they belong to a set).

Each of the elements included in a dictionary will be required to include

• a key (or “search key,”) which belongs to some ordered set — such as the integers or the set of strings.
• additional data.

Notice that this is true of the “elements” of a real dictionary: The “keys” are the words you might wish to look up, and the associated “additional data” are the dictionary’s definitions of the words.

Operations that must be supported include the following.

• insert(x): Insert an element x into the dictionary. If the dictionary already includes an element with the same key as x then the dictionary is not changed.
• delete(k): Delete the element with key k. If no element with key k is in the dictionary, the dictionary is not changed.
• search(k): Search for and return a pointer to an element of the dictionary whose key is k if one exists. Return a null pointer if there is no such element.

Array- and List-Based Implementations

We will begin with a brief discussion of elementary array- and list-based representations of dictionaries. Notes based on the lecture presentation of this topic are now available.

Search Trees

We will continue with a discussion of binary search trees. We will consider ”ordinary” or ”regular” binary search trees as well as one kind of “balanced” binary search tree.

Notes providing an introduction to binary search trees, insertion and deletion in binary search trees, are now available.

A tutorial exercise concerning array-based and list-based representations of dictionaries, as well as binary search trees, is now available online.

Hash Tables

Finally, we will consider various kinds of “hash tables.”

References

The dictionary ADT is defined briefly on page 197 of the textbook. Various list-based implementation of dictionaries are discussed (each quite briefly) in Section 10.2

Binary search trees and hash tables are each discussed more extensively: Binary search trees are discussed in Chapters 12 and 13, while hash tables are discussed in Chapter 11.

Expectations for Students

After studying this topic in this course (including attending lectures, completing assigned reading and working through the exercises), students should understand and be able to do the following.

• Students should understand the definition and properties of the “dictionary” abstract data type, and students should be able to use this to solve computational problems that are of interest.

• Students should understand the strengths and weaknesses of the various implementations of dictionaries that have been studied and should be able to choose among these based on the characteristics of the problem that is to be solved using a dictionary.

• Students should be able to implement each of the data structures (that have been studied as “implementations” of dictionaries) in Java.

• Students should also be familiar with the implementations of these data structures that are provided as standard components of Java, and should be able to use these when writing programs.

Questions for Review

Introduction to Dictionaries; Array- and List-Based Representations

1. What is the “dictionary” abstract data type? How does it resemble a real dictionary?

2. How can a dictionary be implemented using a simple array? How are dictionary operations implemented, and how much do these operations cost, if a dictionary is implemented in this way?

3. How can a dictionary be implemented using a linked list? How are dictionary operations implemented, and how much do these operations cost, if a dictionary is implemented in this way?

Binary Search Trees

1. What is a “binary tree”?

2. What is a “binary search tree”? What is the “binary search tree property”?

3. How can a dictionary be implemented as a binary search tree?

4. What are the “size” and “depth” of a binary search tree? How are these related?

5. How are dictionary operations implemented when a binary search tree is used, and what is the cost of these operations? How do the cost of these operations depend on the shape of the search tree?

6. What is a “red-black tree”? What are the ”red-black properties”?

7. What is the relationship between the size and depth of a red-black tree?

8. How are operations on red-black trees related to corresponding operations on binary search trees?

9. What is the “expected cost” of operations on binary search trees? What assumptions are made in order to estimate the expected cost of operations? What can be concluded about the cost of operations if it is not known whether the assumptions are true?

Hash Tables

1. What is a hash table with chaining? What kind of “hash function” is needed to implement a hash table with chaining?

2. Describe (and, if it is helpful, give pseudocode for) the operations supported by a hash table with chaining. What is the worst-case cost of these operations? Why?

3. What is the expected cost of operations in a hash table with chaining? What assumptions are used to estimate the expected cost of each kind of operation?

4. What is a hash table with open addressing? What kind of “hash function” is needed to implement a hash table with open addressing?

5. Describe (and, if it is helpful, give pseudocode for) the operations supported by a hash table with open addressing. What is the worst-case cost of these operations? Why?

6. What is the expected cost of operations in a hash table with open addressing? What assumptions are used to estimate the expected cost of each kind of of operation?

7. What are each of the following?

   • linear probing
   • quadratic probing
   • double hashing

8. Two kinds of hash tables have now been discussed. How might you decide which to use?

   Note: Each is better under some circumstances. A complete answer to this question should characteristics of data, or its use, that would make each kind of hash table the better choice.

9. Describe, and discuss implementation issues concerning, each of the following ways to produce a hash function:

   • the division method
   • the multiplication method

   • Describe how to evaluate a hash function when the input is a character string. What implementation issues must be considered (and how do you handle these) when hashing a long character string?

General Questions

1. Compare and contrast all the different data structures, useful for implementing dictionaries, that have been discussed in lectures. Under what circumstances would each be a better choice than the others?

---

This page last modified: http://www.cpsc.ucalgary.ca/~jacobs/cpsc331/W07/topics/dictionaries.html