Exercices: arbres et tas

J’ai préparé deux nouveaux jeux d’exercices:

Si vous travaillez sur un exercice ou deux, n’hésitez pas à venir me voir pour commentaires ou à en discuter ci-dessous. (Mais ne postez pas de solutions SVP.)

Publicités

Notes de cours № 8 (arbres) et № 9 (tas)

Note pré-doc / intra

Vous pouvez réservez un créneau de 10 minutes pour discuter votre intra à http://doodle.com/poll/ekzk25m55mgwubey. Si vous voulez juste consulter votre copie corrigée, venez pendant le temps affiché (lundi 11:30-13:00, mardi 10:30-11:30, jeudi 10-11) sans réservation.

You can reserve a time slot to discuss your mid-term/comprehensive exam at  http://doodle.com/poll/ekzk25m55mgwubey If you just want to consult your copy, come without reservation any time (Monday 11:30-13:00, Tuesday 10:30-11:30 or Thursday 10:00-11:00).

Arbres

Note 8 : notes08-trees

wikipedia logo Wikipedia

File de priorité / tas

Note 9: notes09-heap (Preuve de Théorème 9.1 fixée par rapport à l’énoncé original notes09-heap)

wikipedia logo Wikipedia

  • file de priorité EN
  • ordre de tas FR EN
  • tas binaire FR EN
  • tri par tas FR EN
  • tas d-aire EN

Expérimentation avec hachage coucou

Suppression impatiente

Notez que dans le code pour suppression impatiente, on réinsère les éléments après la case vidée (et non pas à partir de la première case identifiée à l’indice i=h(x).) Voir correction en Ligne S1 dans l’énoncé: devoir4.

Quant à la date de remise, vous ne serez pas pénalisé si vous soumettez avant le 17 novembre 20:15 (donc, avec un délai ≤ 72h).

Exemple avec hachage coucou

Pour illustrer ce qu’on veut faire en Devoir 4, voici mon expérimentation avec hachage coucou. C’est une structure très élégante, avec O(1) temps au pire pour recherche et suppression. Rasmus Pagh donne une bonne présentation en ligne sur l’idée.

  1. J’ai encodé la méthode dans la classe koekoeke.CuckooHashingSet:https://github.com/csurosm/Koekoeke/blob/master/src/koekoeke/CuckooHashingSet.java. La classe implémente l’interface de java.util.Set.
  2. J’ai modifié la source de SetTester pour utiliser CuckooHashingSet. En Ligne 480:
    Set<Object> trythis =  new koekoeke.CuckooHashingSet(); 
    
  3. J’ai lancé l’exécution après compilation dans la ligne de commande, 12 fois par taille testée:
    % bash -c 'for N in 65536 131072 262144 524288 1048576 2097152 4194304; do for rep in 1 2 3 4 5 6 7 8 9 10 11 12; do  java -Xmx2G -cp IFT2015-A16.jar SetTester ${N}; done; done' > timings.log 
    
  4. Afin d’importer les données dans un logiciel de feuille de calcul (Microsoft Excel ou Google Sheets), j’ai enlevé les lignes de remarques. (Dans la feuille, j’ai trié les rangées par les colonnes `Phase’ et ‘size’.)
    % grep -v '#' timings.log > timings.txt      
    
  5. J’ai répeté la procédure pour HashSet. Voici la combinaison des deux fichiers (avec 25 répétitions au lieu de 12):  Google spreadsheet. (Temps amorti rapporté dans phase `exec’, usage de mémoire dans phase `final’.)

cuckoo-timingscuckoo-memory

Devoir 3

Dans Devoir 3, on vérifie le paradoxe des anniversaires. Il s’agit de compiler la liste de joueurs sur un équipe de sport de votre préférence et compter les jumeaux astrologiques. (On attend que >50% des équipes de >23 joueurs ont des jumeaux astrologiques.)

Énoncé: devoir3. Notez que la soumission est par commentaire à ce message (non-anonyme, bien sûr!).

Mes disponibilités pour la semaine: mardi 11 octobre, 11-12:30 et jeudi 13 octobre, 10-11. Envoyez-moi un email pour autres temps.

Bonne fête à tout le monde!