Differences
This shows you the differences between two versions of the page.
Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
22cs300 [2022-08-29] – [Introduction to Algorithms (CS300) in Fall 2022 at KAIST's School of Computing] Martin Ziegler | 22cs300 [2022-11-01] (current) – Martin Ziegler | ||
---|---|---|---|
Line 15: | Line 15: | ||
Lecturer: Martin Ziegler | Lecturer: Martin Ziegler | ||
- | Lecture | + | Lecture |
Schedule: Tuesdays and Thursdays, 10:30am to 12:00 KST | Schedule: Tuesdays and Thursdays, 10:30am to 12:00 KST | ||
Line 21: | Line 21: | ||
Language: English __only__ (except for students discussing in KLMS) | Language: English __only__ (except for students discussing in KLMS) | ||
- | Teaching Assistants: | + | Teaching Assistants: |
Office hours: TBD | Office hours: TBD | ||
Line 29: | Line 29: | ||
Recommended background: CS204 (Discrete Mathematics), | Recommended background: CS204 (Discrete Mathematics), | ||
- | Philosophy: Education is a Human Right, not a competition. \\ | + | |
+ | ===== Philosophy/Pedagogy ===== | ||
+ | |||
+ | Education is a Human Right, not a competition. \\ | ||
This course aims //beyond//, and takes for granted students mastering, the __first__ level of [[https:// | This course aims //beyond//, and takes for granted students mastering, the __first__ level of [[https:// | ||
- | ====== Homework/ | + | Each chapter (see #syllabus) below deliberately starts very easy and then grows to more involved aspects and ends with cross promotion to advanced topics covered by separate lectures. |
+ | |||
+ | ===== Homework/ | ||
Receptive learning and reproductive knowledge do not suffice for thorough understanding. Hence, for students' | Receptive learning and reproductive knowledge do not suffice for thorough understanding. Hence, for students' | ||
Line 59: | Line 65: | ||
===== Synopsis/ | ===== Synopsis/ | ||
- | - {{ : | + | - Introduction ({{ : |
+ | * Hierarchy of Abstraction | ||
* Virtues of Computer // | * Virtues of Computer // | ||
* Problem specification | * Problem specification | ||
Line 69: | Line 76: | ||
* Recurrences and the //Master Theorem// | * Recurrences and the //Master Theorem// | ||
* Polynomial Multiplication: | * Polynomial Multiplication: | ||
- | - Searching ({{ : | + | - Searching ({{ : |
* Linear Search | * Linear Search | ||
* Binary Search | * Binary Search | ||
* Uniqueness | * Uniqueness | ||
* Hashing | * Hashing | ||
- | * Median/Quantiles | + | * Median/Order Statistics |
+ | * Approximate/ | ||
* 1D Range Counting | * 1D Range Counting | ||
- | * 2D Range Counting | + | * 2D/3D Range Counting |
- | - Sorting ({{ : | + | * Range Reporting |
+ | - Sorting ({{ : | ||
* Bubble Sort | * Bubble Sort | ||
* Selection Sort | * Selection Sort | ||
Line 83: | Line 92: | ||
* 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 | * Sorting in Parallel | ||
- | - Data ({{ : | + | - Data ({{ : |
* Hardware vs. Mathematical | * Hardware vs. Mathematical | ||
* Logical Structures = Abstract Data Types | * Logical Structures = Abstract Data Types | ||
Line 96: | Line 105: | ||
* (Balanced) Search Trees | * (Balanced) Search Trees | ||
* AVL Trees | * AVL Trees | ||
- | - Graphs ({{ : | + | - Graphs ({{ : |
* Recap on Graphs: un/ | * Recap on Graphs: un/ | ||
* Connectedness | * Connectedness | ||
Line 128: | Line 137: | ||
* homework assignment #0 and honor code will be uploaded on KLMS. | * homework assignment #0 and honor code will be uploaded on KLMS. | ||
- | * [[https:// | + | * [[https:// |
- | * [[https:// | + | * [[https:// |
* [[https:// | * [[https:// | ||
* [[https:// | * [[https:// | ||
* 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. | * 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:// |