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
25cs500 [2025-02-17] – [Syllabus/Slides] Martin Ziegler25cs500 [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/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 32: Line 32:
 Lecturer: [[cs500@theoryofcomputation.asia|Martin Ziegler]] (use only this email address!) Lecturer: [[cs500@theoryofcomputation.asia|Martin Ziegler]] (use only this email address!)
  
-Classroom: Online+Classroom: E11 #304
  
 Schedule: Tue+Thu 16h00~17h30pm KST \\ Schedule: Tue+Thu 16h00~17h30pm KST \\
Line 38: Line 38:
 Language: English only Language: English only
  
-Teaching Assistants: [[cs500@theoryofcomputation.asia|TBD]]\\+Teaching Assistants: [[cs500@theoryofcomputation.asia|현지훈+김소민+송민우]] (use only this email address!) \\
  
 Homework: Handwritten individual solutions (English only) and programming assignments in [[https://kaist.elice.io/|ELICE]]. Homework: Handwritten individual solutions (English only) and programming assignments in [[https://kaist.elice.io/|ELICE]].
  
-Grading: 40% attendance/quizzes, 20% homework, 20% midterm, 20% final exam+Grading: 20% attendance, 20% quizzes/participation, 20% homework, 20% midterm, 20% final exam \\ 
 +Using this mix gives //everyone// the chance of passing  with sufficient grade... 
 + 
 +Midterm: April 15, 16h~18h45, E11 #304 \\ 
 +Final Exam: June 10, 16h~18h45, E11 #304
  
 Prerequisites: CS204 (Discrete Mathematics), CS300 (Introduction to Algorithms) Prerequisites: CS204 (Discrete Mathematics), CS300 (Introduction to Algorithms)
 +
 +Policies: Joining class no later than 10 minutes counts as full attendance, \\
 +no later than 30 minutes still counts as half attendance, \\
 +later than 30 minutes counts as unexcused absence. \\
 +Excused absence must be confirmed by the student's academic advisor via email.
  
 ==== Literature ==== ==== Literature ====
Line 62: Line 71:
  
 ==== 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. \\
 +
 0.  Summary ({{:cs500z.ppt|PPT}}, {{:cs500z.pdf|PDF}}) \\ 0.  Summary ({{:cs500z.ppt|PPT}}, {{:cs500z.pdf|PDF}}) \\
 1.  Introduction  ({{:cs500a.ppt|PPT}}, {{:cs500a.pdf|PDF}}) \\ 1.  Introduction  ({{:cs500a.ppt|PPT}}, {{:cs500a.pdf|PDF}}) \\
-9. parallel Time ({{:cs500i.ppt|PPT}}, {{:cs500i.pdf|PDF}}) \\ +9. parallel Time ({{:cs500p.ppt|PPT}}, {{:cs500p.pdf|PDF}}) \\ 
-10. Memory ({{:cs500k.ppt|PPT}}, {{:cs500k.pdf|PDF}}) \\ +10. Memory ({{:cs500m.ppt|PPT}}, {{:cs500m.pdf|PDF}}) \\ 
-11. Bonus: Quantum Computing ({{:cs500l.ppt|PPT}}, {{:cs500l.pdf|PDF}}) \\+11. Bonus: Quantum Computing ({{:cs500q.ppt|PPT}}, {{:cs500q.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}}) \\ 
-4. Amortized Analysis ({{:cs500d.ppt|PPT}}, {{:cs500d.pdf|PDF}}) \\ 
 6. Online/Competitive Analysis ({{:cs500f.ppt|PPT}}, {{:cs500f.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}})
-8. Approximation  ({{:cs500h.ppt|PPT}}, {{:cs500h.pdf|PDF}}) \\ +
 ==== E-Learning: ==== ==== E-Learning: ====
-  * [[https://klms.kaist.ac.kr/|KLMS]] +  * [[https://klms.kaist.ac.kr/course/view.php?id=169186|KLMS]] 
-  * [[https://kaist.elice.io/|ELICE]]+  * [[https://kaist.elice.io/courses/728300/|ELICE]]
   * [[http://youtube.com/playlist?list=PLvcvykdwsGNH94LPIF6g5vtFkcQ5fqN17|YouTube]]   * [[http://youtube.com/playlist?list=PLvcvykdwsGNH94LPIF6g5vtFkcQ5fqN17|YouTube]]
   * {{averagequicksort.pdf|Average-Case Analysis of QuickSort}}   * {{averagequicksort.pdf|Average-Case Analysis of QuickSort}}
 +