Project: guidelines
==============
Main advice: find some problem you have an interest or have fun learning
more about (application you studied in another course, puzzle type problem,
search problem, etc)

type I
The typical project will underline a problem (application or abstract).
Discuss what is know about the problem (after some research).
Implement two different algorithmic strategies to solve the problem.
Do experimental testing, comparing the methods for the data set of instances.
Write all the findings in a professional report.

type II
Alternatively, the project may verse on theory of NP-completeness.
Study several known reductions for a known problem. Do more research,
read a lot of papers, survey the ideas.
Study a new application and study its NP-completeness (create a new reduction).
This is less straight forward, but may interest some theoretically inclined
students.

Below is some guidelines for type I project

1) Picking the Problem:
a) pick a real world application that interests you: scheduling, sudoku puzzles, 
network problems, DNA sequencing, etc. (some you my have studied in
other courses or have a personal interest)
OR
b) pick an abstract problem that interests you: finding cliques in graphs,
solving traveling salesman problem, formula satisfiability, graph colouring, etc.

The main characteristic of the problem is that it should be some hard problem,
e.g. NP-hard or harder.
a) may involve modeling of the problem (transforming from real world to
a model such as the ones in b) or variations of them
---------------------------------------------------------------------------------------------------
2) Choose solution strategies:

The second part of the course deals with several solution strategies
(backtracking, local search, approximation algorithms, randomized
algorithms; there are also greedy heuristics).
For each problem of the type b), many people tried various
solution strategies, and you can find papers about them as
a starting point.

Typically, you would study 2 different methods.
For example: 
Solve TSP via backtracking and via tabu search (type of local search).
Solve cliques via greedy heuristic, and simulated annealing.
Do 2 different approximation algorithms for a problem.
Use randomized algorithms plus another method for a cryptographic application.
Solve Sudoku via exhaustive search, comparing various different strategies
etc.
--------------------------------------------------------------------------------------------------
3) Specify your experimental design:

How you will obtain data (use standard problem repositories, problem databases, 
benchmarks, using real world data (if applicable), etc.

Which sort of quantities/stats you would use to  compare the 
effectiveness of your algorithms.
----------------------------------------------------------------------------------------------------

About the proposal:
With the project proposal,  you sort of give yourself your own assignment.
I can judge whether it is enough, too much. I can also give you some
guidance (ideas, pointers), given my experience in the area. I can give ideas
on how to expand a good idea that was not so well developed in the proposal.
The objective is that you communicate well what you plan to do, so that
we can discuss and revise it before you go to deep into the doing.