Aperçu des semaines

  • Cette semaine

    27 and 28 September

    Introduction to algorithms and data structures (chap. 1-3, 10, 12, 17)

    • Algorithms
    • Asymptotic complexity in time and space 
    • Consequences in practice
    • Elementary data structures (arrays, lists, heaps, queues, binary search trees)
    • Dynamic arrays
  • 4 and 5 October

    Divide and conquer (chap. 4, 30)

    • Brute-force search
    • Divide and conquer (binary search, matrix multiplication)
    • Analysis of recursive algorithms
    • Master theorem
    • Fast multiplication of polynomials, discrete Fourier transform
    •  Homework 2 - Python Test
      Accès restreint Disponible à partir du 5 octobre 2018, 12:00
    •  Homework 2 - C++ Test
      Accès restreint Disponible à partir du 5 octobre 2018, 12:00
  • 11 and 12 October

    Dynamic programming and greedy algorithms (chap. 15, 16)

    • Memorisation and dynamic programming (change making problems, sequence alignment)
    • Greedy algorithms (knapsack)
    • Knapsack and NP-hardness
    •  Homework 3 - Python Test
      Accès restreint Disponible à partir du 12 octobre 2018, 12:00
    •  Homework 3 - C++ Test
      Accès restreint Disponible à partir du 12 octobre 2018, 12:00
  • 25 and 26 October

    Sorting algorithms (chap. 6-8)

    • Insertion sort
    • Merge sort
    • Quicksort
    • Heaps and heapsort
    • Lower bounds
    • Bucket sort
    •  Homework 4 - Python Test
      Accès restreint Disponible à partir du 26 octobre 2018, 12:00
    •  Homework 4 - C++ Test
      Accès restreint Disponible à partir du 26 octobre 2018, 12:00
  • 8 and 9 November

    Data structures for sets and hashing (chap. 11, 13)

    • Hashing
    • Open addressing
    • Red-black trees
    •  Homework 5 - Python Test
      Accès restreint Disponible à partir du 9 novembre 2018, 12:00
    •  Homework 5 - C++ Test
      Accès restreint Disponible à partir du 9 novembre 2018, 12:00
  • 15 and 16 November

    Disjoint-set data structures (chap. 21)

    • Weighted union heuristic
    • Union by rank
    • Path compression

    • 22 and 23 November

      Text algorithms (chap. 32)

      • Pattern matching
        • Naive
        • KMP
      • Dictionary look-up
        • Binary search tree, hashing
        • Bloom filter (*)
        • Trie (*)
      • Multiple pattern matching
        • Aho-Corasick (*)
        • Suffix trees (*)
      • Automata
      • 29 and 30 November

        Minimum spanning tree (chap. 23)

        • Priority queue
        • Kruskal’s algorithm
        • Prim’s algorithm

        • 6 and 7 December

          Depth-first search (chap. 22)

          • Depth-first search
          • Topological sort
          • Strongly connected components

          • 13 and 14 December

            Shortest paths (chap. 24)

            • Priority queues
            • Dijkstra’s algorithm
            • Bellman-Ford algorithm

            • 20 and 21 December

              Flow networks (chap. 26)

              • Max-flow min-cut theorem
              • Ford-Fulkerson algorithm

              • 10 and 11 January

                Flow networks II (chap. 26)

                • Edmonds-Karp algorithm (augmenting along the shortest path)
                • Scaling algorithm (*)