Computer Science 385
Design and Analysis of Algorithms
Spring 2019, Siena College
Lecture 16: Decrease and Conquer Wrapup
Date: Friday, February 22, 2019
Agenda
- Announcements
- No office hours this afternoon (sorry!)
- Lab 5: Graph Traversals will now be accepted through the Wednesday when we return from break
- Exam 1 recap
- Problem Set 2: [PDF] grading notes, highly recursive
solution to programming task
- Problem Set 3: [HTML] [PDF] out
- Decrease and conquer wrapup
- back to insertion sort
- binary search
- topological sort
- fake coin problem
- Please read about generating permutations and subsets
Terminology
- directed acyclic graph/dag
- topological sort
- source removal algorithm for topological sort
- generating permutations of a list
- generating subsets of a list