York University - EECS 4171
Advanced Topics in Algorithms
Course Information
- Term: Fall 2024
- Lectures:
Synchronous lectures are held via Zoom on Tuesdays and Thursdays (at 14:30 - 15:50). They will be recorded and the recording will be made available shortly after each lecture. These lectures are "content delivery" lecture that introduces the concepts to be learned for the week.
Lectures will be broadcast live on Zoom and also recorded via Zoom (link to be added)
- Instructor:
Shahin Kamali
kamalis@yorku.ca
- Teaching Assistants:
TBD - Office hours:
Thursdays 13:00 - 13:45 in person at LAB 101
Thursdays 13:45 - 14:30 on Zoom (link to be added)
Or by appointment (send an email)
- Info & Syllabus:
Find all details here
This is an advanced course in design and analysis of algorithms. The course exposes students to various topics in design, analysis, application, and restrictions of algorithms. We cover various topics in exact algorithms (e.g., flow, matching, string algorithms), approximation algorithms (graph problems, knapsack), randomized algorithms (e.g., primality testing, random walks) geometric algorithms (convex hull, art-gallery, geometric matching), streaming algorithms (majority problem, lower bounds), online algorithms (ski-rental, search, paging, and regret minimization), linear programming (algorithms and applications), and algorithmic fairness.
Students will learn various tools and analysis techniques to allow them design algorithms with provable guarantees in practical scenarios. While the course covers a wide range of algorithmic problems, one or two algorithms from each topic will be discussed in depth.
By the end of this course, students are expected to be able to design algorithms that use techniques such as LP duality or randomization and be able to analyze and improve these algorithms using analysis techniques that provide performance guarantee in terms of time complexity or quality of the solutions.
- Textbooks:
No book is required to be purchased. References and lecture notes will be posted for various topics.
- TOPICS
Possible topics to be covered include (note that these material is subject to slight change):
- Exact Algorithms
- Flow algorithms: Ford-Fulkerson, Edmond-Karp, Push-relabel algorithms
- Graph matching, bipartite matching, Blossom algorithm
- String algorithms and pattern matching: KMP, Boyer-Moore, suffix trees
- Data compression: bZip2 and LZ
algorithms
- Approximation Algorithms
- Traveling salesperson (TSP problem): NP-completeness overview, Christofides algorithm, Euclidean TSP.
- Coloring, vertex cover, and
Unique Game Conjecture
- Randomized algorithms
- Primality testing, Miller-Rabin algorithm
- Verifying matrix multiplication: Freivald's algorithm
- Identity testing, Schwartz-Zippel Theorem
- Randomized complexity classes: ZPP, RP, co-RP, BPP
- Random walks, Papadimitrou’s
2SAT algorithm
- Introduction to Steaming and Online Algorithms
- Majority problem and algorithms: Boyer-Moore majority vote, Bloom filters
- Matching and information-theory lower bounds
- Ski-rental, cow-path, and paging
- Online learning and regret
minimization
- Linear programming (LP)
- LP duality, approximation algorithms
- Minimax / Simplex
- LP applications in design of
online algorithms: online set cover
- Fairness in Algorithm Design
- Time Fairness: Secretary and Knapsack problems
- Group fairness: matching and
clustering
- Geometric Algorithms
- Convex hull algorithms
- Art-gallery problem
- Non-crossing matching
- Further Topics
- Polynomial Time Approximation Schemes (PTAS): bin packing
- Fully Polynomial Time
Approximation Schemes: Knapsack
- Fixed Parameter Tractable
Algorithms