Material to Know for Exam 2

Solving recurrences by back substitution.

Solving divide-and-conquer recurrences by the Master Theorem

Mergesort - code, recurrences, and solving recurrences by back substitution

Quicksort - Hoare's partition; ideal and worst case recurrences; techniques for optimization

Russian peasant Multiplication (and division) and C++ bit operations

Binary Search

Depth First Search - DFS trees; back edges; connectedness, cycle detection

Breadth first seach pf a graph - BFS trees; cross edges

Topological sort

0-1 Knapsack; generation of combinations of 0,1,...n-1 using bit operations

There may be a few optional questions from the exercises.