ECTS : 3
Volume horaire : 39
Description du contenu de l'enseignement :
Introduction: algorithms and their analysis.
Searching elements in an array: linear search, binary search (bissection), hashing.
Recursion: principle and limitations induced by the recursion stack.
Classical sorting algorithms: Insertion sort, merge sort, quicksort, heap sort and their respective complexity.
Data structures: heaps, stacks, queues, linked lists, hash tables. Short introduction to object oriented programming in Pyhton to ease the implementation of these data structures.
Compétence à acquérir :
This class covers algorithm design and performance analysis. It introduces various sorting algorithms, and data structures such as heaps, stacks, queues, linked lists and hash tables. Some basic elements of object-oriented programming are also introduced. Python is used to implement and illustrate the algorithms and data structures.
Mode de contrôle des connaissances :
Mid-terms exams and final exam.
Bibliographie, lectures recommandées :
Introduction to Algorithms, third or fourth edition, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein.
MIT Press.
Problem Solving with Algorithms and Data Structures, Release 3.0, Brad Miller, David Ranum, Franklin,
Beedle & Associates, ISBN 978-1590282571