- français
- English
Fiches de cours 2017-2018
Algorithms
CS-250
Enseignant(s) :
Kapralov MikhailLangue:
English
Summary
The students learn the theory and practice of basic concepts and techniques in algorithms. The course covers mathematical induction, techniques for analyzing algorithms, elementary data structures, major algorithmic paradigms such as dynamic programming, sorting and searching, and graph algorithms.Content
Mathematical Induction
- Mathematical background, Euler's formula for trees, Schwartz-Zippel lemma.
Analysis of Algorithms
- O-notation, time and space complexity, recurrence relations, probabilistic analysis.
Data structures
- Arrays, linked lists, trees, heaps, hashing, graphs.
Design of algorithms by induction
- Evaluating polynomials, divide-and-conquer algorithms, dynamic programming.
Greedy Algorithms
- Spanning tree and shortest path algortihms
Sorting and searching
- Merge sort, bucket sort, quicksort, heapsort, binary search.
Graphs algorithms and data structures
- Graphs traversals, shortest paths, spanning trees, transitive closure, decompostitions, matching, network flows.
Complexity
- Polynomial reductions, NP-completeness.
Keywords
algorithms, data structures, efficiency, problem solving
Learning Prerequisites
Recommended courses
Discrete Structures
Learning Outcomes
By the end of the course, the student must be able to:- Illustrate the execution of algorithms on example inputs
- Describe basic data structures such as arrays, lists, stacks, queues, binary search trees, heaps, and hash tables
- Analyze algorithm efficiency
- Compare alternative algorithms and data structures with respect to efficiency
- Choose which algorithm or data structure to use in different scenarios
- Use algorithms and data structures taught in the course on concrete problem instances
- Design new algorithms and data structures based on known methods
- Prove the correctness of an algorithm
Teaching methods
Ex cathedra lecture, exercises in classroom
Assessment methods
Continuous assessment with final exam.
Resources
Bibliography
Thomas Cormen, Charles Leiserson, Ronald Rivest, Clifford Stein: Introduction to algorithms, Third Edition, MIT Press, 2009.
Ressources en bibliothèque
Websites
Dans les plans d'études
- SemestreAutomne
- Forme de l'examenEcrit
- Crédits
6 - Matière examinée
Algorithms - Cours
4 Heure(s) hebdo x 14 semaines - Exercices
2 Heure(s) hebdo x 14 semaines
- Semestre
- SemestreAutomne
- Forme de l'examenEcrit
- Crédits
6 - Matière examinée
Algorithms - Cours
4 Heure(s) hebdo x 14 semaines - Exercices
2 Heure(s) hebdo x 14 semaines
- Semestre
- Passerelle HES - IN, 2017-2018, Semestre automne
- SemestreAutomne
- Forme de l'examenEcrit
- Crédits
6 - Matière examinée
Algorithms - Cours
4 Heure(s) hebdo x 14 semaines - Exercices
2 Heure(s) hebdo x 14 semaines
- Semestre
- Passerelle HES - SC, 2017-2018, Semestre automne
- SemestreAutomne
- Forme de l'examenEcrit
- Crédits
6 - Matière examinée
Algorithms - Cours
4 Heure(s) hebdo x 14 semaines - Exercices
2 Heure(s) hebdo x 14 semaines
- Semestre
- SemestreAutomne
- Forme de l'examenEcrit
- Crédits
6 - Matière examinée
Algorithms - Cours
4 Heure(s) hebdo x 14 semaines - Exercices
2 Heure(s) hebdo x 14 semaines
- Semestre
- SemestreAutomne
- Forme de l'examenEcrit
- Crédits
6 - Matière examinée
Algorithms - Cours
4 Heure(s) hebdo x 14 semaines - Exercices
2 Heure(s) hebdo x 14 semaines
- Semestre
- SemestreAutomne
- Forme de l'examenEcrit
- Crédits
6 - Matière examinée
Algorithms - Cours
4 Heure(s) hebdo x 14 semaines - Exercices
2 Heure(s) hebdo x 14 semaines
- Semestre
- SemestreAutomne
- Forme de l'examenEcrit
- Crédits
6 - Matière examinée
Algorithms - Cours
4 Heure(s) hebdo x 14 semaines - Exercices
2 Heure(s) hebdo x 14 semaines
- Semestre
- SemestreAutomne
- Forme de l'examenEcrit
- Crédits
6 - Matière examinée
Algorithms - Cours
4 Heure(s) hebdo x 14 semaines - Exercices
2 Heure(s) hebdo x 14 semaines
- Semestre
Semaine de référence
Lu | Ma | Me | Je | Ve | |
---|---|---|---|---|---|
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 |
En construction
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