Basic Information
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.
Faculty: Data and Decision Sciences
|Undergraduate Studies
|Graduate Studies
Pre-required courses
(94223 - מבני נתונים ואלגוריתמים and 94411 - Probability (ie)) or (94224 - Data Structures and Algorithms and 94412 - Probability (advanced)) or (94226 - Introduction to Algorithms and 94412 - Probability (advanced)) or (94412 - Probability (advanced) and 234247 - Algorithms 1)