Midterm Time: Oct 16, during class time.
Coverage: Lectures 1-9, Chapters 1-3, Projects 1 and 2.

0. Recursion
   Write simple recursive routines

1. Math review:

   - exponents/logarithms/geometric series/arithmetic series
   - Proof by induction

2. C++ basic concepts

   - keywords: public, private, protected.
   - Parameter passing methods
   - Return passing methods
   - function objects

3. Generic programming
   - Function template and class template
   (you need to be able to write function and class template).

4. Algorithm analysis
   - notation of big O, big Omega, and big Theta.
     (formal definitions and the intuitions
   - order of important functions
   - determining complexity of functions/algorithms

5. Vector, List, Deque, Stack, and Queue
   - Prototypes and implementations of different data structures
   - Vector implementation (also project No. 2)
   - Doubly-linked list and its iterator implementation. 
      * Node structure and Key functions (insert and erase)
      * iterator implementation
   - Doubled-ended queue implementation
      * circular array concept: how to determine the number of elements 
        in a deque, empty deque, etc
      * key methods ([], front, back, push_front, pop_front, push_back, 
        pop_back: using the circular array concept).
      * iterator implementation
   - Complexity of the key methods in the data structures
   
   - stack and queue
     * concept and prototype
     * applications: DFS, BFS, postfix evaluation
     * implementations as adaptor classes. 
   - bottomline: you will need to understand the code.

Question types: 
1) T/F
2) short answers
3) longer problems and/or coding
4) project related

The following are in the exam:
   - Proof by induction
   - Formal definitions of big-O, theta, or Omega notations
   - Complexity analysis of programs (similar to homework)
   - Implementation of insert/erase in doubly linked list
   - Implementation of circular array concept in deque
   - Implementation or application of stack/queue
   - Variations of homework problems
   - Code snippets from project 1 and project 2 (25 points)