Skip to main content
MyCourses MyCourses
  • Schools
    School of Arts, Design, and Architecture (ARTS) School of Business (BIZ) School of Chemical Engineering (CHEM) –sGuides for students (CHEM) – Instructions for report writing (CHEM) School of Electrical Engineering (ELEC) School of Engineering (ENG) School of Science (SCI) Language Centre Open University Library Aalto university pedagogical training program UNI (exams) Sandbox
  • Service Links
    MyCourses - Instructions for Teachers - Teacher book your online session with a specialist - Digital tools for teaching - Personal data protection instructions for teachers - Instructions for Students - Workspace for thesis supervision Sisu Student guide Courses.aalto.fi Library Services - Resourcesguides - Imagoa / Open science and images IT Services Campus maps - Search spaces and see opening hours Restaurants in Otaniemi ASU Aalto Student Union Aalto Marketplace
  • ALLWELL?
    Study Skills Support for Studying Starting Point of Wellbeing About AllWell? study well-being questionnaire
  •   ‎(en)‎
      ‎(en)‎   ‎(fi)‎   ‎(sv)‎
  • Toggle Search menu
  • Hi guest! (Log in)

close

Can not find the course?
try also:

  • Sisu
  • Courses.aalto.fi

CS-E4500 - Advanced Course in Algorithms D, Lecture, 6.9.2022-1.12.2022

This course space end date is set to 01.12.2022 Search Courses: CS-E4500

  1. Home
  2. Courses
  3. School of Science
  4. department of...
  5. cs-e4500 - ad...
 
Syllabus

General

  • General

    General

    Overview:

    This is an advanced level (optional) course in the Fall of 2022 diving deeper into the theory side of algorithms. The focus of this iteration is on randomized algorithms with applications on parallel and distributed algorithms. Randomization often allows for relatively simple algorithm design outsourcing the hard part to the analysis. If deterministic algorithms are desired, one can often derandomize the randomized design with a small overhead. In the context of parallel algorithms, randomness offers tools for symmetry breaking, a crucial tool for efficient algorithms.


    Prerequisites: Fundamentals of algorithm design and analysis (e.g. CS-E3190). Mathematical maturity.

    First lecture: 6.9.2022 at 12:15 - 14:00 in T5 - A133
    First exercise: 15.9.2022 at 12:15 - 14:00 in Undergraduate Centre, ALMA MEDIA - U356


    Learning objectives

    • An introduction to central concepts in randomized algorithms such as concentration bounds.
    • Analysis of randomized processes with limited dependence.
    • Derandomization through the method of conditional expectations


    Schedule

    Week 1: Introduction. Basic concepts related to random variables such as probability, independence, Las Vegas / Monte Carlo algorithms and probability boosting.

    Week 2: The coupon's collector problem. Your favorite supermarket has announced a special offer for anyone that collects all of their 100 different campaign stickers. After each purchase, you obtain one sticker uniformly at random. How many purchases do you need to make in expectation and high probability until you obtained all the stickers?
    Notes: 02-notes

    Week 3: Suppose there is a randomized process that creates a combinatorial object, such as a graph cut, with a strictly positive probability. Then clearly, such an object must exists! We introduce the probabilistic method and use the expectation argument to find large cuts and satisfying assignments for the SAT problem.
    Notes: 03-notes

    Week 4: More on probabilistic method. There exist graphs with a high chromatic number and high girth. Furthermore, we introduce the method of conditional probabilities to derandomize the max cut approximation algorithm. Interestingly, this algorithm turns out to be equivalent to the greedy algorithm.
    Notes: 04-notes

    Week 5: Even more on probabilistic method. Often, when searching for a point in a probability space, the random variables have dependencies. These dependencies  yield difficulties in applying the probabilistic method. The Lovasz Local Lemma is a tool that provides existential guarantees in case the dependencies are sparse in the sense that each random variable depends only on a few other random variables.
    Notes: 05-notes

    Week 6: k-wise independent randomness. Often and in many applications, mutual independence of events or random variables is too much to ask. A weaker notion of independence is pairwise (or k-wise) independence, which means that each random variable or event is independent of any other single (or k) random variables or events. We will elaborate on this perhaps unintuitive concept and show how to create b pairwise independent random variables from log b mutually independent random variables. We will apply this to obtain an algorithm for finding a cut of size m/2 and give a straightforward way to derandomize this algorithm.
    Notes: 06-notes

    Week 7: Bonus problems

    • icon for activity FilePracticalities File PDF document
    • icon for activity FileExercise points File PDF document
    • icon for activity ForumAnnouncements Forum

Course home

Course home

Next section

Graded Sheets►
Skip Upcoming events
Upcoming events
Loading There are no upcoming events
Go to calendar...
  • CS-E4500 - Advanced Course in Algorithms D, Lecture, 6.9.2022-1.12.2022
  • Sections
  • General
  • Graded Sheets
  • Tutorial Sheets
  • Code of Conduct
  • Home
  • Calendar
  • Learner Metrics

Aalto logo

Tuki / Support
  • MyCourses help
  • mycourses(at)aalto.fi
Palvelusta
  • MyCourses rekisteriseloste
  • Tietosuojailmoitus
  • Palvelukuvaus
  • Saavutettavuusseloste
About service
  • MyCourses protection of privacy
  • Privacy notice
  • Service description
  • Accessibility summary
Service
  • MyCourses registerbeskrivining
  • Dataskyddsmeddelande
  • Beskrivining av tjänsten
  • Sammanfattning av tillgängligheten

Hi guest! (Log in)
  • Schools
    • School of Arts, Design, and Architecture (ARTS)
    • School of Business (BIZ)
    • School of Chemical Engineering (CHEM)
    • –sGuides for students (CHEM)
    • – Instructions for report writing (CHEM)
    • School of Electrical Engineering (ELEC)
    • School of Engineering (ENG)
    • School of Science (SCI)
    • Language Centre
    • Open University
    • Library
    • Aalto university pedagogical training program
    • UNI (exams)
    • Sandbox
  • Service Links
    • MyCourses
    • - Instructions for Teachers
    • - Teacher book your online session with a specialist
    • - Digital tools for teaching
    • - Personal data protection instructions for teachers
    • - Instructions for Students
    • - Workspace for thesis supervision
    • Sisu
    • Student guide
    • Courses.aalto.fi
    • Library Services
    • - Resourcesguides
    • - Imagoa / Open science and images
    • IT Services
    • Campus maps
    • - Search spaces and see opening hours
    • Restaurants in Otaniemi
    • ASU Aalto Student Union
    • Aalto Marketplace
  • ALLWELL?
    • Study Skills
    • Support for Studying
    • Starting Point of Wellbeing
    • About AllWell? study well-being questionnaire
  •   ‎(en)‎
    •   ‎(en)‎
    •   ‎(fi)‎
    •   ‎(sv)‎