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
24cs500 [2024-04-23] – [Syllabus/Slides] Martin Ziegler24cs500 [2025-04-05] (current) – external edit 127.0.0.1
Line 2: Line 2:
  
 All Computer Science is based on the concept of an efficient //algorithm//: as opposed to a //program// or a //heuristic//. All Computer Science is based on the concept of an efficient //algorithm//: as opposed to a //program// or a //heuristic//.
-We thus call these 'virtues' and features distinguishing CS from EE (Electrical Engineering):+We thus call these 'virtues' and features distinguishing CS (=Science) from EE (=Engineering):
  
   *     unambiguous problem specification   *     unambiguous problem specification
Line 15: Line 15:
 More specifically we discuss, design, and analyze algorithms with respect to various __cost__ measures //beyond// traditional (=sequential) runtime, More specifically we discuss, design, and analyze algorithms with respect to various __cost__ measures //beyond// traditional (=sequential) runtime,
 such as      such as     
-  *  memory,  +  *  memory use,  
   *  parallel time/depth,      *  parallel time/depth,   
   *  size=#CPUs/gates,     *  size=#CPUs/gates,  
Line 26: Line 26:
   * amortized,     * amortized,  
   * competitive (ratio),   * competitive (ratio),
-  * approx. ratio etc. \\+  * approximation ratio etc. \\
 The practical impact of these algorithms is demonstrated in selected implementations. The practical impact of these algorithms is demonstrated in selected implementations.
  
Line 63: Line 63:
   * R. Sedgewick: [[https://www.coursera.org/learn/algorithms-part1|Algorithms]]   * R. Sedgewick: [[https://www.coursera.org/learn/algorithms-part1|Algorithms]]
   * Coursera: [[https://www.coursera.org/specializations/data-structures-algorithms|Data Structures and Algorithms]]   * Coursera: [[https://www.coursera.org/specializations/data-structures-algorithms|Data Structures and Algorithms]]
 +  * MIT OCW: [[https://ocw.mit.edu/courses/6-046j-design-and-analysis-of-algorithms-spring-2015/|Design and Analysis of Algorithms (2015)]]
  
 ==== Syllabus/Slides ==== ==== Syllabus/Slides ====
 1.  Recap, Intro & Overview  ({{:cs500a.ppt|PPT}}, {{:cs500a.pdf|PDF}}) \\ 1.  Recap, Intro & Overview  ({{:cs500a.ppt|PPT}}, {{:cs500a.pdf|PDF}}) \\
-9.  Parallel Algorithms ({{:cs500i.ppt|PPT}}, {{:cs500i.pdf|PDF}}) \\ +9.  Parallel Algorithms ({{:cs500p.ppt|PPT}}, {{:cs500p.pdf|PDF}}) \\ 
-10.  Memory-Efficient Algorithms ({{:cs500k.ppt|PPT}}, {{:cs500k.pdf|PDF}}) \\+10.  Memory-Efficient Algorithms ({{:cs500m.ppt|PPT}}, {{:cs500m.pdf|PDF}}) \\
 5. Randomized/Expected Analysis  ({{:cs500e.ppt|PPT}}, {{:cs500e.pdf|PDF}}) \\ 5. Randomized/Expected Analysis  ({{:cs500e.ppt|PPT}}, {{:cs500e.pdf|PDF}}) \\
 3. Average-Case Analysis ({{:cs500c.ppt|PPT}}, {{:cs500c.pdf|PDF}}) \\ 3. Average-Case Analysis ({{:cs500c.ppt|PPT}}, {{:cs500c.pdf|PDF}}) \\
 2.  Tree Data Structures ({{:cs500b.ppt|PPT}}, {{:cs500b.pdf|PDF}}) \\ 2.  Tree Data Structures ({{:cs500b.ppt|PPT}}, {{:cs500b.pdf|PDF}}) \\
 4. Amortized Analysis ({{:cs500d.ppt|PPT}}, {{:cs500d.pdf|PDF}}) \\ 4. Amortized Analysis ({{:cs500d.ppt|PPT}}, {{:cs500d.pdf|PDF}}) \\
-6. Online/Competitive Analysis ({{:cs500f.ppt|PPT}}, {{:cs500f.pdf|PDF}}) \\ + 
-7. P/NP Intermission ({{:cs500g.ppt|PPT}}, {{:cs500g.pdf|PDF}}) \\ +
-8. Approximation  ({{:cs500h.ppt|PPT}}, {{:cs500h.pdf|PDF}})+
 ==== E-Learning: ==== ==== E-Learning: ====
   * [[https://klms.kaist.ac.kr/course/view.php?id=156166|KLMS]]   * [[https://klms.kaist.ac.kr/course/view.php?id=156166|KLMS]]
   * [[https://kaist.elice.io/courses/88381/|ELICE]]   * [[https://kaist.elice.io/courses/88381/|ELICE]]
   * [[http://youtube.com/playlist?list=PLvcvykdwsGNH94LPIF6g5vtFkcQ5fqN17|YouTube]]   * [[http://youtube.com/playlist?list=PLvcvykdwsGNH94LPIF6g5vtFkcQ5fqN17|YouTube]]
-With about 100 students enrolled, please refrain from contacting me by personal email. \\+  * {{:averagequicksort.pdf|Average-Case Analysis of QuickSort}} 
 +With over 100 students enrolled, please refrain from contacting me by personal email. \\
 Instead use KLMS to reach out to the TAs (preferred), \\ Instead use KLMS to reach out to the TAs (preferred), \\
 or write to the dedicated email address [[cs500@theoryofcomputation.asia|cs500@theoryofcomputation.asia]]. or write to the dedicated email address [[cs500@theoryofcomputation.asia|cs500@theoryofcomputation.asia]].
 +