Differences
This shows you the differences between two versions of the page.
Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
18cs300 [2018-11-22] – [E-Learning:] Martin Ziegler | 18cs300 [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/ | ||
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** | ||
- | Claiming/ | ||
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 # |
+ | **[[https:// | ||
+ | Final/hw#8 claiming hour on Dec.18 at 11am in E3-1 #4443 | ||
Line 63: | Line 65: | ||
===== Synopsis/ | ===== Synopsis/ | ||
- | - {{ :cs300a.ppt |Computational Problems and Algorithmic Solutions}} | + | - {{ :18cs300a.ppt |Motivation}} |
* Virtues of Computer // | * Virtues of Computer // | ||
* Problem specification | * Problem specification | ||
Line 89: | Line 91: | ||
* Counting Sort | * Counting Sort | ||
* Radix Sort | * Radix Sort | ||
- | - Graph Problems | + | - Graphs |
* Recap on Graphs: un/ | * Recap on Graphs: un/ | ||
* Connectedness | * Connectedness | ||
Line 97: | Line 99: | ||
* Max. bipartite matching | * Max. bipartite matching | ||
* Min-Cut | * Min-Cut | ||
- | - String Problems | + | - Strings |
* 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 | + | - 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:// | * homework #0 in [[https:// | ||
* {{ : | * {{ : | ||
Line 117: | Line 123: | ||
* homework #6 in [[https:// | * homework #6 in [[https:// | ||
* homework #7 in [[https:// | * homework #7 in [[https:// | ||
+ | * {{ : | ||
* [[http:// | * [[http:// | ||
* 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:// |