Main Page for Randomized Algorithms (RA-MIRI) course at MIRI-FIB

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

• Teaching staff
• Calendar
• Course roadmap and material
• Lists of problems

• Teaching staff
  • Maria Serna
    Campus Nord, Edif. Omega, Desp. 235      
    E-mail: mjserna at cs.upc.edu
  
  
• Calendar
• Final exam: January 8, 2021 (take home exam)
• In class assignments: See Racó
• Lab project: due date Jan 22, 2021


• Course Roadmap
• Basic probabilistic tools
• Introduction
• Basic probability analysis
• Figerprinting and primality (updated 01-10-2020)
• Analyzing the expected behavior
• Definitions and basic examples
• More examples
• More on expectation
• Concentration
• Basic concentration bounds
• Chernoff bounds and Sampling
• Some algorithms for sampling on data streams
• Hashing
• Balls and bins
• Universal hash functions
• Cuckoo hashing
• Approximate counting different elements
• Random processes
• Markov chains (updated 19/11/2020)
• MC: Stationary distributions (updated 03/12/2020)
• MC: some applications
• Lists of problems
  
  • Problems 1
  • Problems 2
  • Problems 3