CS 442 - Algorithm Design and Analysis

5.0 Credits
Principles of design of efficient algorithms: recursion, divide and conquer, balancing, dynamic programming, greedy method, and data structure selection. Correctness and analysis of algorithms. Examples drawn from problems in sorting, searching, set manipulation, pattern-matching, graphs, matrices, polynomials, and integers.
Prerequisite Completion of CS 302 and CS 334 with a grade of 2.5 or higher or instructor permission.
Course-level Learning Objectives (CLOs)
Upon successful completion of this course, students will be able to:

Translate word problems into computational problems.
Determine an appropriate algorithm design paradigm for a new problem.
Design an algorithm using a variety of algorithm-design paradigms (including greedy algorithms, divide and conquer, dynamic programming, flow modeling, and others).
Prove an algorithm produces the correct answer.
Reduce between a known problem and a new problem (for showing hardness or for reusing existing algorithms).
Identify and cope with computational problems that are infeasible.
Assess the implications of modeling decisions in the real world.

Course Typically Offered
Winter