Information about the Second Test

The second test in this course will take place on Friday, April 2. It will cover material from Chapter 5 through the first two sections of Chapter 9. As usual, you should expect a mixture of different types of problems: definitions, short-answer essays, longer conceptual essays, and programming.

Important terms and ideas for this test include:

Sets and maps Keys and values in a map Hash tables Hash code Properties of a good hash function Collision in a hash table Why are collisions inevitable? Open hash table Closed hash table Linear probing Run-time analysis for hash tables Hash table implementation of Sets Hash table implementation of Maps Template classes in C++ STL (Standard Template Library) Sets and Maps in the STL Iterators in the STL The SortedSet and SortedMap ADT's STL sets and maps are sorted Binary sort trees In-order traversal of a BST Successor of a node in a BST Search in a binary sort tree Insertion into a binary sort tree Deletion from a binary sort tree Balanced binary tree Run-time analysis for binary sort trees B-Trees Degree of a B-Tree Height of a B-Tree Search in a B-Tree Insertion into a B-Tree Deletion from a B-Tree Run-time analysis for B-Trees Graphs Vertices and Edges Directed graph Undirected graph Path in a graph Length of a path Cycle in a graph Dag (directed acyclic graph) Weighted graph Adjacency matrix of a graph Sparse graph Edge-list representation of a graph Breadth-first search (BFS) Use of a queue in BFS Depth-first search (DFS) Use of a stack in DFS Recursive DFS Using a boolean "visited" array Connected (undirected) graph Connected component Finding connected components Topological sort of a dag Topological sort using DFS Run-time analysis of graph algorithms The "Set" ADT set.add(x) set.remove(x) set.contains(x) The "Map" ADT map.get(k) map.put(k,v) map.remove(k) map.containsKey(k) Sets in the STL set<ItemType> s.insert(x); s.begin(); s.end(); s.find(x); set<ItemType>::iterator ++p and *p for a set iterator p Maps in the STL map<KeyType,ItemType> m[k] m.begin() m.end() m.find(k) map<KeyType,ItemType>::iterator ++p for a map iterator p p->first, p->second