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.