3 Credit Hour Course
Intended For Level 0 Term 0 Students
Prerequisite:
Randomized Algorithms: Las Vegas and Monte Carlo Algorithms; Randomized Data Structures: Skip Lists; Amortized Analysis: Different methods, Applications in Fibonacci Heaps; Lower Bounds: Decision Trees, Information Theoretic Lower Bounds, Adversary Arguments; Approximation Algorithms: Approximation Schemes, Hardness of Approximation; Fixed Parameter Tractability: Parameterized Complexity, Techniques of designing Fixed Parameter Algorithms, Examples; Online Algorithms: Competitive Analysis, Online Paging Problem, k-server Problem; External Memory Algorithms; Advanced Data Structures: Linear and Non-linear Methods
