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 [2024-03-31] – [Synopsis] Martin Ziegler23cs500 [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,    +  *  parallel time/depth,    
-  *  size=number of CPUs/gates,   +  *  size=#CPUs/gates,   
-  *  communication volume +  *  communication volume,
   * #coin flips etc. \\   * #coin flips etc. \\
 And we discuss, design, and analyze algorithms in various __modes__ //beyond// the traditional worst-case, And we discuss, design, and analyze algorithms in various __modes__ //beyond// the traditional worst-case,
Line 25: Line 25:
   * 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 62: 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 73: Line 75:
 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 ({{:cs500k.ppt|PPT}}, {{:cs500k.pdf|PDF}})+10. Memory ({{:cs500m.ppt|PPT}}, {{:cs500m.pdf|PDF}})
  
 ==== E-Learning: ==== ==== E-Learning: ====
Line 80: 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}}