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-03-18] – [Administration:] Martin Ziegler24cs500 [2025-06-26] (current) – [Syllabus/Slides] Martin Ziegler
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,    +  *  parallel time/depth,    
-  *  size=number of CPUs/gates,   +  *  size=#CPUs/gates,   
-  *  communication volume etc. \\+  *  communication volume, 
 +  * #coin flips etc. \\
 And we discuss, design, and analyze algorithms in various __modes__ //beyond// the traditional worst-case, And we discuss, design, and analyze algorithms in various __modes__ //beyond// the traditional worst-case,
 such as    such as   
Line 24: Line 25:
   * expected,    * expected, 
   * amortized,     * amortized,  
-  * competitive etc. \\+  * competitive (ratio), 
 +  * 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 42: Line 44:
 Grading: 20% attendance/quizzes, 20% homework, 30% midterm, 30% final exam Grading: 20% attendance/quizzes, 20% homework, 30% midterm, 30% final exam
  
-Midterm: April 18, 9h00~11h45  in  E11 #3**04** \\+Midterm: April 18, **9**h00~11h45  in  E11 #3**04** \\
  
-Final exam: June 13, 9h00~11h45  in  E11 #3**04** \\+Final exam: June 13, **9**h00~11h45  in  E11 #3**04** \\
  
 Prerequisites: CS204 (Discrete Mathematics), CS300 (Introduction to Algorithms) Prerequisites: CS204 (Discrete Mathematics), CS300 (Introduction to Algorithms)
Line 61: 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 ====
 +
 +This course (pun) introduces "appetizer" chapters 
 +on some of the many topics in contemporary //Algorithm Design and Analysis//: \\
 +as an overview and to make you "hungry" for later perhaps pursuing a PhD in this field. \\
 +
 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 ({{:cs500j.ppt|PPT}}, {{:cs500j.pdf|PDF}}) \\ +10.  Memory-Efficient Algorithms ({{:cs500m.ppt|PPT}}, {{:cs500m.pdf|PDF}}) \\ 
-2.  Tree Data Structures ({{:cs500b.ppt|PPT}}, {{:cs500b.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}}) \\
 4. Amortized Analysis ({{:cs500d.ppt|PPT}}, {{:cs500d.pdf|PDF}}) \\ 4. Amortized Analysis ({{:cs500d.ppt|PPT}}, {{:cs500d.pdf|PDF}}) \\
-5. Randomized/Expected Analysis  ({{:cs500e.ppt|PPT}}, {{:cs500e.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]].
 +