Advanced Algorithmic Techniques with Applications

The theory of algorithms is an important foundation of both Computer Science and Computer Engineering. This is a third course on algorithms to provide students with additional algorithmic techniques and expose them to the theory of computational complexity, which offers a deeper understanding of the demarcation between hard and easy problems.

What You'll Learn

DAY 1

Hard Problems and Complexity Theory

• Key ideas: Decision and optimization problems, P and NP, NP
• Completeness and reductions
• Sample Applications

Approximation Algorithms and Heuristics

• Key ideas: Heuristic vs approximation algorithms.
• Sample Applications: Set covering, TSP, scheduling.

DAY 2

Randomized Algorithms

• Key ideas: Monte Carlo and Las Vegas algorithms.
• Sample Applications: Hashing and Bloom filters

Introduction to Lower Bounds

• Key ideas: Lower bound theory
• Sample Applications: searching, sorting, etc.