Main Page for the Algorithmics and Complexity (GM) course at FME

Fall term 2023-2024

Modifications to the schedule, grades, and other info will be made available through Atenea.

• Teaching staff
• Calendar
• Course roadmap and material
• Lists of problem
• Additional material

• Teaching staff
  • Maria Serna
    Campus Nord, Edif. Omega, Desp. 235     
    E-mail: mjserna at cs.upc.edu
    
  
  
• Calendar
• Final Exam: 22/12/2023


• Course Roadmap
  • 1. Computational complexity
  • The Turing Machine model
  • Complexity classes
  • 2. Basic algorithmic techniques
  • 3. Randomized algorithms. Modular arithmetic and primality testing
  • An application of hashing
  • Modular arithmetic
  • 4. Approximation algorithms
  • 5. Parameterization
  • Kernelization
  • Treewidth
  • Parameterizing by Treewidth
  • Parameterized Complexity
  
  
  • Lists of problems
    
    • Sheet 1
    • Sheet 2
    • Sheet 3
    • Sheet 4
    • Sheet 5
    
    
• Some links that might be useful
  
  
  • Theoretical Computer Science Cheat Sheet
  • Dictionary of Algorithms, Data Structures, and Problems
  • A Compendium of NP Optimization Problems
  • The Collection of Computer Science Bibliographies
  • The History of Computing