Advanced Algorithmics (AA-GEI) course at FIB

Module 2: Approximate, parameterized and streaming algorithms

Spring term 2023-2024

Modifications to the schedule, grades, and other info will be made available through the Racó located at FIB.

• Course roadmap and material
• Lists of problem
• Additional material

• Teaching staff
  • Carme Àlvarez (Responsible)
    Campus Nord, Edif. Omega, Desp. 243      
    E-mail: alvarez at cs.upc.edu
  • Maria Serna
    Campus Nord, Edif. Omega, Desp. 235     
    E-mail: mjserna at cs.upc.edu
    
  
  
• Course Roadmap
  • 1. Approximation algorithms
  • Definitions and first examples (with transitions, without transitions) (updated 19/04)
  • Linear Programming: Relax and Round (with transitions, without transitions)
  • Linear Programming: Duality (with transitions, without transitions)
  • Primal-Dual algorithms(with transitions, without transitions)
  • 2. Parameterized complexity and algorithms
  • Definitions and basic algorithmic techniques (with transitions, without transitions)
  • 3. Algorithms for data streams
  
  
• Lists of problems
  
  • Sheet 1 (consecutive, one per page)
  
  
• Some links that might be useful
  
  
  • Theoretical Computer Science Cheat Sheet
  • Dictionary of Algorithms, Data Structures, and Problems
  • A Compendium of NP Optimization Problems