Nous illustrons notre approche de base du développement et de l'analyse des algorithmes en examinant le problème de la connectivité dynamique. Nous présentons le type de données union-find et examinons plusieurs implémentations (recherche rapide, union rapide, union rapide pondérée et union rapide pondérée avec compression de chemin). Enfin, nous appliquons le type de données union-find au problème de percolation de la chimie physique.

Notre approche de l'analyse des performances des algorithmes repose sur la méthode scientifique. Nous commençons par réaliser des expériences informatiques pour mesurer les temps d'exécution de nos programmes. Nous utilisons ces mesures pour élaborer des hypothèses sur les performances. Ensuite, nous créons des modèles mathématiques pour expliquer leur comportement. Enfin, nous envisageons d'analyser l'utilisation de la mémoire de nos programmes Java.

Nous considérons deux types de données fondamentaux pour le stockage de collections d'objets : la pile et la file d'attente. Nous mettons en œuvre chacun de ces types de données en utilisant soit une liste à lien unique, soit un tableau de redimensionnement. Nous introduisons deux fonctionnalités Java avancées - les génériques et les itérateurs - qui simplifient le code client. Enfin, nous examinons diverses applications des piles et des files d'attente, allant de l'analyse d'expressions arithmétiques à la simulation de systèmes de files d'attente.

Nous présentons le problème du tri et l'interface Comparable de Java. Nous étudions deux méthodes de tri élémentaires (tri par sélection et tri par insertion) et une variante de l'une d'entre elles (shellsort). Nous considérons également deux algorithmes pour mélanger uniformément un tableau. Nous concluons par une application du tri au calcul de la coque convexe via l'algorithme de balayage de Graham.

Nous étudions l'algorithme mergesort et montrons qu'il garantit le tri de tout tableau de n éléments avec au plus n lg n comparaisons. Nous considérons également une version ascendante non récursive. Nous prouvons que tout algorithme de tri basé sur les comparaisons doit effectuer au moins n lg n comparaisons dans le pire des cas. Nous discutons de l'utilisation de différents ordonnancements pour les objets que nous trions et du concept connexe de stabilité.

Nous introduisons et mettons en œuvre l'algorithme de tri aléatoire et analysons ses performances. Nous étudions également l'algorithme randomisé quickselect, une variante du tri sélectif qui permet de trouver le kème élément le plus petit en temps linéaire. Enfin, nous étudions le tri sélectif à trois voies, une variante du tri sélectif qui fonctionne particulièrement bien en présence de clés dupliquées.

Nous présentons le type de données de la file d'attente prioritaire et une implémentation efficace utilisant la structure de données du tas binaire. Cette implémentation conduit également à un algorithme de tri efficace connu sous le nom de heapsort. Nous concluons par une application des files d'attente prioritaires dans laquelle nous simulons le mouvement de n particules soumises aux lois de la collision élastique.

Nous définissons une API pour les tables de symboles (également appelées tableaux associatifs, cartes ou dictionnaires) et décrivons deux implémentations élémentaires utilisant un tableau trié (recherche binaire) et une liste non ordonnée (recherche séquentielle). Lorsque les clés sont comparables, nous définissons une API étendue qui inclut les méthodes supplémentaires min, max floor, ceiling, rank et select. Pour développer une implémentation efficace de cette API, nous étudions la structure de données de l'arbre de recherche binaire et analysons ses performances.

Dans ce cours, notre objectif est de développer une table de symboles avec des performances logarithmiques garanties pour la recherche et l'insertion (et beaucoup d'autres opérations). Nous commençons par 2-3 arbres, qui sont faciles à analyser mais difficiles à implémenter. Ensuite, nous considérons les arbres de recherche binaires rouge-noir, que nous considérons comme une nouvelle façon d'implémenter les arbres 2-3 en tant qu'arbres de recherche binaires. Enfin, nous présentons les arbres B, une généralisation des arbres 2-3 qui sont largement utilisés pour mettre en œuvre les systèmes de fichiers.

Nous commençons par la recherche d'intervalles 1d et 2d, où le but est de trouver tous les points dans un intervalle 1d ou 2d donné. Pour ce faire, nous considérons les kd-arbres, une généralisation naturelle des BST lorsque les clés sont des points dans le plan (ou des dimensions supérieures). Nous considérons également les problèmes d'intersection, où le but est de trouver toutes les intersections parmi un ensemble de segments de lignes ou de rectangles.

Nous commençons par décrire les propriétés souhaitables des fonctions de hachage et la manière de les mettre en œuvre en Java, y compris un principe fondamental connu sous le nom d'hypothèse de hachage uniforme qui sous-tend le succès potentiel d'une application de hachage. Nous examinons ensuite deux stratégies de mise en œuvre des tables de hachage - le chaînage séparé et le sondage linéaire. Ces deux stratégies permettent d'obtenir des performances en temps constant pour la recherche et l'insertion dans le cadre de l'hypothèse de hachage uniforme.

Nous examinons diverses applications des tables de symboles, notamment les ensembles, les clients de dictionnaires, les clients d'indexation et les vecteurs épars.