Computer Science 385
Design and Analysis of Algorithms

Spring 2019, Siena College

Home     Syllabus     Schedule

Agenda

• Announcements
  • Reminder: everyone gets 15 quiz bonus points if we get 95% or better response rate on course evaluations - do them today!!
  • Academic Showcase Project: [HTML] [PDF] code submissions and final writeups due this afternoon by commiting and pushing to GitHub
  • Get any remaining Lab 11: Limitations of Algorithm Power submissions to me today
• Final exam reminders
  • Wednesday, May 1, 8:30-10:30 AM, RB 202, but I will plan to be there early for anyone who wants to start and have some extra time
  • You will be provided with all needed summation and log formulas, and you will be permitted up to three double-sided sheets of handwritten notes as a reference
  • Exam is cumulative but there is more of an emphasis on topics since Exam 2: backtracking and limitations of algorithm power
  • Reviewing all labs and problem sets and checking out the practice questions would be a good way to prepare
  • Review times: this afternoon and tomorrow afternoon, 4-5 PM, locations TBD
• Limitations of Algorithms
  • the P and NP classes
    • tractability
    • class P
    • class NP
    • NP-complete problems
    • HOMER³ believes P=NP
• Quiz 5

Terminology

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

Links

• Simpsons Math
• Homer 3D (see 2:00 or so)