Computer Science 385
Design and Analysis of Algorithms

Spring 2026, Siena University

Home     Syllabus     Schedule

Agenda

• Announcements
  • Sign up to volunteer for the HSPC!
  • Empirical Study 1: [PDF] due Wednesday (code) and next Monday (writeup)
  • Problem Set 3: [PDF] due Friday
  • tomorrow's lab is partially on computers
• Decrease and conquer wrapup
  • More recurrences
  • Topological Ordering: source removal algorithm
  • The Fake Coin problem
  • One to practice on your own: Levitin Exercise 2.4.4, p. 77
• Introduction to Divide and Conquer
  • basic idea
  • the Master Theorem

Terminology

• directed acyclic graph/dag
• topological sort
• master theorem
• mergesort