Coursebooks 2017-2018

PDF
 

Analytic algorithms

CS-435

Lecturer(s) :

Vishnoi Nisheeth

Language:

English

Summary

In the last decade, many fundamental algorithmic problems have benefited from viewing the underlying discrete problems through the lens of continuous/analytic methods. In this course we will introduce a selection of such techniques and explore their applications.

Content

' Convexity and gradient descent

' Multiplicative weight update (MWU) method and online convex optimization

' Gradient descent based methods for solving linear equations

' Optimization problems involving polynomials

' Graphs and their eigenvectors and eigenvalues

' Graphs as electrical networks

' Graphs Laplacians and solving Laplacian equations

' Application: Fast algorithms to compute network flows (using MWU, electrical flows and Laplacian solvers)

' Application: Fast algorithms for graph cuts (using eigenvectors and Laplacian solvers)

' Application: Algorithms for counting perfect matchings in graphs (using convex programs involving polynomials)

Keywords

Convex optimization, Spectral methods, Polynomials, Discrete Optimization, Continuous Optimization

Learning Prerequisites

Required courses

Calculus (MATH105), Linear Algebra (MATH110), Algorithms (CS250), Theory of Computation (CS251) or equivalents, Advanced Algorithms (CS-450) (or equivalent).

Recommended courses

Important concepts to start the course

This is an advanced course and requires mathematical maturity including linear algebra, multi-variate calculus, analysis, probability and algorithms.

Learning Outcomes

By the end of the course, the student must be able to:

Assessment methods

Homeworks, Scribe Notes, Exam and Project/Presentation*.

*Tentative

Resources

Bibliography

Books relevant to the course:

Vishnoi - Lx=b

Nesterov - Introductory lectures on convex optimization

Shalev-Schwartz - Online learning and online convex optimization

References for Basics:

Apostol - Calculus I and II

Strang - Linear algebra and its applications

Boyd and Vanderberghe - Convex optimization

Strogatz - Nonlinear dynamics and Chaos

Ressources en bibliothèque
Notes/Handbook

Vishnoi - Zeros of Polynomials and their Applications to theory. Available from http://theory.epfl.ch/vishnoi/Publications_files/ZerosIntro.pdf

Vishnoi -- A mini-course on convex optimization. Available from http://theory.epfl.ch/vishnoi/Nisheeth-VishnoiFall2014-ConvexOptimization.pdf

In the programs

  • Data Science, 2017-2018, Master semester 2
    • Semester
      Spring
    • Exam form
      During the semester
    • Credits
      4
    • Subject examined
      Analytic algorithms
    • Lecture
      2 Hour(s) per week x 14 weeks
    • Exercises
      1 Hour(s) per week x 14 weeks
  • Computer Science, 2017-2018, Master semester 2
    • Semester
      Spring
    • Exam form
      During the semester
    • Credits
      4
    • Subject examined
      Analytic algorithms
    • Lecture
      2 Hour(s) per week x 14 weeks
    • Exercises
      1 Hour(s) per week x 14 weeks
  • Communication Systems - master program, 2017-2018, Master semester 2
    • Semester
      Spring
    • Exam form
      During the semester
    • Credits
      4
    • Subject examined
      Analytic algorithms
    • Lecture
      2 Hour(s) per week x 14 weeks
    • Exercises
      1 Hour(s) per week x 14 weeks
  • Communication Systems - master program, 2017-2018, Master semester 4
    • Semester
      Spring
    • Exam form
      During the semester
    • Credits
      4
    • Subject examined
      Analytic algorithms
    • Lecture
      2 Hour(s) per week x 14 weeks
    • Exercises
      1 Hour(s) per week x 14 weeks

Reference week

MoTuWeThFr
8-9
9-10
10-11
11-12
12-13
13-14
14-15
15-16
16-17
17-18
18-19
19-20
20-21
21-22
Under construction
Lecture
Exercise, TP
Project, other

legend

  • Autumn semester
  • Winter sessions
  • Spring semester
  • Summer sessions
  • Lecture in French
  • Lecture in English
  • Lecture in German