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-06-04] – Homework #6 deadline extension 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 59: Line 59:
   *     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)   * Online Computation and Competitive Analysis (Allan Borodin and Ran El-Yaniv)
-  * Probability and Computing: Randomized Algorithms and Probabilistic Analysis (Micha Mitzenmacher and Eli Upfal) +  * 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 71: 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}}
Line 84: 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]].   * {{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]].
-