Computer Science 385
Design and Analysis of Algorithms
Spring 2025, Siena College
Lecture 12: Decrease and Conquer Algorithms; Recurrences
Date: Monday, February 17, 2025
Agenda
- Announcements
- It's a Siena weather delay so we pivot to an asynchronous online day - all due dates remain as is
- Problem Set 2: [PDF] submission due Wednesday, no new groups
- Lab 2: METAL Data and Analysis
Practice - yeah, still, I will look at what you
have this week
- Delayed to Friday: Wrapping up the In-class group activity: Brute-Force Convex Hull (link in Canvas)
- Exam 1 information
- During labs, Tuesday, February 25
- See handout for more
- 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
Links