Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revisionPrevious revision
Next revision
Previous revision
21cs300 [2021-02-26] – [E-Learning:] Martin Ziegler21cs300 [2022-02-09] (current) – [Literature:] Martin Ziegler
Line 1: Line 1:
-====== Introduction to Algorithms (CS300) in Spring 2021 at KAIST's School of Computing ======+====== Introduction to Algorithms (CS300) in Fall 2021 at KAIST's School of Computing ======
  
-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 'virtues' of Theoretical Computer Science:+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 'virtues' of Theoretical Computer Science:
  
   *     full and unambiguous problem specification   *     full and unambiguous problem specification
   *     formal semantics of operational primitives   *     formal semantics of operational primitives
-  *     algorithm design (as opposed to 'programming')+  *     algorithm design (as opposed to 'coding')
   *     and analysis (correctness, asymptotic cost)   *     and analysis (correctness, asymptotic cost)
   *     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/code.
 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 E3-1</del>+Lectures: online via //Zoom// <del>in building E11</del>
  
-Schedule: Tuedays and Thursdays, 9:00am to 10:15+Schedule: Tuedays and Thursdays, 17:30am to 19:00 KST
  
 Language: English __only__ (except for students discussing in KLMS) Language: English __only__ (except for students discussing in KLMS)
  
-Teaching Assistants: 우 (head), 임동현황지만 +Teaching Assistants: <del>임동현 (head)</del> Makenov  Arnur (head) \\  
 +Hyeonguk RyuJaejun Lee, Jihoon Hyun, Kyounga Woo, Minjae Park, Mukhtar Kussaiynbekov, Seungjin Baek, Taeyoung Kim, Yeonghun KimYoonsung Choi
  
-Office hours: TBD+Office hours: online
  
 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: The final grade will (essentially) be composed as follows: Homework 30%, Quizzes 10%, Midterm exam 30%, Final exam 30%.+Grading: Only //Pass/////Fail//, depending on Homework 30%, Quizzes+Attendance 10%, Midterm exam 30%, Final exam 30%.
  
 +Retakers admitted to improve grades C-,D,F; not to improve grades C0 and C+.
  
 Recommended background: CS204 (Discrete Mathematics), CS206 (Data Structures) Recommended background: CS204 (Discrete Mathematics), CS206 (Data Structures)
  
-Philosophy: Education is a Human Right, not a competition. +Philosophy: Education is a Human Right, not a competition. \\ 
-This course aims beyond knowledge for the second and third level of Bloom's Hierarchy of cognitive learning.+This course aims //beyond//, and takes for granted students mastering, the __first__ level of [[https://cft.vanderbilt.edu/guides-sub-pages/blooms-taxonomy/|Bloom's Hierarchy of cognitive learning]].
  
 ====== Homework/Assignments: ====== ====== Homework/Assignments: ======
  
 Receptive learning and reproductive knowledge do not suffice for thorough understanding. Hence, for students' convenience, we will regularly offer homework assignments, both theoretically and practically; and encourage working on them by having a random selection of them enter into the final grade. \\ Receptive learning and reproductive knowledge do not suffice for thorough understanding. Hence, for students' convenience, we will regularly offer homework assignments, both theoretically and practically; and encourage working on them by having a random selection of them enter into the final grade. \\
-Submit your individual handwritten solutions to theoretical problems in due time into **one of the homework submission boxes**; and the programming assignments in **ELICE**+<del>Submit your individual handwritten solutions to theoretical problems in due time into **one of the homework submission boxes**</del>; and the programming assignments in **ELICE**
  
 ===== 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. </del> \\ 
 +We do not accept late submissions. \\
 Copied solutions receive 0 points and personal interrogation during office/claiming hours. \\ Copied solutions receive 0 points and personal interrogation during office/claiming hours. \\
 Cheating during the exam results in failed grade //F//. \\ Cheating during the exam results in failed grade //F//. \\
Line 54: Line 58:
   *     Vöcking, Alt, Dietzfelbinger, Reischuk, Scheideler, Vollmer, Wagner: Algorithms Unplugged, Springer (2011).   *     Vöcking, Alt, Dietzfelbinger, Reischuk, Scheideler, Vollmer, Wagner: Algorithms Unplugged, Springer (2011).
   * M. Sipser:  Introduction to the theory of computation, Boston (1997)    * M. Sipser:  Introduction to the theory of computation, Boston (1997) 
 +  * Peter Brass: Advanced Data Structures (2008)
  
 For your convenience some of these books have been collected in KAIST's library 'on reserve' for this course. For your convenience some of these books have been collected in KAIST's library 'on reserve' for this course.
Line 66: Line 71:
     * 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: Long, Karatsuba, Toom, Cook     * Polynomial Multiplication: Long, Karatsuba, Toom, Cook
Line 75: Line 81:
     * Median/Quantiles     * Median/Quantiles
     * 1D Range Counting     * 1D Range Counting
 +    * 2D Range Counting
   - Sorting ({{ :21cs300c.pdf |pdf}},{{ :21cs300c.ppt |ppt}})   - Sorting ({{ :21cs300c.pdf |pdf}},{{ :21cs300c.ppt |ppt}})
     * Bubble Sort     * Bubble Sort
Line 81: Line 88:
     * Merge Sort     * Merge Sort
     * Quicksort     * Quicksort
-    * Linear-Time Median +    * {{ :median.pdf|Linear-Time Median}}
     * Optimality of Sorting     * Optimality of Sorting
     * Counting Sort     * Counting Sort
     * Radix Sort     * Radix Sort
-  Graphs ({{ :21cs300d.pdf |pdf}},{{ :21cs300d.ppt |ppt}})+    * Sorting in Parallel 
 +  Data ({{ :21cs300d.pdf |pdf}},{{ :21cs300d.ppt |ppt}}) 
 +    * Hardware vs. Mathematical 
 +    * Logical Structures = Abstract Data Types 
 +    * Basic: Boolean/Bit, Integer 
 +    * Derived: Array,  Stack, Queue 
 +    * Linked Data Structures 
 +    * (Balanced) Search Trees 
 +    * AVL Trees 
 +  - Graphs ({{ :21cs300e.pdf |pdf}},{{ :21cs300e.ppt |ppt}})
     * Recap on Graphs: un/directed, weighted     * Recap on Graphs: un/directed, weighted
     * Connectedness     * Connectedness
Line 93: Line 109:
     * 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 116:
     * 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 122:
     * Backtracking     * Backtracking
     * Branch and Bound     * Branch and Bound
 +  - Randomization ({{ :21cs300h.pdf |pdf}},{{ :21cs300h.ppt |ppt}}) 
 +    * Un/Reliability 
 +    *  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 here +  * homework assignment #0 and honor code will be uploaded on KLMS. 
-  * [[https://klms.kaist.ac.kr/course/view.php?id=124902|KLMS]]  +  * [[https://klms.kaist.ac.kr/course/view.php?id=129860|KLMS]]  
-  * [[https://kaist.elice.io/courses/7446/|ELICE]]+  * [[https://kaist.elice.io/courses/14911|ELICE]]  
 +  * [[https://www.youtube.com/playlist?list=PLvcvykdwsGNF9nmJpwXJklSCzstnFlNik|YouTube]]
   * [[https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005|MIT OpenCourseware]]   * [[https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005|MIT OpenCourseware]]
-  * 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://kahoot.it/|KAHOOT!]], so please install the app on your [[https://play.google.com/store/apps/details?id=no.mobitroll.kahoot.android|Android]] or [[https://itunes.apple.com/app/apple-store/id1131203560|Apple]] smartphone   * We use [[https://kahoot.it/|KAHOOT!]], so please install the app on your [[https://play.google.com/store/apps/details?id=no.mobitroll.kahoot.android|Android]] or [[https://itunes.apple.com/app/apple-store/id1131203560|Apple]] smartphone