1IAB3 | Basics of algorithmics | Computer Science - Apprenticeship | S5 | ||||||
---|---|---|---|---|---|---|---|---|---|
Lessons : 10 h | TD : 10 h | TP : 0 h | Project : 0 h | Total : 20 h | |||||
Co-ordinator : Christine Porquet |
Prerequisite | |
---|---|
Course "Introduction to programming" | |
Course Objectives | |
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). | |
Syllabus | |
- 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. |
|
Practical work (TD or 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. |
|
Acquired skills | |
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. |
|
Bibliography | |
- 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 )