Computer Science 385
Design and Analysis of Algorithms

Spring 2025, Siena College

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: 20 bonus problem set points for everyone if we get to 95% participation rate by the time the evals close
  • Optional final exam review session tomorrow at 9:30 in RB 302
  • Join us for lunch and trivia tomorrow!
  • And the exam itself right here on Thursday at 11
• The impossible search algorithm
• Limitations of Algorithms
  • the P and NP classes
    • tractability
    • class P
    • class NP
    • NP-complete problems
    • HOMER³ believes P=NP
• Department assessment questions

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)