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. 

Some of the algorithmic problems will be connected to the 
Specker Derivative Game (SDG).
http://www.ccs.neu.edu/home/lieber/evergreen/specker/sdg-home.html

Some of those problems are needed for the game implementation and superior algorithms 
lead to superior performance of the trading robot. Other algorithmic optimization problems are given as parameters 
to SDG creating a new derivative for the game. SDG will then produce an interesting approximation
algorithm for the optimization problem. Approximation algorithms are studied
in chapter 11 of the text book.

The task of SDG is to implement trading robots that win in an artificial derivative market through offering derivatives, 
and buying and processing derivatives produced by other trading robots.
(In biological terminology, the task is to implement organisms that survive in an artificial world through offering outsourced services, 
and consuming and processing outsourced services produced by other organisms.)

Buying a derivative gives you the right to receive raw material satisfying the property prescribed by the derivative.
The second right is to sell back the finished product you produce from the raw material at a price determined
by the quality of the finished product. The derivatives are based on combinatorial maximization problems,
for example, MAX-CSP. 

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.

More information to follow.