by csurosm

Liste de sujets et disponibilité

J’ai compilé la liste définitive de sujets pour l’examen final: notes15-final.

You can find the list of subjects for the final exam / pré-doc here: notes15-final.

Je suis disponible mercredi 9:30–11, 14:00–15:00 et jeudi 9:30–11:30 pour discussions: SVP réservez votre créneau à http://doodle.com/poll/h76znxxuc8tk4dqy

You can schedule a meeting with me Wednesday 9:30–11am, 2–4pm and Thursday 9:30–11:30am at http://doodle.com/poll/h76znxxuc8tk4dqy.

by csurosm

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
by csurosm

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