Differences
This shows you the differences between two versions of the page.
Both sides previous revisionPrevious revisionNext revision | Previous revisionLast revisionBoth sides next revision | ||
21cs300 [2021-03-11] – [Introduction to Algorithms (CS300) in Spring 2021 at KAIST's School of Computing] HyunWoo Lee | 21cs300 [2021-12-28] – [Introduction to Algorithms (CS300) in Fall 2021 at KAIST's School of Computing] Martin Ziegler | ||
---|---|---|---|
Line 1: | Line 1: | ||
- | ====== Introduction to Algorithms (CS300) in Spring | + | ====== Introduction to Algorithms (CS300) in Fall 2021 at KAIST' |
- | All Computer Science is based on the concept of an efficient algorithm: a finite sequence of primitive instructions that, when executed according to their well-specified semantics, provably provide a mechanical solution to the infinitely many instances of a complex mathematical problem within a guaranteed number of steps of least asymptotic growth. We thus call these the ' | + | All Computer Science is based on the concept of an efficient algorithm: a finite sequence of primitive instructions that, when executed according to their well-specified semantics, provably provide a mechanical solution to the infinitely many instances of a complex mathematical problem within a guaranteed number of steps of least asymptotic growth. We thus call these ' |
* full and unambiguous problem specification | * full and unambiguous problem specification | ||
* | * | ||
- | * | + | * |
* and analysis (correctness, | * and analysis (correctness, | ||
* with proof of asymptotic optimality. | * with proof of asymptotic optimality. | ||
- | We will learn all about important basic algorithms and their analysis. | + | We will learn all about important basic algorithms and their analysis, |
+ | as well as the difference to heuristics or programs/ | ||
Their practical impact is demonstrated in selected implementations. | Their practical impact is demonstrated in selected implementations. | ||
Lecturer: Martin Ziegler | Lecturer: Martin Ziegler | ||
- | Lectures: online via //Zoom// <del>classroom #1501 in building | + | Lectures: online via //Zoom// < |
- | Schedule: Tuedays and Thursdays, | + | Schedule: Tuedays and Thursdays, |
Language: English __only__ (except for students discussing in KLMS) | Language: English __only__ (except for students discussing in KLMS) | ||
- | Teaching Assistants: | + | Teaching Assistants: |
+ | Hyeonguk Ryu, Jaejun Lee, Jihoon Hyun, Kyounga Woo, Minjae Park, Mukhtar Kussaiynbekov, Seungjin Baek, Taeyoung Kim, Yeonghun Kim, Yoonsung Choi | ||
- | Office hours: | + | Office hours: |
Quiz: On randomly selected sessions we will perform a short online quiz. | Quiz: On randomly selected sessions we will perform a short online quiz. | ||
- | Grading: | + | Grading: |
+ | Retakers admitted to improve grades C-,D,F; not to improve grades C0 and C+. | ||
Recommended background: CS204 (Discrete Mathematics), | Recommended background: CS204 (Discrete Mathematics), | ||
- | Philosophy: Education is a Human Right, not a competition. | + | Philosophy: Education is a Human Right, not a competition. |
- | This course aims // | + | This course aims //beyond//, and takes for granted students mastering, |
====== Homework/ | ====== Homework/ | ||
Line 41: | Line 44: | ||
===== Academic Honesty: ===== | ===== Academic Honesty: ===== | ||
- | Late homework submissions (until 7pm) will receive a 50% penalty. \\ | + | <del>Late homework submissions (until 7pm) will receive a 50% penalty. </ |
+ | We do not accept late submissions. \\ | ||
Copied solutions receive 0 points and personal interrogation during office/ | Copied solutions receive 0 points and personal interrogation during office/ | ||
Cheating during the exam results in failed grade //F//. \\ | Cheating during the exam results in failed grade //F//. \\ | ||
Line 66: | Line 70: | ||
* Optimal efficiency | * Optimal efficiency | ||
* Operational primitives | * Operational primitives | ||
+ | * Five algorithms for computing Fibonacci Numbers | ||
* Recurrences and the //Master Theorem// | * Recurrences and the //Master Theorem// | ||
* Polynomial Multiplication: | * Polynomial Multiplication: | ||
Line 75: | Line 80: | ||
* Median/ | * Median/ | ||
* 1D Range Counting | * 1D Range Counting | ||
+ | * 2D Range Counting | ||
- Sorting ({{ : | - Sorting ({{ : | ||
* Bubble Sort | * Bubble Sort | ||
Line 81: | Line 87: | ||
* Merge Sort | * Merge Sort | ||
* Quicksort | * Quicksort | ||
- | * Linear-Time Median | + | * {{ : |
* Optimality of Sorting | * Optimality of Sorting | ||
* Counting Sort | * Counting Sort | ||
* Radix Sort | * Radix Sort | ||
- | | + | * Sorting in Parallel |
+ | | ||
+ | * Hardware vs. Mathematical | ||
+ | * Logical Structures = Abstract Data Types | ||
+ | * Basic: Boolean/ | ||
+ | * Derived: Array, | ||
+ | * Linked Data Structures | ||
+ | * (Balanced) Search Trees | ||
+ | * AVL Trees | ||
+ | - Graphs ({{ : | ||
* Recap on Graphs: un/ | * Recap on Graphs: un/ | ||
* Connectedness | * Connectedness | ||
Line 93: | Line 108: | ||
* Max. bipartite matching | * Max. bipartite matching | ||
* Min-Cut | * Min-Cut | ||
- | - Strings ({{ :21cs300e.pdf |pdf}},{{ :21cs300e.ppt |ppt}}) | + | - Strings ({{ :21cs300f.pdf |pdf}},{{ :21cs300f.ppt |ppt}}) |
* Terminology | * Terminology | ||
* Pattern matching: Knuth-Morris-Pratt | * Pattern matching: Knuth-Morris-Pratt | ||
Line 100: | Line 115: | ||
* Parsing: Cocke-Younger-Kasami | * Parsing: Cocke-Younger-Kasami | ||
* Huffman Compression | * Huffman Compression | ||
- | - Paradigms ({{ :21cs300f.pdf |pdf}},{{ :21cs300f.ppt |ppt}}) | + | - Paradigms ({{ :21cs300g.pdf |pdf}},{{ :21cs300g.ppt |ppt}}) |
* Divide and Conquer | * Divide and Conquer | ||
* Dynamic Programming | * Dynamic Programming | ||
Line 106: | Line 121: | ||
* Backtracking | * Backtracking | ||
* Branch and Bound | * Branch and Bound | ||
+ | - Randomization ({{ : | ||
+ | * Un/ | ||
+ | * Sources of Randomness | ||
+ | * Las Vegas vs. Monte Carlo | ||
+ | * Primality Testing | ||
+ | * Errors and Amplification | ||
+ | * Blackbox Polynomial Test | ||
+ | * Schwartz-Zippel Lemma | ||
===== E-Learning: ===== | ===== E-Learning: ===== | ||
- | * homework assignment #0 and honor code will be uploaded | + | * homework assignment #0 and honor code will be uploaded |
- | * [[https:// | + | * [[https:// |
- | * [[https:// | + | * [[https:// |
+ | * [[https:// | ||
* [[https:// | * [[https:// | ||
- | * Due to the large number (>200) of students enrolled, we unfortunately cannot answer questions by email. \\ Instead please use the KLMS Bulletin Board or visit the TAs during their office hours. | + | * Due to the large number (>300) of students enrolled, we unfortunately cannot answer questions by email. \\ Instead please use the KLMS Bulletin Board or visit the TAs during their office hours. |
* We use [[https:// | * We use [[https:// |