Fiche de cours

Algorithms

CS-250

icon pdfFiche de cours

Enseignant(s) :

Svensson Ola Nils Anders

Langue:

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.

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

  • 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.

 

Keywords

algorithms, data structures, efficiency, problem solving

Learning Prerequisites

Recommended courses

Advanced ICC I

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

Dans les plans d'études

  • Informatique, 2021-2022, Bachelor semestre 3
    • Semestre
       Automne
    • Forme de l'examen
       Ecrit
    • Crédits
      6
    • Matière examinée
      Algorithms
    • Cours
      4 Heure(s) hebdo x 14 semaines
    • Exercices
      2 Heure(s) hebdo x 14 semaines
    • Type
      obligatoire
  • Mathématiques, 2021-2022, Bachelor semestre 5
    • Semestre
       Automne
    • Forme de l'examen
       Ecrit
    • Crédits
      6
    • Matière examinée
      Algorithms
    • Cours
      4 Heure(s) hebdo x 14 semaines
    • Exercices
      2 Heure(s) hebdo x 14 semaines
    • Type
      optionnel
  • Passerelle HES - IN, 2021-2022, Semestre automne
    • Semestre
       Automne
    • Forme de l'examen
       Ecrit
    • Crédits
      6
    • Matière examinée
      Algorithms
    • Cours
      4 Heure(s) hebdo x 14 semaines
    • Exercices
      2 Heure(s) hebdo x 14 semaines
    • Type
      obligatoire
  • Passerelle HES - SC, 2021-2022, Semestre automne
    • Semestre
       Automne
    • Forme de l'examen
       Ecrit
    • Crédits
      6
    • Matière examinée
      Algorithms
    • Cours
      4 Heure(s) hebdo x 14 semaines
    • Exercices
      2 Heure(s) hebdo x 14 semaines
    • Type
      obligatoire
  • Science et ingénierie computationnelles, 2021-2022, Master semestre 1
    • Semestre
       Automne
    • Forme de l'examen
       Ecrit
    • Crédits
      6
    • Matière examinée
      Algorithms
    • Cours
      4 Heure(s) hebdo x 14 semaines
    • Exercices
      2 Heure(s) hebdo x 14 semaines
    • Type
      optionnel
  • Science et ingénierie computationnelles, 2021-2022, Master semestre 3
    • Semestre
       Automne
    • Forme de l'examen
       Ecrit
    • Crédits
      6
    • Matière examinée
      Algorithms
    • Cours
      4 Heure(s) hebdo x 14 semaines
    • Exercices
      2 Heure(s) hebdo x 14 semaines
    • Type
      optionnel
  • Systèmes de communication, 2021-2022, Bachelor semestre 3
    • Semestre
       Automne
    • Forme de l'examen
       Ecrit
    • Crédits
      6
    • Matière examinée
      Algorithms
    • Cours
      4 Heure(s) hebdo x 14 semaines
    • Exercices
      2 Heure(s) hebdo x 14 semaines
    • Type
      obligatoire
  • Cyber security minor, 2021-2022, Semestre automne
    • Semestre
       Automne
    • Forme de l'examen
       Ecrit
    • Crédits
      6
    • Matière examinée
      Algorithms
    • Cours
      4 Heure(s) hebdo x 14 semaines
    • Exercices
      2 Heure(s) hebdo x 14 semaines
    • Type
      optionnel
  • Mineur en Informatique, 2021-2022, Semestre automne
    • Semestre
       Automne
    • Forme de l'examen
       Ecrit
    • Crédits
      6
    • Matière examinée
      Algorithms
    • Cours
      4 Heure(s) hebdo x 14 semaines
    • Exercices
      2 Heure(s) hebdo x 14 semaines
    • Type
      optionnel
  • Mineur en Systèmes de communication, 2021-2022, Semestre automne
    • Semestre
       Automne
    • Forme de l'examen
       Ecrit
    • Crédits
      6
    • Matière examinée
      Algorithms
    • Cours
      4 Heure(s) hebdo x 14 semaines
    • Exercices
      2 Heure(s) hebdo x 14 semaines
    • Type
      optionnel

Semaine de référence

 LuMaMeJeVe
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