Subject: Subject Sylbus: Algorithms in Uncertain Scenarios - 097280

Algorithms in Uncertain Scenarios - 097280
Given In
  Lecture Exercise Laboratory Project or
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 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.

2000siamdavid pelegdistributed computing: a locality-sensitive approach
1998cambridge university pressallan borodin and ran el-yanivonline computation and competitive analysis

Created in 08/03/2021 Time 14:05:49