Traditional Algorithms Rely on Random Access to the Whole Input Throughout the Execution.in Reality, However, Parts of the Input Are Often Revealed in a Later Stage Thus Requiring Alternative Algorithmic Models That Capture Such Uncertain Scenarios. the Course Aims at Investigating Such Algorithmic Models through Various Combinatorial Optimization Problems.

Learning Outcomes
Upon Completion of the Course, the Students Will Know How to:
1. Design Algorithms for Basic Online Problems and Analyze Their Competitive Ratio. These Problems Include: Variants of the Paging Problem,Limited Cases of the Metrical Task System Problem, Problems Based on the Rent-Or-Buy Principle
2. Design Algorithms for Basic Problems Under the Streaming Model and Analyze Their Approximation Ratio. These Problems Include: Variants of the Minimum Spanning Tree Problem in Graphs, Variants of Spanner Construction Problems in Graphs,Limited Cases of Vertex/Edge Covering Problems in Graphs and Hypergraphs
3. Apply Basic Principles in the Design and Analysis of Algorithms for Combinatorial Stochastic Optimization Problems. These Principles Include: Sampling for the Purpose of Constructing Solutions,Using Linear Programming
4. Apply Basic Principles in the Design and Analysis of Distributed Algorithms in the Message Passing Model. These Principles Include: Using Randomness for the Purpose of Symmetry Breaking,Dependency on the Network Size Vs Dependency on the Maximum Degree in Local Computation.