CS 456 Algorithm Design and Analysis
Algorithm design is fundamental to Computer Science, and powerful algorithms are at the heart of most of the electronic tools used every day, from Facebook to Google Maps, to airline scheduling systems. This course focuses on learning fundamental principles of algorithm design and analysing the correctness and complexity of these algorithms. It covers design strategies such as greedy, divide-and-conquer, and dynamic programming strategies. This course trains students to apply powerful problem-solving techniques to the complex problems they will encounter in their careers as computer scientists.
To be able to compute the time and space complexity of both iterative and recursive algorithms. To be able to use the various algorithm design strategies to solve problems, and to be able to determine the appropriate algorithm design strategy for solving a given problem. To be able to solve problems using fundamental graph algorithms. To be able to define the classes P and NP and to explain the significance of NP-completeness.
Algorithm analysis: Asymptotic analysis, Big-O notation and use, Little o, big omega and big theta notation, Master Theorem; Algorithms design techniques: brute-force, greedy, divide-and-conquer, recursive backtracking, dynamic programming, branch-and-bound, heuristics; Graphs & graph algorithms; Foundational computational theory: Finite-state machines, Context-free grammars, Introduction to the P and NP classes and the P vs. NP problem, Introduction to the NP-complete class and exemplary NP-complete problems.
Activities in the in the weekly lab session include: working on algorithm analysis problems, algorithm design case studies, and extra time to work on open-ended assignments and projects with the aid of the instructor.