Computer Science 385
Design and Analysis of Algorithms

Spring 2017, Siena College

Home     Syllabus     Schedule

Agenda

• Announcements
  • You can continue work on Lab 5 until the start of your next lab on Tuesday.
• Homework Set 2 Out
• Decrease and conquer
  • Levitin describes several more decrease and conquer algorithms
  • We will consider one more "decrease by one": topological sort
  • Please read about generating permutations and subsets
  • And one more "decrease by a constant factor": the fake coin problem
• Divide and conquer
  • master theorem
  • mergesort

Terminology

• directed acyclic graph/dag
• topological sort
• source removal algorithm for topological sort
• generating permutations of a list
• generating subsets of a list
• binary search
• fake coin problem
• master theorem
• mergesort