Rozdíly

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

--- teaching:ads12526_lecture [2026/05/08 09:28] – exam Martin Koutecky
+++ teaching:ads12526_lecture [2026/05/11 14:04] (aktuální) – Martin Koutecky
@@ Řádek 22: / Řádek 22: @@
 | 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. | 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. | //Plan: 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]**, start dynamic programming **[ALG 12]**.//
+| 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 72: / Řá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 79: / Řá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
@@ Řádek 87: / Řádek 91: @@
   * 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) */