Week | Day | Date | Topics | Slides |
---|---|---|---|---|
13 | Mon | 28-Jan | Introduction, peak finding | |
Tue | 29-Jan | O-notation | ||
Remarks: Throughout this course, log(n) denotes the binary logarithm, i.e., log(n) = log2(n). In the slides used in the lecture the derivative of log(n) was wrongly computed with 1/n, while it should of course be 1/(n ln(2)), with ln(n) being the logarithm to base e. I corrected this in the slides. | ||||
14 | Mon | 04-Feb | Theta, Omega, RAM Model | |
Tue | 05-Feb | Linear and binary search, proofs by induction | ||
Tue | 05-Feb | Exercise class 1 | Worksheet 1 | |
Remarks: Exercises on O-notation, Omega, and Theta can all be solved by finding constants c,n0 such that the definition of Big-O (resp. Theta, Omega) is fulfilled. Recall that any constants that fulfill the respective definition are fine, i.e., you do not need to find the smallest ones. Solutions will be provided soon. | Sol. - long Sol. - short | |||
15 | Mon | 11-Feb | Loop invariants, insertion sort | |
Tue | 12-Feb | Pre-lecture slides | ||
16 | Mon | 18-Feb | ||
Tue | 19-Feb | |||
Tue | 19-Feb | Exercise class | ||
17 | Mon | 25-Feb | ||
Tue | 26-Feb | |||
18 | Mon | 11-Mar | ||
Tue | 12-Mar | |||
Tue | 12-Mar | In-class Test | ||
19 | Mon | 18-Mar | ||
Tue | 19-Mar | |||
20 | Mon | 25-Mar | ||
Tue | 26-Mar | |||
Tue | 26-Mar | Exercise class | ||
21 | Mon | 01-Apr | ||
Tue | 02-Apr | |||
22 | Mon | 29-Apr | ||
Tue | 30-Apr | |||
Tue | 30-Apr | Exercise class | ||
23 | Mon | 06-May | ||
Tue | 07-May |