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-07-04] – [Design and Analysis of Algorithms (CS500) in Spring 2023 at KAIST's School of Computing] Martin Ziegler23cs500 [2024-03-31] (current) – [Synopsis] Martin Ziegler
Line 6: Line 6:
   *     unambiguous problem specification   *     unambiguous problem specification
   *     semantics of operational primitives   *     semantics of operational primitives
-  *     algorithm design (as opposed to 'coding'/implementing)+  *     algorithm design (as prerequisite to 'coding'/implementing)
   *     and analysis (correctness, cost)   *     and analysis (correctness, cost)
   *     with proof of optimality.    *     with proof of optimality. 
Line 13: 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.