Computer Science 385

Design and Analysis of Algorithms

Spring 2019, Siena College

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

- decrease and conquer
- decrease by one
- decrease by constant factor
- insertion sort
- recurrence relation
- stopping condition/base case of a recurrence