Computer Science 385
Design and Analysis of Algorithms

Spring 2026, Siena University

Home     Syllabus     Schedule

Agenda

• Announcements
  • Academic Showcase Project final submissions today (be sure to look back at the requirements)
  • Problem Set 6: [PDF] hard deadline today so reference solutions can be released
  • Course evals response rate bonus offer: grading threshold for everyone if we get to 95% participation rate by the time the evals close
  • Optional final exam review session tomorrow at 2 in RB 340
  • And the exam itself right here on Wednesday at 8:30
• Limitations of Algorithms
  • the P and NP classes
    • tractability
    • class P
    • class NP
    • NP-complete problems
    • HOMER³ believes P=NP

Terminology

• distribution counting sort
• tractable problems
• intractable problems
• undecidability
• halting problem
• Class NP
• NP-complete
• NP-hard
• CNF-satisfiability problem
• independent set problem
• Hamiltonian cycle problem

Links

• P vs. NP - The Biggest Unsolved Problem in Computer Science
• Simpsons Math
• Homer 3D (see 2:00 or so)