Programmation efficace
Modal INF441

 Ce cours entraine les étudiants au concours de programmation ACM, et fait un survol d'un grand nombre d'algorithmes.

cours: Christoph Dürr
exercices: Steve Oudot
.
..

Informations

salle PC 20 de 10h30 à12h et 13h30 à 15h00, ensuite en salle informatique 35 de 15h30 à17h45

Si vous n'êtes pas inscrit au Modal, mais voulez quand même participer au concours ACM, alors inscrivez vous ici. Vous serez informé du lieu, l'heure et des modalitées. Merci. Et contactez le binet ACM.

Documents

Livres: Liens: Programmes:

01 | Ve 03/02 Introduction

[exploration avec backtracking]
Inscrivez vous ici (site 'C')
  1. [C] A + B Problem
  2. [C] The Triangle Game
  3. [C] Sudoku 9x9
  4. [D] [C] Sudoku 16x16 -- in,out
  5. [C] T9
Ajout: d'après cet article, pour Sudoku, la recherche locale est moins efficace que l'algorithme des liens dansants.

02 | Ve 10/02 algorithmes gloutons

[comment trier, union-find, codes de Huffman]
Note sur le site de Zhejiang [C]: il répond Runntime Error si votre programme comporte des throw new Error(..), ou des assert(..), même avant que ces instructions soient exécutées.
  1. [C] The Circumference of the Circle
  2. [T] [C] [D] Networking
  3. [T] [D] Variable Radix Huffman Encoding
  4. [T] [C] [D] Advanced ASCII Cubes
  5. [T] [D] Magic Sticks Again
  6. [G] Rotate
  7. [C] [D] Huffman Trees (help needed!)

03 | Ve 17/02 programmation dynamique


  1. [C] [D] Longest Ordered Subsequence
  2. [T] [D] Tetris
  3. [C] [D] The Separator
  4. [C] [D] Common Subsequence
  5. [A] Stacking Boxes

04 | Ve 02/03 programmation dynamique

  1. [C] [D] Color a Tree
  2. [C] [D] Radar Installation
  3. [D] Is Bigger Smarter?
  4. [C] [D] To The Max
  5. [C] [D] Largest Rectangle in a Histogram
  6. [D] Homework
  7. [D] Playground
  8. [D] Binary Trees
Lisez ces exemples pour apprendre comment ne pas faire.

05 | Ve 09/03 calculer

  1. [B] Ars Longa
  2. [A] Editor Nottobad
  3. [C] [D] Tri Tiling
  4. [in/out] [D] Boolean Expresion
  5. [C] [D] Interpreter
  1. [C] [D] Spreadsheet
  2. [C] [D] Hexagonal Routes
  3. [C] Lazy Evaluation [D] Simplified λ-evalutations
  4. [D] Prime Gap
Voici des problèmes données pendant des entretiens d'embauche.

06 | Ve 16/03 exploration de graphes

  1. [C] [D] Finding Nemo
  2. [cache] [D] Mine
  3. [C] [D] Traffic Jam
  4. [C] [D] Street Directions
  5. [C] [D] Minesweeper
  6. [C] [D] Australian Voting
  7. [C] [D] The Trip
  8. [C] [D] LC Display

07 | Ve 30/03 couplages

Avant de commencer, vous devez, je dis bien, devez, répondre à ce questionnaire.
  1. [G] Egg Drop
  2. [C] [D] Courses
  3. [cache] [D] Poor Wenwen
  4. [C] [D] Pizza delivery
  5. [A] [D] Babel Towers
  6. [cache] [D] Make it Manhattan
  7. [A] Manhattan
Une suggestion de comment boucler en C++.

08 | Ve 06/04 géométrie

  1. [in/out] [C] [D] Herding Frosh
  2. [in/out] [H] [D] Rectilinear polygon
  3. [A] [D] Seminar Room
  4. [in/out] [X] [D] Line Segments
  5. [C] Heliport - difficile

09 | Ve 13/04 contrôle

matin sur papier, après-midi sur machine

Pendant l'examen vous pouvez ammener le poly et 25 pages de code ou de notes. Sur machine vous aurez accès aux documentation de l'API de JDK et de la STL.

Un lien sur la partie papier des examens passés est en tête de cette page. Les examens passés sur machine sont en bas de cette page à partir de DiskTree je crois. Utilisez le cache de google, pour retrouver les sujets.

** | problèmes choisis pour entrainment libre

  1. [A] TeX Quotes - c'est l'exercice HelloWord
  2. [A] The 3n + 1 problem - la difficultée réside dans la limite des nombres.
  3. [A] Check The Check (*) - organiser son programme
  4. [A] Cola - simulation, facile
  5. [A] The House Of Santa Claus - facile, exploration exhaustive
  6. [A] Robot Motion
  7. [A] Ordering Tasks
  8. [A] The Skyline Problem
  9. [A] What's Cryptanalysis? - comment trier des agrégats ?
  10. [A] Common Permutation - chaînes, facile
  11. [A] Network Connections - structure de données
  12. [A] Ananagrams - chaînes
  13. [A] Crypt Kicker (*) - chaînes, long
  14. [A] File Fragmentation - chaînes, simple
  15. [B] Game of Life
  16. [B] Containers
  17. [B] Consanguine Calculations
  18. [A] Minimal coverage
  19. [A] Add All
  20. [A] Freckles
  21. [A] Poker Hands (*)
  22. [B] Know When to Hold 'em
  23. [B] Huffman Trees (*)
  24. [A] Camel Trading
  25. [A] Troublemakers
  26. [A] The Base-1 Number System
  27. [A] Vacation
  28. [T] Count wireless Link
  29. [A] Chopsticks (*)
  30. [A] Antimonotonicity
  31. [A] Coin Changing Again
  32. [B] Brackets Removal
  33. [A] Summation of Four Primes
  34. [A] Factovisors
  35. [A] Euclid Problem
  36. [B] Low Cost Air Travel
  37. [A] Bicoloring
  38. [A] Dominant Strings
  39. [B] The mysterious X network - bon exemple pour comparer les vitesses de C++ de Java
  40. [A] Councilling
  41. [A] Crime Wave - The Sequel
  42. [A] Police Road Blocks [ce n'est pas dit dans l'énoncé, mais probablement le graphe est planaire, et alors peut appliquer l'algorithme de Reif en O(n log2 n)]
  43. [A] Transportation system
  44. [B] The Finest Chef
  45. [A] Isolated Segments
  46. [B] Rectangular Polygons
  47. [D] DiskTree
  48. [D] Optimal Array Multiplication Sequence
  49. [D] Incidental Points
  50. [D] Brackets sequence
  51. [D] Common item
  52. [D] Cryptoquote
  53. [D] Giant Screen
  54. [D] Feel Good
  55. [D] IP Networks
  56. [C] [D] Greatest Common Increasing Subsequence (**)
  57. [B] Rectangular Polygons
  58. [D] Strange Expression
  59. [D] Area of Polycubes
  60. [D] European railroad tracks