Some of the terms listed under one topic may be considered under others. For example, we may consider the Knapsack Problem first under the Greedy Method, but then it is again solved using Dynamic Programming, etc.

What kinds of questions? Describe, distinquish, brief overview, list, timing, show, reduce, prove...

Suggestion: Look at each problem type (one group at a time). Write down problem solutions/definitions to a number of the problems. Look at generalities within types (this helps to get the general method abstracted which then also helps you to remember specific solutions without "just" memorization).

1. Performance Analysis

   • Mathematical Induction

   • Recursion

   • Recurrance Formula

   • Time Complexity

   • Asympotic Notation (Big O, Omega and Theta)

   • Practical Complexities (and comparisons)

   • Performance Measurement

2. Elementary Data Structures

   • Stacks, Queues, Lists, Trees, Binary Trees, Binary Search

   • Search, Sort (general algorithms and timing)

   • Heaps, Heapsort

   • Set: UNION, FIND, Weighting and Collapsing Rules

   • Graphs (again in Chapter 6)

3. Divide and Conquer

   • General Method

   • Max and Min

   • Merge Sort, QuickSort (Hoare), Selection

   • Partition, Median of Medians

   • Strassen's Multiplication Matrix

4. The Greedy Method

   • General Method

   • Knapsack (and 0/1)

   • Minimum Cost Spanning Trees: Kruscal and Prim

   • Single-Source Shortest Path (Dijkstra)

   • Scheduling (Minimize mean finish time)

   • Huffman Codes

5. Dynamic Programming

   • General Method

   • Multistage Graphs

   • All Pairs Shortest Paths

   • Single-Source Shortest Path

   • Coin Changing

   • The Traveling Salesperson Problem

   • Transitive Closure

   • String Matching ?

6. Basic Traversals and Search Techniques

   • Breadth-first and Depth-first Search and Traversal

   • Forward edges, Back edges, Cross edges

   • Connected Components and Spanning Trees

   • Biconnected Components

   • Articulation Points and Bridges

   • Euler Partitions

7. Backtracking and Branch and Bound

   • General Method

   • N-Queens Problem

8. Lower Bound Theory

   • Comparison Based Algorithms

   • Comparison Trees

   • Oracles

   • Reductions

9. NP-Hard and NP-Complete

   • Non-Deterministic Algorithms

   • Decision Problems, Optimization problems

   • polynomially equivalent problems

   • Reductions, reductions, reductions

   • P, NP, NP-Hard and NP-Complete

   • Cook's theorem

   • Problems

     • Satisfiability

     • Clique

     • Hamiltonian Circuits and Paths

     • Node Cover Problem

     • Independent Set

     • Subgraph Isomorphism Problem

     • Longest Path

     • Feedback Node Set

     • Chromatic Number Decision Problem

     • Scheduling (Weighted Mean Finish Times)

     • Partition

   • Reductions, reductions, reductions

   • Turing (Cook's proof and Halting Problem)