home page - news - syllabus - topics - schedule - assignments - tutorials - tests - java - references - Mike Jacobson |
Introduction - Correctness of Algorithms - Analysis of Algorithms - ADTs, Stacks, Queues - Dictionaries - Searching and Sorting - Graph Algorithms |
Dictionaries |
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
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.
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.
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.
Finally, we will consider various kinds of “hash tables.”
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.
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.
What is the “dictionary” abstract data type? How does it resemble a real dictionary?
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?
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?
What is a “binary tree”?
What is a “binary search tree”? What is the “binary search tree property”?
How can a dictionary be implemented as a binary search tree?
What are the “size” and “depth” of a binary search tree? How are these related?
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?
What is a “red-black tree”? What are the ”red-black properties”?
What is the relationship between the size and depth of a red-black tree?
How are operations on red-black trees related to corresponding operations on binary search trees?
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?
What is a hash table with chaining? What kind of “hash function” is needed to implement a hash table with chaining?
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?
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?
What is a hash table with open addressing? What kind of “hash function” is needed to implement a hash table with open addressing?
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?
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?
What are each of the following?
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.
Describe, and discuss implementation issues concerning, each of the following ways to produce a hash function:
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?
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 |