Dans ce module, l'étudiant apprendra les bases des structures de données qui organisent les données pour rendre certains types d'opérations plus rapides. Le module commence par une introduction générale aux structures de données et aborde quelques structures de données simples telles que les files d'attente premier entré-premier sorti et la pile dernier entré-premier sorti. Ensuite, nous introduisons la structure de données heap et les propriétés de base des heaps. Nous présentons ensuite les algorithmes d'insertion, de suppression et de recherche de l'élément minimum d'un tas, ainsi que leurs complexités temporelles. Enfin, nous étudierons la structure de données des files d'attente prioritaires et présenterons quelques applications.

Nous passerons en revue les algorithmes quicksort et quickselect pour trier et sélectionner efficacement le kème plus petit élément d'un tableau. Il s'agira également d'une introduction au rôle de la randomisation dans la conception des algorithmes. Ensuite, nous étudierons les tables de hachage : une structure de données très utile qui permet de rechercher et d'extraire efficacement de grandes quantités de données. Nous apprendrons les principes de base des tables de hachage et des opérations sur les tables de hachage.

Dans ce module, nous allons apprendre la sélection aléatoire de pivots pour le tri sélectif et la sélection rapide. Nous apprendrons à analyser la complexité des algorithmes randomisés quicksort/quickselect. Nous apprendrons le hachage d'adresses ouvertes : une technique qui simplifie la conception des tables de hachage. Ensuite, nous étudierons la conception des fonctions de hachage et leur analyse. Enfin, nous présenterons et analyserons les filtres de Bloom qui sont utilisés dans diverses applications telles que l'interrogation de données en continu et le comptage.