Computer Science 385
Design and Analysis of Algorithms
Spring 2017, Siena College
Lecture 10: Decrease and Conquer Algorithms
Date: Monday, February 27, 2017
Agenda
- Announcements
- Exam 1 is graded, and will be returned in lab tomorrow.
- Lab 5 as usual tomorrow.
- Homework Set 2 coming Friday.
- Looking ahead: Exam 2 will be during lab meetings on March 21.
- 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