C S 312
Algorithm Design and Analysis
Computer Science
College of Physical and Mathematical Sciences
Course Description
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.
When Taught
Fall and Winter
Grade Rule
Grade Rule 8: A, B, C, D, E, I (Standard grade rule)
Min
3
Fixed
3
Fixed
3
Fixed
0
Title
Efficiency
Learning Outcome
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).
Title
Fundamental Computer Algorithms
Learning Outcome
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.
Title
Correctness
Learning Outcome
The student can prove the correctness of a subset of the algorithms considered in the course.
Title
Analysis
Learning Outcome
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.
Title
Implementation
Learning Outcome
The student can independently implement selected algorithms in the context of motivating applications using Python.
