Computer Science 385
Design and Analysis of Algorithms
Spring 2018, Siena College
Lecture 9: Decrease and Conquer Algorithms
Date: Monday, February 12, 2018
Agenda
- Announcements
- Lab 4: Brute-Force Algorithms [HTML] [PDF], due before your lab meeting this week
- Problem Set 2: [PDF] due Friday
- Please bring laptops to lab again this week if you can.
- Exam 1 information
- Next Tuesday, February 20, Roger Bacon 202
- Exam available 6-10 PM, but you must start by 8 and cannot leave before 8
- No lab meetings Tuesday, February 20 or Wednesday, February 21
- Topics covered are those in the first 3 chapters of Levitin,
Lectures up to 8, 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 morning
and afternoon
- Decrease and conquer algorithms
- insertion sort, both iterative and recursive
- Analyzing recursive algorithms with recurrences
Terminology
- decrease and conquer
- decrease by one
- decrease by constant factor
- insertion sort
- recurrence relation
- stopping condition/base case of a recurrence