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] – Martin Ziegler22cs300 [2022-11-01] (current) – Martin Ziegler
Line 76: 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 91: 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 104: 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 136: 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