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
18cs300 [2018-11-20] – [Synopsis/Syllabus:] Martin Ziegler18cs300 [2021-07-31] (current) Martin Ziegler
Line 9: Line 9:
   *     with proof of asymptotic optimality.    *     with proof of asymptotic optimality. 
  
-We will learn all about important basic algorithms and their analysis.+We will learn all about important basic algorithms and their analysis
 +as well as the difference to heuristics or programs/code.
 Their practical impact is demonstrated in selected implementations. Their practical impact is demonstrated in selected implementations.
  
Line 23: Line 24:
  
 Office hours: **Wed 14:30-17:30 @ N1 404** Office hours: **Wed 14:30-17:30 @ N1 404**
-  Midterm claiming/office hour on Nov.7 will be held in **E3-1 #3444** 
  
 Quiz: On randomly selected sessions we will perform a short written quiz. Quiz: On randomly selected sessions we will perform a short written quiz.
Line 30: Line 30:
  
 Written **midterm** exam on Wednesday October 17 at 16h30 in E11 Terman Hall. \\ Written **midterm** exam on Wednesday October 17 at 16h30 in E11 Terman Hall. \\
-Written **final** exam on Wednesday December **5** at 10h30 in E3-1 #1501.+Written **final** exam on Wednesday December **5** at 10h30 in E3-1 #1501. \\ 
 +**[[https://kaist.elice.io/courses/532/lectures/5377|Final ELICE assignment]]** due Monday, Dec.18 11am. 
 +  Final/hw#8 claiming hour on Dec.18 at 11am in E3-1 #4443
  
  
Line 63: Line 65:
 ===== Synopsis/Syllabus: ===== ===== Synopsis/Syllabus: =====
  
-  - {{ :cs300a.ppt |Computational Problems and Algorithmic Solutions}}+  - {{ :18cs300a.ppt |Motivation}}
     * Virtues of Computer //Science//:     * Virtues of Computer //Science//:
     * Problem specification     * Problem specification
Line 89: Line 91:
     * Counting Sort     * Counting Sort
     * Radix Sort     * Radix Sort
-  - Graph Problems ({{ :cs300d.pdf |pdf}},{{ :cs300d.ppt |ppt}})+  - Graphs ({{ :cs300d.pdf |pdf}},{{ :cs300d.ppt |ppt}})
     * Recap on Graphs: un/directed, weighted     * Recap on Graphs: un/directed, weighted
     * Connectedness     * Connectedness
Line 97: Line 99:
     * Max. bipartite matching     * Max. bipartite matching
     * Min-Cut     * Min-Cut
-  - String Problems ({{ :cs300e.pdf |pdf}},{{ :cs300e.ppt |ppt}})+  - Strings ({{ :cs300e.pdf |pdf}},{{ :cs300e.ppt |ppt}})
     * Terminology     * Terminology
     * Pattern matching: Knuth-Morris-Pratt     * Pattern matching: Knuth-Morris-Pratt
Line 104: Line 106:
     * Parsing: Cocke-Younger-Kasami     * Parsing: Cocke-Younger-Kasami
     * Huffman Compression     * Huffman Compression
-  - Dynamic Programming Greedy Paradigms+  - Paradigms ({{ :cs300f.pdf |pdf}},{{ :cs300f.ppt |ppt}}) 
 +    * Divide and Conquer 
 +    * Dynamic Programming  
 +    * Greedy  
 +    * Backtracking 
 +    * Branch and Bound
  
-===== E-Learning: =====+ ===== E-Learning: =====
  
-  * slides will be uploaded as the course progresses 
   * homework #0 in [[https://kaist.elice.io/courses/532/lectures/3613|ELICE]] asks you to implement three algorithms for computing Fibonacci Numbers and is due by 10am on Sep.10    * homework #0 in [[https://kaist.elice.io/courses/532/lectures/3613|ELICE]] asks you to implement three algorithms for computing Fibonacci Numbers and is due by 10am on Sep.10 
   * {{ :18cs300_1.pdf | honor code + homework #1}} are due in individual English handwriting by 10:25am on Sep.17   * {{ :18cs300_1.pdf | honor code + homework #1}} are due in individual English handwriting by 10:25am on Sep.17
Line 116: Line 122:
   * {{ :18cs300_5.pdf | homework #5}} is due in individual English handwriting by 10:25am on Nov.5   * {{ :18cs300_5.pdf | homework #5}} is due in individual English handwriting by 10:25am on Nov.5
   * homework #6 in [[https://kaist.elice.io/courses/532/lectures/4273|ELICE]] asks you to implement the //linear-time median// and is due by 10:30am on Nov.<del>14</del> **16 (Friday)**   * homework #6 in [[https://kaist.elice.io/courses/532/lectures/4273|ELICE]] asks you to implement the //linear-time median// and is due by 10:30am on Nov.<del>14</del> **16 (Friday)**
-  * homework #7 in [[https://kaist.elice.io/courses/532/lectures/4986|ELICE]] asks you to implement //Prim's Algorithm// and is due by 10:30am on Nov.23 (Friday)**+  * homework #7 in [[https://kaist.elice.io/courses/532/lectures/4986|ELICE]] asks you to implement //Prim's Algorithm// and is due by 10:30am on Nov.23 (Friday) 
 +   {{ :18cs300_8.pdf | homework #8}} is due in individual English handwriting by 10:25am on Dec.3
   * [[http://klms.kaist.ac.kr/course/view.php?id=99397|KLMS]]    * [[http://klms.kaist.ac.kr/course/view.php?id=99397|KLMS]] 
   * Due to the large number (240) of students enrolled, we unfortunately cannot answer questions by email. \\ Instead please use the KLMS Bulletin Board or visit the TAs during their office hours.   * Due to the large number (240) of students enrolled, we unfortunately cannot answer questions by email. \\ Instead please use the KLMS Bulletin Board or visit the TAs during their office hours.
 +  * We use [[https://kahoot.it/|KAHOOT!]], so please install the app on your [[https://play.google.com/store/apps/details?id=no.mobitroll.kahoot.android|Android]] or [[https://itunes.apple.com/app/apple-store/id1131203560|Apple]] smartphone