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

  • Computer Science, 2016-2017, Master semester 1
    • Semester
      Fall
    • 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, 2016-2017, Master semester 3
    • Semester
      Fall
    • 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, 2016-2017, Master semester 1
    • Semester
      Fall
    • 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, 2016-2017, Master semester 3
    • Semester
      Fall
    • 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