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
23cs500 [2023-06-10] – [Design and Analysis of Algorithms (CS500) in Spring 2023 at KAIST's School of Computing] Martin Ziegler23cs500 [2025-04-05] (current) – external edit 127.0.0.1
Line 1: Line 1:
 ====== Design and Analysis of Algorithms (CS500) in Spring 2023 at KAIST's School of Computing ====== ====== Design and Analysis of Algorithms (CS500) in Spring 2023 at KAIST's School of Computing ======
  
-All Computer Science is based on the concept of an efficient algorithm: a finite sequence of primitive instructions that, when executed according to their well-specified semantics, provably provide a mechanical solution to the infinitely many instances of a complex mathematical problem within a guaranteed number of steps of least asymptotic growth. We thus call these 'virtues' and features distinguishing Computer Science from Electrical Engineering:+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 (=Science) from EE (=Engineering):
  
   *     unambiguous problem specification   *     unambiguous problem specification
   *     semantics of operational primitives   *     semantics of operational primitives
-  *     algorithm design (as opposed to 'programming/coding')+  *     algorithm design (as prerequisite to 'coding'/implementing)
   *     and analysis (correctness, cost)   *     and analysis (correctness, cost)
   *     with proof of optimality.    *     with proof of optimality. 
  
 ==== Synopsis ==== ==== Synopsis ====
-Building on undergraduate CS300 (Introduction to Algorithms), the graduate-level course CS500 revolves around  +Building on undergraduate [[22cs300|CS300 (Introduction to Algorithms)]], the graduate-level course CS500 revolves around  
-the design and analysis of advanced algorithms.  \\ +//advanced// aspects of algorithms.  \\ 
-More specifically we discuss, design, and analyze algorithms with respect to various __cost__ measures //beyond// (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,    
-  *  number of CPUs/gates,   +  *  size=#CPUs/gates,   
-  *  communication volume etc. \\ +  *  communication volume, 
-And we discuss, design, and analyze algorithms in various __modes__ //beyond// the worst-case,+  * #coin flips etc. \\ 
 +And we discuss, design, and analyze algorithms in various __modes__ //beyond// the traditional worst-case,
 such as    such as   
   * average-case,      * average-case,   
   * 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 35: Line 38:
 Language: English only Language: English only
  
-Teaching Assistants: [[qawbecrdtey@kaist.ac.kr|현지훈]] and [[jeongho.park@kaist.ac.kr|박정호]]\\+Teaching Assistants: [[cs500@theoryofcomputation.asia|현지훈 and 박정호]]\\
  
 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]].
Line 60: 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 ====
Line 67: Line 71:
 3. Average-Case Analysis ({{:cs500c.ppt|PPT}}, {{:cs500c.pdf|PDF}}) \\ 3. Average-Case Analysis ({{:cs500c.ppt|PPT}}, {{:cs500c.pdf|PDF}}) \\
 4. Amortized Analysis ({{:cs500d.ppt|PPT}}, {{:cs500d.pdf|PDF}}) \\ 4. Amortized Analysis ({{:cs500d.ppt|PPT}}, {{:cs500d.pdf|PDF}}) \\
-5. Randomization  ({{:cs500e.ppt|PPT}}, {{:cs500e.pdf|PDF}}) \\ +5. Randomized/Expected Analysis  ({{:cs500e.ppt|PPT}}, {{:cs500e.pdf|PDF}}) \\ 
-6. Online/Competitive  ({{: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}}) \\ 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}}) \\
-9. parallel Time ({{:cs500i.ppt|PPT}}, {{:cs500i.pdf|PDF}}) \\ +9. parallel Time ({{:cs500p.ppt|PPT}}, {{:cs500p.pdf|PDF}}) \\ 
-10. Memory+10. Memory ({{:cs500m.ppt|PPT}}, {{:cs500m.pdf|PDF}})
  
 ==== E-Learning: ==== ==== E-Learning: ====
Line 78: Line 82:
   * [[https://kaist.elice.io/courses/64965/|ELICE]]   * [[https://kaist.elice.io/courses/64965/|ELICE]]
   * [[http://youtube.com/playlist?list=PLvcvykdwsGNH94LPIF6g5vtFkcQ5fqN17|YouTube]]   * [[http://youtube.com/playlist?list=PLvcvykdwsGNH94LPIF6g5vtFkcQ5fqN17|YouTube]]
-  * {{averagequicksort.pdf|Solution to the quiz in Chapter 3}}+  * {{averagequicksort.pdf|Average-Case Analysis of QuickSort}}