analysis of algorithms: proving correctness and running time.
sorting and selection algorithms
data structures: hash tables, binary search trees, $k-{D}$ trees,
union-find, etc.
graph algorithms
combinatorial optimization: greedy algorithms, shortest paths,
dynamic programming, branch-and-bound
References:
Cormen, Leiserson, and Rivest. _Introduction to Algorithms_, MIT
Press, 1990.
Automata and computability theory:
Topics:
regular expressions and languages
finite automata
context-free grammars and languages
pushdown automata
recursive and r.e. languages
Turing machines
computability and undecidability (including diagonalization, the
halting problem, reductions, and Rice's theorem)
References:
Davis, Sigal, and Weyuker. _Computability, Complexity, and Languages_,
Academic Press, Harcourt, Brace & Company, 1994.
or
Floyd and Beigel, _The Language of Machines_, Computer Science Press,
1993.
Complexity theory:
Topics:
NP-completeness (Cormen et al, ch. 36; Davis et al, ch. 15; Floyd
et al, ch. 9; or Papadimitriou, ch. 9)
References:
any one of:
Papadimitriou. _Computational Complexity_, Addison-Wesley, 1994.
Cormen, Leiserson, and Rivest. _Introduction to Algorithms_, MIT
Press, 1990.
Davis, Sigal, and Weyuker. _Computability, Complexity, and Languages_,
Academic Press, Harcourt, Brace & Company, 1994.
Floyd and Beigel, _The Language of Machines_, Computer Science Press,
1993.
Enumeration (counting):
Topics:
permutations, Pascal's triangle, Stirling numbers
Fibonacci numbers, linear recurrences
sieve formulas
asymptotics, order of magnitude
References:
Graham, Knuth, and Patashnik. _Concrete Mathematics; a Foundation
for Computer Science_, Addison-Wesley, 1989.
or
Lovasz. _Combinatorial Problems and Exercises_, North-Holland,
1993 (chapters 1-4).
Graph Theory:
Topics:
graphs, trees, connectivity
flows and matchings
adjacency matrices
References:
or
