Free Advanced Algorithms Course, and topics we will cover include the word RAM model, data structures, amortization, online algorithms, linear programming, semidefinite programming, approximation algorithms, hashing, randomized algorithms, fast exponential time algorithms, graph algorithms, and computational geometry.
Free Advanced Algorithms Course
The project can take several forms:
- Solve an open problem in the theory of algorithms, formulate a new problem, or make some other contribution to the study of algorithms.
- Implement algorithms solving some problem and perform an empirical evaluation. Try finding heuristics that speed up things in practice, and also finding hard inputs to break the heuristics. See if you can prove that the heuristics work well for some interesting class of inputs. Try to find modifications of how the algorithm was originally described to obtain speedup and improved memory consumption (e.g. by constant factors).
- Write a survey on a few related algorithms papers. A good approach is to first try to solve an open problem, which generally requires reading several background papers first, then switching to a survey if the problem evades solution. If possible try to come up with new definitions or abstractions that allow unifying several papers on a topic.
You are encouraged to relate the final project to your research interests, and you will not be limited to the topics discussed in class.