Algorithms in Uncertain Scenarios  097280





Lecture 
Exercise 
Laboratory 
Project or Seminar 
House Work 
Weekly Hours 
3 



3 

Determination of the grade subject to submitting the final thesis.
Prerequisites:
 
(
  Data Structures and Algorithms 
094223
 
  
and
 Probability (Ie) 
094411
 ) 

or

(
  Probability (Advanced) 
094412
 
  
and
 Algorithms 1 
234247
 ) 
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 RentOrBuy 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.
TextbooksPublished  Publisher  Authors  Book 

2000  siam  david peleg  distributed computing: a localitysensitive approach 
1998  cambridge university press  allan borodin and ran elyaniv  online computation and competitive analysis 
Created in 08/03/2021 Time 14:05:49