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
22cs300 [2022-08-29] – [Introduction to Algorithms (CS300) in Fall 2022 at KAIST's School of Computing] Martin Ziegler22cs300 [2022-11-01] (current) – Martin Ziegler
Line 15: Line 15:
 Lecturer: Martin Ziegler Lecturer: Martin Ziegler
  
-Lecture hall: E11 터만홀+Lecture location: E11 //Terman Hall// / online
  
 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: TBD+Teaching Assistants: Lwam Araya, Sookyung Han, Sujeong Lim, Abbas Mammadov, Jinyoung Oh, Mingi Shin, Biniyam Aschalew Tolera
  
 Office hours: TBD Office hours: TBD
Line 29: Line 29:
 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/Pedagogy ===== 
 + 
 +Education is a Human Right, not a competition. \\ 
 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]]. 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: ======+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/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. \\
Line 59: Line 65:
 ===== Synopsis/Syllabus: ===== ===== Synopsis/Syllabus: =====
  
-  - {{ :22cs300a.ppt |Motivation}}+  - Introduction ({{ :22cs300a.pdf |pdf}},{{ :22cs300a.ppt |ppt}}) 
 +    * Hierarchy of Abstraction
     * Virtues of Computer //Science//:     * Virtues of Computer //Science//:
     * Problem specification     * Problem specification
Line 69: Line 76:
     * Recurrences and the //Master Theorem//     * Recurrences and the //Master Theorem//
     * Polynomial Multiplication: Long, Karatsuba, Toom, Cook     * Polynomial Multiplication: Long, Karatsuba, Toom, Cook
-  - Searching ({{ :22cs300b.pdf |pdf}},{{ :22cs300b.ppt |ppt}})+  - Searching ({{ :22cs300b.pdf|pdf}},{{ :22cs300b.ppt|ppt}})
     * Linear Search     * Linear Search
     * Binary Search     * Binary Search
     * Uniqueness     * Uniqueness
     * Hashing     * Hashing
-    * Median/Quantiles+    * Median/Order Statistics 
 +    * Approximate/Linear-Time
     * 1D Range Counting     * 1D Range Counting
-    * 2D Range Counting +    * 2D/3D Range Counting 
-  - Sorting ({{ :22cs300c.pdf |pdf}},{{ :22cs300c.ppt |ppt}})+    * Range Reporting 
 +  - Sorting ({{ :22cs300c.pdf|pdf}},{{ :22cs300c.ppt|ppt}})
     * Bubble Sort     * Bubble Sort
     * Selection Sort     * Selection Sort
Line 83: Line 92:
     * Merge Sort     * Merge Sort
     * Quicksort     * Quicksort
-    * {{ :median.pdf|Linear-Time Median}}+    * Linear-Time Median revisited
     * Optimality of Sorting     * Optimality of Sorting
     * Counting Sort     * Counting Sort
     * Radix Sort     * Radix Sort
     * Sorting in Parallel     * Sorting in Parallel
-  - Data ({{ :22cs300d.pdf |pdf}},{{ :22cs300d.ppt |ppt}})+  - Data ({{ :22cs300d.pdf|pdf}},{{ :22cs300d.ppt|ppt}})
     * 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 ({{ :22cs300e.pdf |pdf}},{{ :22cs300e.ppt |ppt}})+  - Graphs ({{ :22cs300e.pdf|pdf}},{{ :22cs300e.ppt|ppt}})
     * Recap on Graphs: un/directed, weighted     * Recap on Graphs: un/directed, weighted
     * 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://klms.kaist.ac.kr/course/view.php?id=XXX|KLMS]]  +  * [[https://klms.kaist.ac.kr/course/view.php?id=140297|KLMS]]  
-  * [[https://kaist.elice.io/courses/XXX|ELICE]] +  * [[https://kaist.elice.io/courses/30277|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