• Basic Concepts
  • ADTs
  • logarithmic math

• Recursion/Induction
  • understanding of recursion
  • ability to implement recursive functions
  • understanding of benefits/overheads of recursion
  • understanding of inductive proof technique

• Asymptotic Analysis
  • understanding of concept
  • ability to manipulate/compare functions asymptotically
  • ability to evaluate an algorithm's asymptotic behavior (space & time)
  • best case, worst case, average case analysis
  • understanding of O(), Omega(), Theta()

• Data Structures -- for each of the following: list, stack, queue, tree, binary search tree, hash table...
  • understand what it is
  • be familiar with its major operations
  • know how it is implemented
  • be able to give its operations' running times
  • have a sense for when it is useful

• Lists
  • array-based, link-based, doubly-linked, dummy head/tail nodes
  • normal vs. sorted
  • (in)appropriateness of recursion

• Stacks & Queues
  • array-based vs. link-based

• Trees
  • terminology (root, leaf, ancestor, etc.)
  • fixed-degree implementation vs. first child/sibling implementation
  • pre-order, post-order traversals

• Binary Search Trees
  • numerical properties (depth vs. number of nodes vs. leaves, etc.)
  • binary search tree structure & ordering
  • pre-order, post-order, in-order traversals
  • lazy deletion
  • rotations
  • AVL Tree balance condition
  • Splay Trees' notion of amortized analysis
  • Red-Black Tree properties

• Hash Tables
  • properties of good hash function
  • concept of string hashing
  • load factor
  • separate chaining
  • rehashing
  • open addressing (linear probing, quadratic probing, double hashing)
  • primary clustering