General statement:

An exam plays more than a single role:

• the instructor uses it to assess the degree to which students can use the concepts introduced in class and in the text;
• the students can test their understanding of the concepts;
• it is an additional opportunity for the students to practice their problem-solving skills.

Midterm Posting Date: Friday, November 2

Midterm Due Date: Tuesday, November 6, at noon

Format: Open text, closed computers. Positively no communication between students, nor outside help (except for the instructor. Note: Andrzej will not be incommunicado between Saturday morning and Sunday evening.)

TOPICS:

• Algorithm design and analysis
  • reading: chapters 1-4.
  • fair questions:
    • deal with logarithms,
    • analyze a piece of code,
    • analyze a loop (invariants!),
    • Big-O notation (and Omega and Theta).

• Stacks and Queues (and Deques and Lists)
  • reading: chapter 10
  • fair questions:
    • know implementations,
    • simple uses,
    • list traversals,
    • sortable permutations.

• Binary (Search) Trees
  • reading: chapters 12-13
  • fair questions:
    • BT properties,implementations,
    • "natural correspondence" with forests,
    • insert values into BST,
    • BST deletion,
    • traversals (in-order, pre-order, post-order, level-order)
    • Red-Black trees: properties, operations.
    • AVL trees: properties.

• Priority Queues
  • reading: chapters 6 and 19
  • fair questions:
    • know implementations,
    • heap initializations,
    • insertions,
    • deletions,
    • sorting,
    • merging.