CSCI 406: Learning Objectives

At the end of the semester, you should be able to:

  1. Apply the fundamental algorithms listed in the syllabus by systematically stepping through their actions on a range of inputs without referring to code or pseudocode (HWs 3-7, Exams 2 & 3, Finals).

  2. Solve simple Math problems involving asymptotic notation, analyze algorithms using asymptotic notation (HW 2, Exam 1).

  3. Match asymptotic complexities to the run times of algorithms in practice, especially as this relates to the distinction between polynomial and exponential time algorithms (TSP Project).

  4. Analyze the impact of the choice of a data structure on the performance of algorithms such as sorting (HW 3, Exam 2).

  5. Appreciate the difference between O(n log n) and O(n2) algorithms, identify divide and conquer algorithms, set up recurrence relations for divide and conquer problems, perform an average case analysis, distinguish randomized algorithms from average cases analyses, and apply lower bound theory through an in-depth study and in the context of the Sorting Problem (HW 4, Exam 2).

  6. Apply steps of the dynamic programing methodology to solve the optimization problems listed in the syllabus and discussed in class (HW 5, Exam 3) as well as on an unseen non-trivial optimization problem in a group (Dynamic Programming Project).

  7. Design algorithmic solutions to non-trivial problems by modeling the problem with graphs (Maze project, group formation exercise).

  8. Define the complexity classes P, NP and NPC and the concept of “reductions" and be able to explain and apply these to simple examples (last week of class, Finals).

  9. Develop “quick and dirty” solutions for an NP complete problem (AlgoBOWL).

  10. Communicate effectively about algorithms (project reports).