# Algorithms and Data CS 4800,
Spring 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.

##
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 consumed 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.)

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)

##
the text below is old and replaced by the above link: Open Innovation using Google Wave

We divide the class into teams of 3 that will rotate.
The teams will play the Scientific Community Game = Specker Challenge Game (SCG),
adapted for algorithmic problems, called SCG-Algorithms. SCG is modeled after a scientific community
with virtual scientists that try to gain reputation. You will play the role
of algorithmic scientist who writes good algorithms with strong predictions that cannot easily be strengthened.
Scientific Community Game (SCG) =
Specker Challenge Game (SCG).

http://www.ccs.neu.edu/home/lieber/evergreen/specker/sdg-home.html
http://www.ccs.neu.edu/home/lieber/evergreen/specker/new/scg.html
http://www.ccs.neu.edu/home/lieber/evergreen/specker/new/SCG-kinds.html

For implementation we will use Java or C#.
Data structures we define using a high-level data structure definition
notation and we generate the source code using DemeterF.
http://www.ccs.neu.edu/research/demeter/DemeterF/
We will use DemeterF to
process the data structures in a multiparadigm manner, using
object-oriented, functional and aspect-oriented programming.
Only a few algorithms will be implemented.

https://lists.ccs.neu.edu/bin/listinfo/cs4800