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-11-21] – [Syllabus/Slides] Martin Ziegler24cs500 [2025-04-05] (current) – external edit 127.0.0.1
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 67: Line 67:
 ==== Syllabus/Slides ==== ==== Syllabus/Slides ====
 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 ({{:cs500k.ppt|PPT}}, {{:cs500k.pdf|PDF}}) \\+10.  Memory-Efficient Algorithms ({{:cs500m.ppt|PPT}}, {{:cs500m.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}}) \\
Line 83: Line 83:
 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]].
 +