CS201 Study Guide

Unit 8: Hash Tables, Graphs, and Trees

8a. Demonstrate effective hash tables

How does hashing determine the position of an object/element in the data storage space?
What are the means of handling collisions?
Is it necessary for the hash key to be unique across all key/data pairs?
In what way does the statistical distribution of key values affect hashing effectiveness?
How can data search be a part of a hashing capability?
How can data sorting be part of a hashing capability?

Hashing goes beyond searching and sorting to calculate the position of a key/value pair in a data storage space. No system is ever perfect. In hashing, it is possible that two different key/value pairs will try to occupy the same location in the data storage space. There are numerous ways to handle that situation, as discussed in this lecture and this follow-on lecture. Other approaches are described here on pages 324-345, with a focus on practical implementation.

8b. Demonstrate effective graphs

What is the difference between a graph and a tree?
How is the efficiency and effectiveness of a graph traversal algorithm related to a graph's topology?
In what ways may a graph be represented by a computer program?
Which are the two most common ways to visit all nodes in a graph?
Which are the two most commonly-required graph paths?

In computer science, the term "graph" refers to a set of vertices (points or nodes) and of edges (lines) that connect the vertices. The creation and traversal of graphs is an important topic when learning to solve complex problems that involve numerous relationships. For an excellent discussion on graphs and graph traversal, read Chapter 11 of this open-access text. As in all things, we need efficiency and effectiveness. Both are defined relative to the application at hand, although it is true that O(f(n)) can be estimated in general for various paradigms. We studied various graph traversals. Each is useful for different applications: finding non-cyclical paths, depth-first search, breadth-first search, lowest-cost path, minimal spanning tree.

8c. Demonstrate effective trees

What is the difference between binary and non-binary trees?
What is the difference between partial and complete trees?
How might one compare trees to graphs?
What are the basic elements of a tree?
What are the two major approaches to visiting every node of a tree?
How are infix and postfix notations related to tree-building and traversal?

Trees are a special case of graphs. A tree is a graph whose nodes do not have multiple references. Plus, tree traversal is only in one direction, downward, from root (top) to leaves (bottom). Review this page for basic definitions and illustrations. Many applications can be satisfied by binary trees (review chapter 5). However, do not be satisfied with being able to respond to common requests. A deeper understanding of trees enables solutions to a wider range of requirements. Continue your study of trees by reviewing non-binary trees (review chapter 6).

Unit 8 Vocabulary

This vocabulary list includes terms that might help you with the review items above and some terms you should be familiar with to be successful in completing the final exam for the course.

Try to think of the reason why each term is included.

Relative to Hashing

hashing
hash function
hash table
key/value pair
collision
chaining
open addressing
bucket
overflow
linear probing
load factor

Relative to Graphs

graph
digraph
labeled graph
weighted graph
vertex
path
depth-first
breadth-first
spanning tree
verticy
edge
undirected graph
adjacent
simple path
cycle
simple cycle
subgraph
acyclic graph
traversal
shortest path
minimal spanning tree
lowest-cost path

Relative to Trees

root
leaf
node
branch
parent
child
level
ancestor
descendent
depth
height
size
incomplete tree
complete tree
infix
postfix
red/black tree
binary search tree
Huffman coding tree
subtree
depth-first
width-first
post-order
pre-order