Coursebooks 2016-2017

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 analytic methods. In this course we will introduce a selection of such techniques and explore their applications.

Content

' Convexity, Gradient Descent and its variants

' Multiplicative Weight Update method 

' Online convex optimization

' Interior point methods for solving convex programs

' Graphs, eigenvalues and Laplacians

' Electrical and combinatorial flows

' Conjugate Gradient Method

' Graph Partitioning and Cheeger's Inequality

' Ramanujan Graphs and Real Stable Polynomials

' Applications

 

Keywords

Convex optimization, Spectral methods

Learning Prerequisites

Required courses

Calculus (MATH105), Linear Algebra (MATH110), Algorithms (CS250), Theory of Computation (CS251) or equivalents.

 

Recommended courses

Advanced Algorithms (CS-450) 

 

Important concepts to start the course

This is an advanced course and requires mathematical maturity including linear algebra, 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

Renegar - A mathematical view of interior point methods in 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

In the programs

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