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

Fall term 2025-2026

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

• Teaching staff
• Calendar
• Course roadmap and material
• Additional material

• Teaching staff
  • Maria Serna
    Campus Nord, Edif. Omega, Desp. 235     
    E-mail: mjserna at cs.upc.edu
    
  
  
• Calendar
• First part exam 28/10/2025 11:30
• Second part exam 18/10/2025 11:30
• Final Exam 08/01/2026 09:00


• Course Roadmap
  • 1. Introduction: Basic algorithmic techniques
  • 2. Computational complexity
  • The Turing Machine model
  • Some undecidable problems
  • Problems types and computational complexity classes
  • NP-Completeness
  • 3. Randomized algorithms. Modular arithmetic and primality testing
  • Probabilistic algorithms (Updated 16/10/2025)
  • Hashing
  • Bloom filters
  • Primality testing
  • RSA Cryptosystems
  • 4. Approximation algorithms
  • Approximation algorithms: definitions and the greedy approach
  • Linear Programing: relaxation and rounding
  • Linear Programing: Primal-dual
  • 5. Parameterization
  • Parameterized algorithms: definitions and the bounded search tree technique
  • Kernelization
  • Parameterizing by tree-width
  
  
  • Lists of problems
    
    • Sheet 1
    • Sheet 2
    • Sheet 3
    • Sheet 4
    • Sheet 5
    • Sheet 6
    
    
• 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 History of Computing