Chapters for the first midterm

The first midterm exam will cover chapters 2, 4, 5, 7, and 19-20.

Topics to review

Here are more specific topics you should review:

• Computing the run time efficiency for an iterative algorithm.
• Expressing the run time efficiency of a recursive algorithm as a recurrence relation.
• Solving recurrence relations by the substitution method.
• Solving recurrence relations by the Master Theorem
• Proof of correctness for iterative algorithms
• Proof of correctness for recursive algorithms
• Union-find data structure with path compression and union by rank.
• Breadth first search
• Depth first search

Exam format

The exam will be a written, in-class exam. The exam is a closed book exam, but I will allow you to bring a single page of notes with you to the exam.