CPSC 327, Spring 2004
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