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-09-07] – [Introduction to Algorithms (CS300) in Fall 2021 at KAIST's School of Computing] Donghyun Lim21cs300 [2022-02-09] (current) – [Literature:] Martin Ziegler
Line 21: Line 21:
 Language: English __only__ (except for students discussing in KLMS) Language: English __only__ (except for students discussing in KLMS)
  
-Teaching Assistants: <del>임동현 (head)</del> Makenov  Arnur (head)+Teaching Assistants: <del>임동현 (head)</del> Makenov  Arnur (head) \\  
 +Hyeonguk Ryu, Jaejun Lee, Jihoon Hyun, Kyounga Woo, Minjae Park, Mukhtar Kussaiynbekov, Seungjin Baek, Taeyoung Kim, Yeonghun Kim, Yoonsung 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.
Line 57: 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 86: 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
Line 120: 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 <del>here</del> on KLMS. +  * homework assignment #0 and honor code will be uploaded on KLMS. 
-  * [[https://klms.kaist.ac.kr/course/view.php?id=|KLMS]] (link does not work) +  * [[https://klms.kaist.ac.kr/course/view.php?id=129860|KLMS]]  
-  * [[https://kaist.elice.io/courses/|ELICE]] (link does not work)+  * [[https://kaist.elice.io/courses/14911|ELICE]] 
   * [[https://www.youtube.com/playlist?list=PLvcvykdwsGNF9nmJpwXJklSCzstnFlNik|YouTube]]   * [[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 (>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://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