ON THIS PAGE:

Course Objectives

Prerequisites

Approach

Typical Text

Course Outline

Course Objectives
To develop the ability to analyze algorithms formally for correctness and efficiency.

Prerequisites
COMP 410 is a hard prerequisite.

Approach
A review of verification, and algorithmic analysis appropriate for beginning graduate students of normal preparation. A variety of interesting and important algorithms are examined using the techniques of these fields.

Typical Text
Aho, Hopcroft, and Ullman, The Design and Analysis of Computer Algorithms
Bentley, Writing Efficient Programs
Gries, The Science of Programming
Reynolds, The Craft of Programming
Sedgewick, Algorithms

Course Outline

Specification (1)

• Formal -- algebraic, state machines
• Informal -- (leave to 145?)

Verification (2)


• Partial correctness (Floyd-Hoare)
• Termination (Dijkstra)

Algorithm Analysis (2)


• Combinatorics
• Recurrence relations
• Generating functions
• order notation (O, o, omega, theta)

Problem Solving Paradigms (2)


• Divide and conquer
• Backtracking
• Dynamic programming

Algorithms and their analysis (6) Possible categories include


• Boolean matrix multiplication
• String processing
• Graph algorithms
• Geometric algorithms
• Fast arithmetic (e.g. Strassen matrix multiplication)