Algorithms CS G113
Fall 2008
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 Fall 2008 edition of the course we will
practice both components: finding abstractions 
and algorithm design techniques in the context
of the SDG game (Specker Derivative Game).
This game goes back to the time when I was a PhD student
at ETH Zurich in Switzerland.
The SDG game bundles numerous algorithmic
problems with lots of messy, application specific detail.
To play the game well, at least the SDG/classic version,
requires numerous abstraction steps
to find the important core.

SDG is a fun game to be played by robots,
not humans, although playing it manually 
is interesting too but requires quite
a bit of manual calculation better done by
a robot. Those robots have elements 
of real trading robots which trade with financial
derivatives and analyse the risk involved
in the derivatives. Risk analysis 
is an important concern of the SDG robot
implementor.

A second component that is important in SDG
playing is hiding secrets. You claim to know
a secret that you think is difficult to recover
by other players. This is important
in the SDG/secret version of the game.

The SDG game creates an artificial world 
in which the robots need to survive.
The robot wins that makes the most money 
following the rules of the world.
Robots that don't follow the rules are
kicked out from the game.
Algorithms are the crucial ingredients
that make a robot succeed over others.

Can you design and implement algorithms for SDG that
are the best in the class and you prove that
they are the best by wining the SDG competitions
that we will run.

What is the definition of SDG you might ask now?
We will explain it in layers.

The SDG game is a multi-player game 
where derivatives are created and bought.
A derivative consists of a predicate, a price
and a seller.
The predicate defines a set of raw materials.
The buyer of a derivative buys two rights:
the right to receive a raw material that satisfies
the predicate and the right to sell back
the finished product created
with the raw material at a price determined
by the quality of the finished product.

The important concepts are:
A set of raw materials. Predicates that
define subsets of raw materials.
Derivatives with their predicate and price.
Finished products and their quality.

Above is the most abstract version of the game.
In this course we will focus on raw materials
that are instances of a combinatorial
maximization problem. Numerous such
problems are discussed in the text book
such as Interval Scheduling (page 13),
Weighted Interval Scheduling (page 14),
Bipartite Matching (page 15) etc.
The goal now is to find a finished product,
given a raw material, where the 
quality is higher than the price originally
paid by the buyer for the derivative.
We say that the buyer makes a profit in this case.
So finishing the raw material involves
solving the maximization problem with
a quality level that achieves a profit.
Chapter 11 of the text book (about 60 pages)
talks about approximation algorithms.
Chapter 12 on local search is also
important: some of the algorithms 
needed to play SDG well are local search algorithms.

We distinguish between two different versions
of SDG: SDG/classic and SDG/secret.
In SDG/classic the range of the objective function
of the combinatorial maximization problem
is normalized to fall into the interval [0,1].
The quality of a finished product is simply
the value of the objective function.
In SDG/secret this restriction does not apply.
Instead, the raw material delivered by the seller not only consists
of an instance of a combinatorial maximization
problem but also of a number q which
is the quality achieved by a secret
finished product that the seller is trying to hide.
The finished product quality q' found by the buyer
will be compared to the quality of the secret
and the buyer will be paid 3*p if s/he
achieves p*q or more, and 0 otherwise.
(The buyer either doubles his/her money or loses it all.)
The seller has to reveal his/her secret after
the seller delivers the finished product.
This way the seller can verify that q was correct.
If the seller has unlimited resources,
she can make q as large as possible.
But this might take a long time because many
maximization problems are NP-hard (see chapter 8).

We specialize further and consider 
SDG/classic/CSP and SDG/secret/CSP.
CSP stands for Constraint Satisfaction Problem
(see page 500).
In the most general form, we are given a set 
of Boolean relations out of which we form
a set of constraints over a set of variables.
A finished product is an assignment
which satisfies a fraction of the constraints.

SDG/classic/CSP has a surprising clean solution
to play the game perfectly. Each derivative has a break-even price
which can be computed efficiently.
SDG/secret/CSP is a game that remains to be understood.
There are some partial results by Hastad.
If we would understand the game we would better understand
the security of our public key cryptosystems, such as RSA.

For SDG/classic/CSP, we have several implementations
of robots that you are welcome to build on
with your own algorithms to improve the
"intelligence" of the robots. This implementation
is based on a synchronous version of the game
where an administrator manages the players
and checks them.

Animesh Kumar and Bryan Chadwick
have also developed a generic implementation
for SDG/classic called SDG/classic/generic
where you plug in
different kinds of maximization problems
to define specific raw materials.
SDG/classic/generic implements the 
basic mechanisms (the game rules) of SDG/classic.

Specker Derivative Game (SDG).
http://www.ccs.neu.edu/home/lieber/evergreen/specker/sdg-home.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 DemFGen, a part of DemeterF.
http://www.ccs.neu.edu/research/demeter/DemeterF/

We will use DemeterF to
process the data structures in a primarily functional manner.

An important topic of the course will be techniques for 
noise elimination to form abstractions. Noise elimination
tries to identify unimportant noise in a given problem
to invent a more abstract problem that is easier to solve.
This is related to Polya's Inventor's paradox.
With DemeterF we apply noise elimination to programming
and to play SDG we will need noise elimination to solve
the underlying algorithmic problems.
Numerous instances of noise elimination appear throughout
the text book. For example, the stable marriage problem 
is obtained by noise elimination from the more general
stable matching problem.
Or later in the book, the P=NP problem is discussed:
are all problems in NP also in P? This involves checking
infinitely many problems in NP. It is well known,
due to a theorem by Cook, that it is sufficient to show
that only one problem, Satisfiability, is in P.
All the other problems in NP are just noise with respect
to the P=NP question.