Basic Information
This Course Will Introduce Students to Advanced Algorithms For Dynamic Graphs. This Active Research Area Focuses On Questions of The Following Flavor# How Quickly Can We Solve Algorithmic Problems On Graphs That Change Slowly Over Time. in Particular, How Much Faster Than Recomputing From Scratch After Every Change in The Graph. This Question Is Central to Problems With Input That Changes Over Time (for Example, in Gps Applications, Closure and Opening of Roads Changes The Road Network), But Is Also Key to Speeding Up Algorithms With Static Inputs (in Much The Same Way That Basic Data Structures Can Be Used to Speed Up Other Classic Algorithms). The Course S Objective Is to Expose Students to Techniques and Results For Basic Problems in The Field (such As Matching, Shortest Paths, Minimum Spanning Trees, Etc). As Part of The Course, The Students Will Also Be Exposes to Central Tools in Algorithm Design and Theory Of Computer Science More Broadly That Are Relevant to The Course Topic, Including Linear Programming and Duality, Randomized Algorithms And The Multiplicative Weight Update Method. The Course Evaluation Will Be Based On Homework and a Final Project. Learning Outcomes# at The End of The Course The Students Will Be Able To# 1. Develop and Analyze Algorithms For Dynamic Graphs. 2. Speed Up Static Algorithms Using Dynamic Graph Algorithms. 3. Prove Lower Bounds For Dynamic Algorithms, Under Popular Conjectures.
Faculty: Computer Science
|Undergraduate Studies
|Graduate Studies
Pre-required courses
(46002 - Design and Analysis of Algorithms and 104034 - Introduction to Probability H) or (94412 - Probability (advanced) and 234247 - Algorithms 1) or (104034 - Introduction to Probability H and 104291 - Combinatorial Algorithms)