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.