Algorithm Design & Analysis

Meetings: MWF 9:10-10:10, Olin 305 (calendar)

Text: Levitin, Introduction to the Design & Analysis of Algorithms, 2nd Edition

Overview

You already know, at some level, everything you need to solve any computational problem. This course will give you the more powerful tools needed to solve computational problems efficiently. For small problems, an efficient program is more pleasant to use, as it responds in a fraction of a second rather than in minutes. For more complicated problems, an inefficient program may require so much time or memory that it is effectively unusable. Ingenious techniques for the design and analysis of algorithms will allow you to tackle these challenging problems.

Topics

In terms of the ACM’s Computing Curricula 2001, this course reviews some Programming Fundamentals (PF3 and PF4) and focuses mainly on Algorithms and Complexity (AL1, AL2, AL3, AL8, and AL10).

We will follow the text fairly closely. A rough schedule follows:

Week 1: Introduction

Week 2: Fundamentals of the Analysis of Algorithm Efficiency

Week 3: Brute Force

Week 4: Divide-and-Conquer

Weeks 5-6: Decrease-and-Conquer

Weeks 7-9: Transform-and-Conquer

Week 10: Space and Time Tradeoffs

Week 11: Dynamic Programming

Week 12: Greedy Technique

Week 13: Iterative Improvement

Week 14: Limitations of Algorithm Power