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
18cs500 [2018-05-22] Martin Ziegler18cs500 [2018-07-01] (current) Martin Ziegler
Line 1: Line 1:
- ====== Design and Analysis of Algorithms (CS500) in Spring 2018 at KAIST's School of Computing ======+====== Design and Analysis of Algorithms (CS500) in Spring 2018 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 the 'virtues' of Theoretical Computer Science: 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 the 'virtues' of Theoretical Computer Science:
Line 9: Line 9:
   *     with proof of asymptotic optimality.    *     with proof of asymptotic optimality. 
  
-Building on undergraduate CS300 (Introduction to Algorithm), the graduate-level course CS500 discusses the design of advanced algorithms and analyzes their behaviour with respect to various notions of performance such as +Building on undergraduate CS300 (Introduction to Algorithms), the graduate-level course CS500 discusses the design of advanced algorithms and analyzes their behaviour with respect to various notions of performance such as 
   * worst-case,   * worst-case,
   * average-case,    * average-case, 
Line 38: Line 38:
  
 Midterm Exam: The midterm exam will be held on Monday, April 16, from 9:00am to 11:45am. We use two lecture rooms. If your student id is less than 20175000, you are expected to take the midterm exam at E11, #309. If your student id is greater than 20175000, you are expected to take the exam at E11, #310.   Midterm Exam: The midterm exam will be held on Monday, April 16, from 9:00am to 11:45am. We use two lecture rooms. If your student id is less than 20175000, you are expected to take the midterm exam at E11, #309. If your student id is greater than 20175000, you are expected to take the exam at E11, #310.  
- + 
 +Final Exam: The final exam will be held on Monday, June 11, from 9:00am to 11:45am. We use two lecture rooms. If your student id is less than 20173636, you are expected to take the final exam at E11, #310. If your student id is greater than 20173636, you are expected to take the final exam at E11, #309. 
 Prerequisites: CS204 (Discrete Mathematics), CS206 (Data Structures), CS300 (Introduction to Algorithms) Prerequisites: CS204 (Discrete Mathematics), CS206 (Data Structures), CS300 (Introduction to Algorithms)
  
Line 56: Line 58:
   *     Vöcking, Alt, Dietzfelbinger, Reischuk, Scheideler, Vollmer, Wagner: Algorithms Unplugged, Springer (2011).   *     Vöcking, Alt, Dietzfelbinger, Reischuk, Scheideler, Vollmer, Wagner: Algorithms Unplugged, Springer (2011).
   *     Introduction to the Analysis of Algorithms (Robert Sedgewick and Philippe Flajolet)    *     Introduction to the Analysis of Algorithms (Robert Sedgewick and Philippe Flajolet) 
 +  * Online Computation and Competitive Analysis (Allan Borodin and Ran El-Yaniv)
 +  * Probability and Computing: Randomized Algorithms and Probabilistic Analysis (Michael Mitzenmacher and Eli Upfal) 
 +  * M. Sipser:  Introduction to the theory of computation, Boston (1997) 
  
 For your convenience some of these books have been collected in KAIST's library 'on reserve' for this course. For your convenience some of these books have been collected in KAIST's library 'on reserve' for this course.
Line 67: Line 72:
   *     {{18cs500d.pdf|Union-Find}}   *     {{18cs500d.pdf|Union-Find}}
   *     {{18cs500e.pdf|Randomization}}   *     {{18cs500e.pdf|Randomization}}
-  *  {{mayerlindenberg1.pdf|Guest Talk #1}} and {{mayerlindenberg2.pdf|#2}} by [[https://www.tuhh.de/ict/mitarbeiter/mayer-lindenberg.html|Prof. Mayer-Lindenberg (TU Hamburg-Harburg)]] 
   * {{18cs500f.pdf|Online/Competitive}}   * {{18cs500f.pdf|Online/Competitive}}
   *     {{ ::cs500-0509.pdf |Complexity Theory}}   *     {{ ::cs500-0509.pdf |Complexity Theory}}
   * Intermission: {{talk-identifiability.pdf|Global Identifiability of Parametric Differential Models}} by [[https://cs.nyu.edu/yap|Prof. Chee K. Yap (New York University)]]   * Intermission: {{talk-identifiability.pdf|Global Identifiability of Parametric Differential Models}} by [[https://cs.nyu.edu/yap|Prof. Chee K. Yap (New York University)]]
   *     {{18cs500h.pdf|Approximation}}   *     {{18cs500h.pdf|Approximation}}
-  * Memory+  *      {{18cs500i.pdf|Memory≈parallel Time}}
   *     Conclusion    *     Conclusion 
  
Line 80: Line 84:
   * {{18cs500hw2_1.pdf |Homework #2}} consists of four problems to be solved in groups of three and submitted in English handwriting before March 30 (Friday) 9am into the CS500 mail box next to the elevator on 3F of building E3-1.   * {{18cs500hw2_1.pdf |Homework #2}} consists of four problems to be solved in groups of three and submitted in English handwriting before March 30 (Friday) 9am into the CS500 mail box next to the elevator on 3F of building E3-1.
   * {{18cs500hw3.pdf |Homework #3}} consists of two problems to be solved in groups of three and submitted in English handwriting before April 13 (Friday) 9am into the CS500 mail box next to the elevator on 3F of building E3-1.   * {{18cs500hw3.pdf |Homework #3}} consists of two problems to be solved in groups of three and submitted in English handwriting before April 13 (Friday) 9am into the CS500 mail box next to the elevator on 3F of building E3-1.
 +  *  {{mayerlindenberg1.pdf|Guest Talk #1}} and {{mayerlindenberg2.pdf|#2}} by [[https://www.tuhh.de/ict/mitarbeiter/mayer-lindenberg.html|Prof. Mayer-Lindenberg (TU Hamburg-Harburg)]]
   * {{18cs500hw4.pdf |Homework #4}} consists of two problems to be solved in groups of three and submitted in English handwriting before May 11 (Friday) 9am into the CS500 mail box next to the elevator on 3F of building E3-1; and one problem to be solved individually in [[https://kaist.elice.io/courses/268/lectures||ELICE]] before May 11 (Friday)9am.   * {{18cs500hw4.pdf |Homework #4}} consists of two problems to be solved in groups of three and submitted in English handwriting before May 11 (Friday) 9am into the CS500 mail box next to the elevator on 3F of building E3-1; and one problem to be solved individually in [[https://kaist.elice.io/courses/268/lectures||ELICE]] before May 11 (Friday)9am.
   * {{18cs500hw5.pdf |Homework #5}} consists of three problems to be solved in groups of three and submitted in English handwriting before May 23 (Wednesday) 9am into the CS500 mail box next to the elevator on 3F of building E3-1.   * {{18cs500hw5.pdf |Homework #5}} consists of three problems to be solved in groups of three and submitted in English handwriting before May 23 (Wednesday) 9am into the CS500 mail box next to the elevator on 3F of building E3-1.
 +  * {{18cs500hw6.pdf |Homework #6}} consists of Problems 14 and 15a to be solved in groups of three and submitted in English handwriting before <del>June 6 (Wednesday)</del> //June 8 (Friday)// 9am into the CS500 mail box next to the elevator on 3F of building E3-1; and of programming Problems 15b) to 15e) to be solved individually in [[https://kaist.elice.io/courses/268/lectures||ELICE]].