Algorithms II

Goals: 

To learn the main techniques for analyzing and designing algorithms while also building a repertory of basic algorithmic solutions to problems in many domains.

Prerequisites: 

Basic data structures (arrays, lists, stacks, queues, trees) and algorithms (binary search; sorting, including mergesort; graph connectivity; graph search); basic discrete mathematics (proof methods, induction, enumeration and counting, basic graph theory); data abstraction.

Topics: 

Algorithm analysis techniques: worst-case, average-case, randomized, competitive, approximation, space. Basic algorithm design techniques: greedy, dynamic programming, divide-and-conquer, convex optimization, spectral techniques, submodular function optimization, and randomization. For more topics, see the course webpage.

Times and Places: 

Lectures on Mondays 13-15 (CE 12) and Tuesdays 13-15 (CM 13); exercise session on Mondays 15-17 (BC02, BC04, INM201, INM203); office hours on Tuesdays 15-16 (GRA331, GRA332, GRC001). 

Exams and Homework:

There will be two exams. One midterm exam and one final exam during the exam session.  

In addition, there will be two homeworks. The first homework will take place during mid-October and the second homework in mid-December.  The homeworks can be made in groups in up to three students and the solutions must be handed in as a single PDF file for each group. 

Grading: 

The grade will be based on quizzes [5%], two homeworks [25%],  midterm [30%], and final [40%].

TAs: Davide Mazzali <davide.mazzali@epfl.ch>, Ekaterina Kochetkova <ekaterina.kochetkova@epfl.ch>, Miltiadis Stouras <miltiadis.stouras@epfl.ch>, Radu Vintan <radu.vintan@epfl.ch>, Lukas Vogl <lukas.vogl@epfl.ch>, Weronika Wrzos-Kaminska  <weronika.wrzos-kaminska@epfl.ch>,

• Introduction to the course, administrivia, topics, prerequisites, etc.
• When does the simplest algorithm work, i.e., greedy?  The answer is captured by matroids.
• Matroid intersection and arborescences.
  
  

For lecture 10, we use the lecture notes from Lecture 9.

For lecture 19 we continue with LSH (see notes for Lecture 18).

For Lecture 21, see the notes of Lecture 20: we will continue with the minimization of submodular functions  and do some problem solving if we have time.

For the notes of Lecture 22 (see last week)