In this follow-on course to 605.621 Foundations of Algorithms, design paradigms are explored in greater depth, and more advanced techniques for solving computational problems are presented. Topics include randomized algorithms, adaptive algorithms (genetic, neural networks, simulated annealing), approximate algorithms, advanced data structures, online algorithms, computational complexity classes and intractability, formal proofs of correctness, sorting networks, and parallel algorithms. Students will read research papers in the field of algorithms and will investigate the practicality and implementation issues with state-of-the-art solutions to algorithmic problems. Grading is based on problem sets, programming projects, and in-class presentations.
605.621 Foundations of Algorithms or equivalent; 605.203 Discrete Mathematics or equivalent.