Computer Science 385

Design and Analysis of Algorithms

Spring 2019, Siena College

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