CS:3330 Final Exam Announcement

The Final exam for CS:3330 "Algorithms" will be held on May 10th (Monday) from 7:30 am to 9:30 am in LR1 Van (Van Allen Hall).

During the exam you can use any written/printed material you bring, including books and lecture notes; in other words, this is an open book/notes exam. Make sure you bring everything that you feel you will need to the exam because you will not be allowed to share or borrow material with classmates during the exam. You will have to turn off and remove from your vicinity all electronic devices including cell phones, lap tops, calculators, dictionaries, etc.

There will be 5 problems on the exam and here is some information on each problem.

  1. On graph algorithms, specifically SSSP and MST algorithms.

  2. On amortized analysis of data structure operations. For practice problems see Problems 4 and 8 from Lecture 15 of Jeff Erickson's notes.

  3. On the divide-and-conquer method For practice problems see Problems 1 and 2 in this graduate algorithm's midterm and Problem 1 in this graduate algorithm's midterm retake.

  4. On the dynamic programming method. For practice problems see Problem 3 in this 16 graduate algorithm's midterm, Problem 2 in this graduate algorithms homework, and Problems 3(a) and 3(g) from Lecture 5 of Jeff Erickson's notes.

  5. On intractability: the class P, NP, NP-hard, NP-complete, showing that a problem is in NP, polynomal-time reductions. For practice problems see Problem 5 in Fall 15, Final