Lecture 12

Lecture 12: Decrease and Conquer Algorithms; Recurrences; Quiz 2
Date: Monday, February 11, 2019

Agenda

Announcements
- Lab 4: Brute-Force Algorithms, due before your lab meeting this week
- Problem Set 2: [PDF] due Friday
- Please bring laptops to lab again this week if you can, also textbooks (also note weather concerns)
Exam 1 information
- Next Tuesday, February 19, Roger Bacon 202
- Exam available 6-10 PM, but you must start by 8 and cannot leave before 8
- Those who cannot make that time, please see me soon so we can make arrangements
- No lab meetings Tuesday, February 19 or Wednesday, February 20
- Topics covered are those in the first 3 chapters of Levitin, Lectures up to 11, labs up to 5, and the first two problem sets
- Some practice questions coming, and we can think about some review times
- You will be provided with all needed summation and log formulas, and you will be permitted a single double-sided sheet of handwritten notes as a reference
- At the least, I will have extra office hours Tuesday afternoon
Quiz 1 return and quick recap
Problem Set 1: [PDF] return and quick recap
Finished up solution to the assignment problem from Friday
Decrease and conquer algorithms
- insertion sort, both iterative and recursive
Analyzing recursive algorithms with recurrences
Quiz 2

Terminology