Rozdíly

Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.

--- teaching:ads12526_lecture [2026/04/27 13:35] – 27. 4. lecture update, plan for 4. 5. Claude Cowork
+++ teaching:ads12526_lecture [2026/05/11 14:04] (aktuální) – Martin Koutecky
@@ Řádek 21: / Řádek 21: @@
 | 20. 4. | $(a,b)$-trees and brief mention of Left-Leaning Red-Black (LLRB) trees **[ALG 8.3]** ([[https://sedgewick.io/wp-content/themes/sedgewick/papers/2008LLRB.pdf|original LLRB paper]], [[https://sedgewick.io/wp-content/uploads/2022/03/2008-09LLRB.pdf|slides]], [[https://read.seas.harvard.edu/~kohler/notes/llrb.html|controversy]]). Tries **[ALG 4.3]**.|
 | 27. 4. | Hashing with chaining **[ALG 11.3]**, open addressing (linear probing, double hashing) **[ALG 11.4]**, universal hashing **[ALG 11.5]**. Brief mention of amortized complexity and expanding arrays **[ALG 9.1]**.|
-| 4. 5. | //Plan: Divide and conquer **[ALG 10]**.// |
+| 4. 5. | Divide and conquer: analysis of Mergesort via the substitution method and the recursion tree technique **[ALG 10.2]**, Karatsuba's algorithm for multiplication of $n$-digit numbers in time $\mathcal{O}(n^{\log_2 3})$ **[ALG 10.3]**, started the Master theorem **[ALG 10.4]** //(to be finished next time)//.|
+| 11. 5. | Finish Master theorem **[ALG 10.4]**. QuickSelect, QuickSort **[ALG 10.6-10.7]**, finding the $k$-th smallest element in linear time **[ALG 10.8]**|
+| 18. 5. | //Plan: dynamic programming: Longest Increasing Subsequence in $O(n \log n)$ time. Edit Distance in $O(nm)$. Floyd-Warshall algorithm for All-Pairs Shortest Paths (APSP). **[ALG 12]**, [[https://jeffe.cs.illinois.edu/teaching/algorithms/book/03-dynprog.pdf|JE 3]].//|
 /*
@@ Řádek 38: / Řádek 40: @@
 {{page>teaching:bits:resources_ads1}}
-/*
-{{ :teaching:ads12324:exam2324.pdf | Exam topics and format (PDF).}}
-====== ADS1 Exam / 2024 ======
+/* {{ :teaching:ads12324:exam2324.pdf | Exam topics and format (PDF).}} */
+====== ADS1 Exam / 2026 ======
 The exam will consist of:
@@ Řádek 71: / Řádek 73: @@
   * Dijkstra's algorithm, $d$-ary heaps
   * Bellman-Ford's algorithm
-  * Floyd-Warshall's algorithm (small topic)
+  * Floyd-Warshall's algorithm (small topic -- covered with dynamic programming)
   * Jarník's algorithm; cut lemma
   * Borůvka's algorithm
@@ Řádek 78: / Řádek 80: @@
   * AVL trees
   * $(a,b)$-trees
+  * Tries (FIND, INSERT, DELETE in $O(L)$ for a string of length $L$)
   * Hashing with chaining (each bucket is a linked list)
-  * Universal hashing
+    * Hashing with open addressing: just know that it exists, with various schemes (collisions are handled by putting elements elsewhere in the same array, not by creating a chain)
+  * Universal hashing -- construction of a $c$-universal family
+  * Expanding arrays -- brief mention, be able to prove that inserting $n$ elements into an expanding array (start from size 1, if it would overflow $\to$ double size and re-insert) takes time $O(n)$.
   * Master theorem -- analyzing the complexity of Divide & Conquer algorithms using the recursion tree
   * Integer multiplication using Karatsuba's algorithm
-  * MomSelect (finding the $k$-th smallest element in an array in linear time)
+  * LinearSelect (finding the $k$-th smallest element in an array in linear time)
   * QuickSelect with random pivots works in expected $\mathcal{O}(n)$ time, QuickSort with random pivots in expected $\mathcal{O}(n \log n)$ time.
   * Edit Distance dynamic programming algorithm
   * Longest Increasing Subsequence dynamic programming algorithm
-  * Lower bounds: searching in a sorted array is $\Omega(\log n)$, sorting is $\Omega(n \log n)$ (only applies to deterministic and comparison-based algorithms)
-*/
+/*  * Lower bounds: searching in a sorted array is $\Omega(\log n)$, sorting is $\Omega(n \log n)$ (only applies to deterministic and comparison-based algorithms) */