Fiches de cours 2017-2018

PDF
 

Advanced algorithms

CS-450

Enseignant(s) :

Svensson Ola Nils Anders

Langue:

English

Summary

A first graduate course in algorithms, this course assumes minimal background, but moves rapidly. The objective is to learn the main techniques of algorithm analysis and design, while building a repertory of basic algorithmic solutions to problems in many domains.

Content

Algorithm analysis techniques: worst-case and amortized, average-case, randomized, competitive, approximation. Basic algorithm design techniques: greedy, iterative, incremental, divide-and-conquer, dynamic programming, randomization, linear programming. Examples from graph theory, linear algebra, geometry, operations research, and finance.

Keywords

See content.

Learning Prerequisites

Required courses

An undergraduate course in Discrete Structures / Discrete Mathematics, covering formal notation (sets, propositional logic, quantifiers), proof methods (derivation, contradiction, induction), enumeration of choices and other basic combinatorial techniques, graphs and simple results on graphs (cycles, paths, spanning trees, cliques, coloring, etc.).

Recommended courses

An undergraduate course in Data Structures and Algorithms.

An undergraduate course in Probability and Statistics.

Important concepts to start the course

Basic data structures (arrays, lists, stacks, queues,trees) and algorithms (binary search; sorting; graph connectivity); basic discrete mathematics (proof methods, induction, enumeration and counting, graphs); elementary probability and statistics (random variables, distributions, independence, conditional probabilities); data abstraction.

Learning Outcomes

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

Teaching methods

Ex cathedra lecture, reading

Assessment methods

Supervision

Office hours Yes
Assistants Yes
Forum Yes
Others For details, see the course web page.

Resources

Bibliography

See web page for the course.

Ressources en bibliothèque
Notes/Handbook

Class notes and references for the running semester will be provided as needed within a few days after each lecture.

Websites

Dans les plans d'études

  • Data Science, 2017-2018, Master semestre 2
    • Semestre
      Printemps
    • Forme de l'examen
      Ecrit
    • Crédits
      7
    • Matière examinée
      Advanced algorithms
    • Cours
      4 Heure(s) hebdo x 14 semaines
    • Exercices
      2 Heure(s) hebdo x 14 semaines
    • Projet
      1 Heure(s) hebdo x 14 semaines
  • Informatique, 2017-2018, Master semestre 2
    • Semestre
      Printemps
    • Forme de l'examen
      Ecrit
    • Crédits
      7
    • Matière examinée
      Advanced algorithms
    • Cours
      4 Heure(s) hebdo x 14 semaines
    • Exercices
      2 Heure(s) hebdo x 14 semaines
    • Projet
      1 Heure(s) hebdo x 14 semaines
  • Science et ingénierie computationnelles, 2017-2018, Master semestre 2
    • Semestre
      Printemps
    • Forme de l'examen
      Ecrit
    • Crédits
      7
    • Matière examinée
      Advanced algorithms
    • Cours
      4 Heure(s) hebdo x 14 semaines
    • Exercices
      2 Heure(s) hebdo x 14 semaines
    • Projet
      1 Heure(s) hebdo x 14 semaines
  • Science et ingénierie computationnelles, 2017-2018, Master semestre 4
    • Semestre
      Printemps
    • Forme de l'examen
      Ecrit
    • Crédits
      7
    • Matière examinée
      Advanced algorithms
    • Cours
      4 Heure(s) hebdo x 14 semaines
    • Exercices
      2 Heure(s) hebdo x 14 semaines
    • Projet
      1 Heure(s) hebdo x 14 semaines
  • Systèmes de communication - master, 2017-2018, Master semestre 2
    • Semestre
      Printemps
    • Forme de l'examen
      Ecrit
    • Crédits
      7
    • Matière examinée
      Advanced algorithms
    • Cours
      4 Heure(s) hebdo x 14 semaines
    • Exercices
      2 Heure(s) hebdo x 14 semaines
    • Projet
      1 Heure(s) hebdo x 14 semaines
  • Systèmes de communication - master, 2017-2018, Master semestre 4
    • Semestre
      Printemps
    • Forme de l'examen
      Ecrit
    • Crédits
      7
    • Matière examinée
      Advanced algorithms
    • Cours
      4 Heure(s) hebdo x 14 semaines
    • Exercices
      2 Heure(s) hebdo x 14 semaines
    • Projet
      1 Heure(s) hebdo x 14 semaines
  • Cyber security minor, 2017-2018, Semestre printemps
    • Semestre
      Printemps
    • Forme de l'examen
      Ecrit
    • Crédits
      7
    • Matière examinée
      Advanced algorithms
    • Cours
      4 Heure(s) hebdo x 14 semaines
    • Exercices
      2 Heure(s) hebdo x 14 semaines
    • Projet
      1 Heure(s) hebdo x 14 semaines
  • Mineur en Informatique, 2017-2018, Semestre printemps
    • Semestre
      Printemps
    • Forme de l'examen
      Ecrit
    • Crédits
      7
    • Matière examinée
      Advanced algorithms
    • Cours
      4 Heure(s) hebdo x 14 semaines
    • Exercices
      2 Heure(s) hebdo x 14 semaines
    • Projet
      1 Heure(s) hebdo x 14 semaines
  • Informatique et communications (edoc), 2017-2018
    • Semestre
      Printemps
    • Forme de l'examen
      Ecrit
    • Crédits
      7
    • Matière examinée
      Advanced algorithms
    • Cours
      4 Heure(s) hebdo x 14 semaines
    • Exercices
      2 Heure(s) hebdo x 14 semaines
    • Projet
      1 Heure(s) hebdo x 14 semaines

Semaine de référence

LuMaMeJeVe
8-9 CM5 INF1
9-10
10-11 INF1
11-12
12-13
13-14 CM1
14-15
15-16
16-17
17-18
18-19
19-20
20-21
21-22
Cours
Exercice, TP
Projet, autre

légende

  • Semestre d'automne
  • Session d'hiver
  • Semestre de printemps
  • Session d'été
  • Cours en français
  • Cours en anglais
  • Cours en allemand