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-09-27] – [Synopsis/Syllabus:] Martin Ziegler22cs300 [2022-11-01] (current) – Martin Ziegler
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 70: 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/3D Range Counting     * 2D/3D Range Counting
     * Range Reporting     * Range Reporting
-  - Sorting ({{ :22cs300c.pdf |pdf}},{{ :22cs300c.ppt |ppt}})+  - Sorting ({{ :22cs300c.pdf|pdf}},{{ :22cs300c.ppt|ppt}})
     * Bubble Sort     * Bubble Sort
     * Selection Sort     * Selection Sort
Line 85: Line 92:
     * Merge Sort     * Merge Sort
     * Quicksort     * Quicksort
-    * 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 98: 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 130: 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