Algorithms and Data CS 4800, Fall 2010. Instructor: Karl Lieberherr.

Textbook: Algorithm Design by Jon Kleinberg and Eva Tardos, Pearson and Addison Wesley. 2006.

We will study algorithmic problems from conception to implementation, following the text book. The text book says in the Preface: "Algorithmic problems form the heart of computer science but they rarely arrive as cleanly packaged, mathematically precise questions. Rather, they tend to come bundled together with lots of messy, application-specific detail, some of it essential, some of it extraneous. As a result, the algorithmic enterprise consists of two fundamental components: the task of getting to the mathematically clean core of a problem and then the task of identifying the appropriate algorithm design techniques." In this 2010 edition of the course we will practice both components.

Knowledge about algorithm design turns out to be pivotal to your career as some interesting and desirable companies first screen students with algorithm questions before they advance to later stages in the interview process.

What are algorithms about?

We produce an artifact that can solve problems for us and we make predictions about this artifact. The most important prediction is that the algorithm is correct. Often we make predictions about the resource consumption of the algorithm. The time consumed by the algorithm is an important concern, but space and energy could be other resources of interest. The prediction is made over a set of instances, such as all instances of size n. We make other predictions about algorithms: how well they solve problems relative to some standard, like the maximum solution.

Mailinglist (archive, sign-up, etc.)


Lectures | Office Hours | Course Directories
Blackboard .

The Algorithm Game

Computational Patterns This website makes a good attempt to capture algorithmic knowledge in the form of patterns (e.g., Dynamic Programming).

Dictionary of Algorithms and Data Structures (NIST)

Scientific Community Game (SCG) = Specker Challenge Game (SCG).