Aperçu des semaines

  • Cette semaine

    16-22/09/2019

    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, queues, rooted trees)
    • Dynamic arrays
  • 23-29/09/2019

    Divide and conquer (chap. 4, 30)

    • Divide and conquer (binary search, matrix multiplication)
    • Analysis of recursive algorithms
    • Master theorem
    • Fast multiplication of polynomials, discrete Fourier transform
    • 30-06/09/2019

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

      • Memoisation and dynamic programming
      • Greedy algorithms
      • Knapsack and NP-hardness
      • 07-13/10/2019

        Sorting algorithms (chap. 6-8)

        • Insertion sort
        • Merge sort
        • Quicksort
        • Heaps and heapsort
        • Lower bounds
        • Bucket sort
        • HW 1 Test
          Accès restreint Disponible à partir du 21 septembre 2019
      • 14-20/10/2019

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

        • Binary search trees
        • Red-black trees
        • Hashing
        • Open addressing
        • Bloom filter (*)
        • 21-27/10/2019

          Algorithms on strings (chap. 32)
          • Pattern matching
            • Naive
            • KMP
          • Dictionary look-up
            • Trie (*)
          • Multiple pattern matching
            • Aho-Corasick (*)
            • Suffix trees (*)
          • Automata



        • 11-17/11/2019

          Disjoint-set data structures (chap. 21)

          • Weighted union heuristic
          • Union by rank
          • Path compression
          • 18-24/11/2019

            Minimum-weight spanning trees (chap. 23)

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

            • 25-01/11/2019

              Depth-first search (chap. 22)

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

              • 02-08/12/2019

                Shortest paths (chap. 24)

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

              • 09-15/12/2019

                Flow networks (chap. 26)

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

                • 16-22/12/2019

                  Flow networks II (chap. 26)

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