Algorithm Design and Analysis

Algorithm Design and Analysis
A study of the design and analysis of algorithms as solutions to problems, including dynamic programming, linear programming, greedy algorithms, divide-and-conquer algorithms, graph algorithms, and intelligent search algorithms.
C S
312
 Hours3.0 Credit, 3.0 Lecture, 0.0 Lab
 PrerequisitesC S 240 & C S 252; or C S 240 & BIO 365
 TaughtFall, Winter
Course Outcomes

Fundamental Computer Algorithms

The student understands fundamental computer algorithms that can be organized in the following algorithmic paradigms: dynamic programming, linear programming, greedy algorithms, divide-and-conquer algorithms, graph algorithms, intelligent search algorithms, and --to a lesser degree--randomized algorithms. As an algorithmic problem solver, the student can formulate novel or unfamiliar problems in mathematical terms so as to elucidate a given problem's relation to known problems, choose a paradigm for solving the problem, and design an algorithm to solve the problem.

Analysis

The student can analyze algorithms belonging to those algorithmic paradigms for their asymptotic worst-case behavior in terms of time and space. Furthermore, the student can analyze algorithms empirically (under simplifying assumptions) and understands the relationship of empirical analysis to average-case behavior. Also, the student can solve LTI difference equations (with geometric forcing functions and change of variable) and can use them to analyze the efficiency of recursive algorithms.

Efficiency

The student can make the distinction between problems and their algorithmic solutions. Moreover, the student can distinguish between efficient and inefficient solutions and can relate these distinctions to the complexity classes of problems, namely P, NP, and NP-Complete learned earlier in the curriculum (CS 252).

Correctness

The student can prove the correctness of a subset of the algorithms considered in the course.

Implementation

The student can independently implement selected algorithms in the context of motivating applications using C# with the Visual Studio IDE.