MK's wiki

Uživatelské nástroje

Nástroje pro tento web

Historie:
teaching:ads12526_lecture

Rozdíly

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

Odkaz na výstup diff

Obě strany předchozí revizePředchozí verze
Následující verze		Předchozí verze
teaching:ads12526_lecture [2026/05/10 11:50] – [Topics] Martin Kouteckyteaching: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]**.| | 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)//.| | 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   * Dijkstra's algorithm, $d$-ary heaps
   * Bellman-Ford's algorithm   * 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   * Jarník's algorithm; cut lemma
   * Borůvka's algorithm   * Borůvka's algorithm
Řádek 90: Řádek 91:
   * Edit Distance dynamic programming algorithm   * Edit Distance dynamic programming algorithm
   * Longest Increasing Subsequence 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) */
  
  
teaching/ads12526_lecture.1778413845.txt.gz · Poslední úprava: autor: Martin Koutecky