Home - Log in

Basics of algorithmics

1IAB2 Basics of algorithmics Computer Science - Apprentissage S5
Cours : 10 h TD : 10 h TP : 0 h Projet : 0 h Total : 20 h
Responsable : Christine Porquet
Pré-requis
Course "Introduction to programming"
Objectifs de l'enseignement
The course provides the necessary foundation for any future software developer: notions about the complexity of algorithms and survey of the various abstract data types and their associated algorithms (implemented in C).
Programme détaillé
- What is an algorithm?
- Worst-case and average-case complexity.
- Spatial and temporal complexity of algorithms: application to search and sort algorithms.
- Survey of the following data types: arrays, stacks and queues, linear lists chained, hash tables, heaps.
- Evaluation of the complexity of search / insert / delete operations on each of these data types.
Applications (TD ou TP)
- Experimental comparison of the complexity of various sorting algorithms (internal and external sorting).
- Recursion (stack of recursive function calls, principles of memo-functions).
- Stacks, queues, lists (ex: radix sort, handling arithmetic expressions).
- Heapsort, merging sorted files using a heap.
Compétences acquises
The student can assess the worst-case complexity of simple algorithms.
He/she is able to use advisedly the following abstract data types: arrays, stacks, queues, lists, hash tables and heaps and can efficiently implement them in C language.
Bibliographie
- Introduction à l'algorithmique. T. Cormen et al. - Dunod - 1994
- Types de données et algorithmes. C. Froidevaux et al. - Mc Graw-Hill - 1990
- Algorithmes et structures de données en langage C, (C ANSI et C++). L. Ammeraal – InterEditions -1996
- Le langage C, norme Ansi. B. Kernigham – Dunod – 2000

© 2024 - ENSICAEN ( Legal Notices - Credits )