The course presents the fundamental data structures as well as the associated algorithms.
Algorithm complexity is introduced. This is what makes it possible to study the efficiency and therefore the quality of an algorithmic solution. The concepts of pointers and recursion as well as the important data structures (such as lists, trees, hash tables ...) are deeply detailed.
This is what is taught in the ALSDD module at ESI in Algiers.
1) Preliminary concepts
- Course objectives (slides)
- Algorithms on Tables (slides)
- A brief introduction to C (slides)
- Memory allocation in C (slides)
- Complexity of iterative algorithms (slides)
(see examples of C programs)
2) Lists - (handout)
- Linked linear lists, Bi-directional lists, circular lists (slides)
- Examples: Merging lists (slides) and Fragmentation of lists (slides)
3) Queues and Stacks
- Implementation and examples (slides)
4) Recursion
- Concept of recursive algorithm, Design of recursive solutions (slides)
- Internal implementation of recursion (slides)
- Complexity of recursive algorithms (slides)
(see examples of C programs)
5) Tree data structure - (handout)
- Binary trees, general definitions (slides)
- Traversal and navigation algorithms (slides)
- Binary Search Trees (sildes)
- AVL trees (slides)
- M-ary trees, B-trees and 2-3-4 trees (slides)
- Red-Black trees and comparison with AVL (slides)
(see examples of C programs)
6) Hash tables
- Hash functions, Collision resolution during insertions (slides)
- Collision resolution during deletions (slides)
- Analytical estimation of overflows (slides)
الكلمات الرئيسية
الخوارزمية ، التعقيد الحسابي ، خوارزميات الفرز ، المتغير ، مؤشر، المتغير الديناميكي ، تخصيص الذاكرة ، هياكل البيانات: انظر الفصل 1
قوائم خطية مرتبطة ، قوائم ثنائية الاتجاه ، قوائم دائرية ، تنفيذ متجاور للقوائم: انظر الفصل 2
قوائم الانتظار ،المكدسات ،معالجة التعبيرات الحسابية ،تنفيذ قوائم الانتظار بواسطة الجداول الدائرية: انظر الفصل 3
العودية ، تصميم الخوارزميات العودية ، تنفيذ العودية ، التحويل إلى خوارزميات غير عودية ، إزالة استدعاءات الإجراءات العودية ، تعقيد الخوارزميات العودية ، خوارزمية الدمج والفرز: انظر الفصل 4
الأشجار ، الأشجار الثنائية ،أشجار البحث الثنائية ، الأشجار المتوازنة ، عمليات الدوران ، اجتياز الأشجار ، الاجتياز حسب المستويات ، التنفيذ المتجاور للأشجار ، التمثيلات المتسلسلة ، التنفيذ الفعال لقوائم الانتظار ذات الأولوية: انظر الفصل 5
التجزئة ، جداول التجزئة ، طرق حل التصادم ، الفحص الخطي ، التجزئة المزدوجة ، التسلسل المنفصل ، التسلسل الداخلي ، التقدير التحليلي للتدفق الزائد: انظر الفصل 6
Mot-clés (fr)
algorithme, complexité algorithmique, algorithmes de tri d’un tableau, variable, pointeur, variable dynamique, allocation mémoire, structures de données : voir chapitre 1
listes linéaires chaînées , listes bidirectionnelles, listes circulaires, implémentation contiguë des listes : voir chapitre 2
files , piles , manipulations des expressions arithmétiques, implémentation des files par tableaux circulaires : voir chapitre 3
récursivité, conception d’algorithmes récursifs, mise en œuvre de la récursivité, transformation en algorithmes non récursifs, élimination des appels récursifs, complexité des algorithmes récursifs, algorithme de tri par fusions : voir chapitre 4
arbres, arbres binaires, arbres de recherches binaires , arbres équilibrés, arbres AVL, arbres rouge-noir, opérations de rotation, parcours d’arbres, inordre, préordre, postordre, parcours par niveaux, implémentation contiguë des arbres, représentations séquentielles, arbres de Huffman, les tas, implémentation efficace des files de priorité : voir chapitre 5
hachage, tables de hachage, fonctions de hachage, méthodes de résolution de collisions, essai linéaire, double hachage, chaînage séparé, chaînage interne, estimation analytique des débordement : voir chapitre 6