Differences
This shows you the differences between two versions of the page.
Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
23cs500 [2023-06-12] – [Synopsis] Martin Ziegler | 23cs500 [2024-03-31] (current) – [Synopsis] Martin Ziegler | ||
---|---|---|---|
Line 1: | Line 1: | ||
====== Design and Analysis of Algorithms (CS500) in Spring 2023 at KAIST' | ====== Design and Analysis of Algorithms (CS500) in Spring 2023 at KAIST' | ||
- | All Computer Science is based on the concept of an efficient algorithm: | + | All Computer Science is based on the concept of an efficient |
+ | We thus call these ' | ||
* | * | ||
* | * | ||
- | * | + | * |
* and analysis (correctness, | * and analysis (correctness, | ||
* with proof of optimality. | * with proof of optimality. | ||
Line 11: | Line 12: | ||
==== Synopsis ==== | ==== Synopsis ==== | ||
Building on undergraduate [[22cs300|CS300 (Introduction to Algorithms)]], | Building on undergraduate [[22cs300|CS300 (Introduction to Algorithms)]], | ||
- | advanced aspects of algorithms. | + | //advanced// aspects of algorithms. |
- | More specifically we discuss, design, and analyze algorithms with respect to various __cost__ measures //beyond// (sequential) runtime, | + | More specifically we discuss, design, and analyze algorithms with respect to various __cost__ measures // |
such as | such as | ||
* memory, | * memory, | ||
- | * parallel time, | + | * parallel time/depth, |
- | * | + | * |
- | * communication volume etc. \\ | + | * communication volume, |
- | And we discuss, design, and analyze algorithms in various __modes__ //beyond// the worst-case, | + | * #coin flips etc. \\ |
+ | And we discuss, design, and analyze algorithms in various __modes__ //beyond// the traditional | ||
such as | such as | ||
* average-case, | * average-case, | ||
* expected, | * expected, | ||
* amortized, | * amortized, | ||
- | * competitive etc. \\ | + | * competitive |
+ | * approx. ratio etc. \\ | ||
The practical impact of these algorithms is demonstrated in selected implementations. | The practical impact of these algorithms is demonstrated in selected implementations. | ||
Line 67: | Line 70: | ||
3. Average-Case Analysis ({{: | 3. Average-Case Analysis ({{: | ||
4. Amortized Analysis ({{: | 4. Amortized Analysis ({{: | ||
- | 5. Randomization | + | 5. Randomized/ |
- | 6. Online/ | + | 6. Online/ |
7. P/NP Intermission ({{: | 7. P/NP Intermission ({{: | ||
8. Approximation | 8. Approximation |