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-17] – [Synopsis] Martin Ziegler23cs500 [2024-03-31] (current) – [Synopsis] Martin Ziegler
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 from EE (Electrical 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. 
Line 12: Line 13:
 Building on undergraduate [[22cs300|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 
 //advanced// aspects of 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,  
-  *  parallel time,    +  *  parallel time/depth,    
-  *  size=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), 
 +  * approx. 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 67: Line 70:
 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}}) \\