CSCI 406: Learning Objectives
At the end of the semester, you should be able to:
- 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).
- Solve simple Math problems involving asymptotic notation, analyze algorithms using asymptotic notation (HW 2, Exam 1).
- 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).
- Analyze the impact of the choice of a data structure on the performance of algorithms such
as sorting (HW 3, Exam 2).
- 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).
- 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).
- Design algorithmic solutions to non-trivial problems by modeling the problem with graphs
(Maze project, group formation exercise).
- 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).
- Develop “quick and dirty” solutions for an NP complete problem (AlgoBOWL).
- Communicate effectively about algorithms (project reports).