teaching:ads12324_lecture
Rozdíly
Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.
Obě strany předchozí revizePředchozí verzeNásledující verze | Předchozí verze | ||
teaching:ads12324_lecture [2024/04/26 00:06] – Martin Koutecky | teaching:ads12324_lecture [2024/05/29 20:41] (aktuální) – Martin Koutecky | ||
---|---|---|---|
Řádek 20: | Řádek 20: | ||
| 16. 4. | $(a, | | 16. 4. | $(a, | ||
| 23. 4. | Brief mention of amortized analysis: expanding arrays can do $n$ INSERT / DELETE operations in time $O(n)$ (but not each operation is $O(1)$) [[https:// | | 23. 4. | Brief mention of amortized analysis: expanding arrays can do $n$ INSERT / DELETE operations in time $O(n)$ (but not each operation is $O(1)$) [[https:// | ||
- | | 30. 4. | // | + | | 30. 4. | Master theorem |
+ | | 7. 5. | Finding | ||
+ | | 14. 5. | //No lecture!// | ||
+ | | 21. 5. | dynamic programming - edit distance, Floyd-Warshall, | ||
- | /* | ||
- | |||
- | | 27. 4. | Universal, perfect hashing [[https:// | ||
- | | 4. 5. | Divide & conquer -- Karatsuba' | ||
- | | 18. 5. | Sorting lower bound [[https:// | ||
- | */ | ||
- | |||
{{page> | {{page> | ||
- | {{ :teaching:ads12122:exam2122.pdf | Exam topics and format | + | {{ :teaching:ads12324:exam2324.pdf | Exam topics and format (PDF).}} |
- | /* | + | ====== ADS1 Exam / 2024 ====== |
- | ====== ADS1 Exam / 2022 ====== | + | |
The exam will consist of: | The exam will consist of: | ||
- | - Two questions about an algorithm or a data structure from the lecture | + | 1. Two questions about an algorithm or a data structure from the lecture |
- | | + | 2. Two tasks similar to those from the tutorial |
+ | |||
+ | The form of the exam is that you will come, get the question sheet, and work on the answers. Once you are finished with one of the answers, you hand it in, I (or one of my colleagues) will read it, point out anything which is missing / incorrect, give you hints if needed, and you can revise it. | ||
+ | At some point either you will reach a correct solution, or you won't want to try to improve it again, or I will feel like I can't give you any more hints, and then we'll reach some grade. | ||
- | The form of the exam is that you will come, get the question sheet, and work on the answers. Once you are finished with one of the answers, you hand it in, I will read it, point out anything which is missing / incorrect, give you hints if needed, and you can revise it. At some point either you will reach a correct solution, or you won’t want to try to improve it again, or I will feel like I can’t give you any more hints, and then we’ll reach some grade. | ||
==== Grading ==== | ==== Grading ==== | ||
- | **To get a 3** it suffices to know definitions and algorithms / data structures and (with hints) finish at least one of the “type 2” tasks (perhaps suboptimally). | + | **To get a 3** it suffices to know definitions and algorithms / data structures and (with hints) finish at least one of the "type 2" |
- | **To get a 2** you need to be able to solve the tasks with some hints, or find a suboptimal (complexity) algorithm. If we proved some intermediate claims during the lecture, and these are used in the proofs of correctness/ | + | **To get a 2** you need to be able to solve the tasks with some hints, or find a suboptimal (complexity-wise) algorithm. |
+ | If we proved some intermediate claims during the lecture, and these are used in the proofs of correctness/ | ||
+ | |||
+ | **To get a 1** you need to analyze the algorithms (correctness and complexity) including the proofs, and you need to be able to solve the "type 2" tasks mostly independently. (Advice like "try dynamic programming" | ||
- | **To get a 1** you need to analyze the algorithms (correctness and complexity) including the proofs, and you need to be able to solve the “type 2” tasks mostly independently. (Advice like “try dynamic programming” and similar is still fine though.) | ||
===== Topics ===== | ===== Topics ===== | ||
- | **Disclaimer: | + | **Disclaimer: |
* BFS, DFS and their edge classifications | * BFS, DFS and their edge classifications | ||
* DFS applications: | * DFS applications: | ||
- | * Dijkstra’s algorithm | + | * 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) |
- | * Jarník’s algorithm | + | * Jarník's algorithm; cut lemma |
- | * Borůvka’s algorithm | + | * Borůvka's algorithm |
- | * Kruskal’s algoritmus + Union-Find data structure using trees | + | * Kruskal's algoritmus + Union-Find data structure using trees |
* Binary Search Trees (BSTs) in general | * Binary Search Trees (BSTs) in general | ||
* AVL trees | * AVL trees | ||
* $(a, | * $(a, | ||
- | | + | * Hashing with chaining (each bucket is a linked list) |
- | | + | |
- | * Hashing with open addressing | + | |
* Universal hashing | * Universal hashing | ||
- | * Master theorem | + | * Master theorem |
- | * Integer multiplication using Karatsuba’s algorithm | + | * Integer multiplication using Karatsuba's algorithm |
* MomSelect (finding the $k$-th smallest element in an array in linear time) | * MomSelect (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 | * 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/ads12324_lecture.1714082809.txt.gz · Poslední úprava: 2024/04/26 00:06 autor: Martin Koutecky