| SSDato | Undervises av | Sted | Tema | Kommentarer / ressurser |
| 19.08.2014 | Dino Karabeg (DK) | OJD Aud Smalltalk | Introduction to algorithms and complexity |
Lecture 1 pages 17-29 and Lecture 2 pages 37-39 and 46-52 in Kompendium til IN210 by Karabeg/Djurhuus. Weekly assignments (ukeoppgaver) next week: Number 3,4,5 and 6 from the Kompendium (Ch. 4). The solutions are provided in Kompendium. |
| 26.08.2014 | Petter Kristiansen (PK) | OJD Aud Smalltalk | String Matching |
Ch. 20 (Berman & Paul) |
| 02.09.2014 | Stein Krogdahl (SK) | OJD Aud Smalltalk | Dynamic programming |
slides used at the lecture September 2. A "better" (?) version of the slides, added September 9. Exercises for Sept. 4 and 9 (slightly changed 4/9-2014) |
| 09.09.2014 | PK and guest lecturer Torbjørn Rognes from the group for Bio-informatics (at the Dept of Informatics). | OJD Aud Smalltalk |
First hour: Implementation of priority queues Second hour: Torbjørn Rognes: On algorithms that are used in Bio-informatics(e.g. searching in gene-sequences). |
Ch. 6 in textbook (B&P) and Ch. 6.5 and 6.7 in Mark Allan Weiss (see below) |
| 16.09.2014 | SK | OJD Aud Smalltalk |
Search strategies: Depth-first, breadth-first, priority, and A*. |
Ch. 10 is partly old stuff from INF2220 (or other courses in "Algorithms and Data Structures"), and the rest is from chapter 23 in our textbook Slides used during the lecture (16/9) |
| 23.09.2014 | SK and guest lecturer Rune Djurhuus | OJD Aud Smalltalk |
First hour: About two-player-games and alpha/beta-cutoff (pruning). Second hour: About chess-playing programs: How good are they? How do they work? What about programs playing other games? Our guest Rune Djurhuus is a Grand Master of chess, and he writes about chess every day in Aftenposten. He also has a masters degree from Dept. of Informatcs at UiO! |
Ch. 23.5 in textbook (Final) Slides |
| 30.09.2014 | DK | OJD Aud Smalltalk | Undecidability |
Lecture 2 pages 52-55, Lecture 3 main ideas from pages 56-71, pages 72-78 in detail and Lecture 4 pages 82-83 in Dino Karabeg og Rune Djurhuus' Kompendium til IN210. |
| 07.10.2014 | DK | OJD Aud Smalltalk | NP-completeness |
Lecture 5 pages 106-131, Lecture 6 pages 132 - 135 and statement and proof idea of Cook's theorem on pages 136-147 in Dino Karabeg and Rune Djurhuus' Kompendium til IN210. |
| 14.10.2014 | DK | OJD Aud Smalltalk | Proving NP-completeness |
Lecture 6 pages 148-159; Lecture 7 pages 160- 183 in Dino Karabeg og Rune Djurhuus' Kompendium til IN210. Solutions are provided in Kompendium |
| 21.10.2014 | SK | OJD Aud Smalltalk |
Matching and Flow in Networks |
|
| 28.10.2014 | PK | OJD Aud Smalltalk |
Triangulation and convex hull. |
Triangulation of a point set (the slides are the curriculum), and the convex hull of a point set (Ch. 8.6.2). |
| 04.11.2014 | DK | OJD Aud Smalltalk |
Coping with NP Completeness I: Smart exhaustive search; approximation; heuristics |
Lecture 10, pages 236-261 in Kompendium til IN210 by Karabeg/Djurhuus. Exercises: No. 32, 34 and 36 in Kompendium. Solutions are provided in Kompendium |
| 11.11.2014 | DK | OJD Aud Smalltalk | Coping with NP Completeness II: Average-case analysis; algorithms that do well on average; probabilistic and parallel algorithms |
Lecture 11 pages 274-287, Lecture 12 p. 290-295 and only main ideas of material on pages 308 and 314 in Kompendium til IN210 by Karabeg/Djurhuus. Solutions are provided in Kompendium |
| 18.11.2014 | IKKE FORELESNING | |||
| 25.11.2014 | DK, PK, SK | OJD Aud Smalltalk | Go through last year's exam, and answer questions | |
| 12.12.2014 | Exam, 09:00 (4 hours) |