| Dato | Undervises av | Sted | Tema | Kommentarer / ressurser |
| 20.08.2012 | Dino Karabeg (DK) | OJD 3437 Sem.rom C | 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. |
| 27.08.2012 | Petter Kristiansen (PK) | OJD 3437 Sem.rom C | String Matching |
Ch. 20. in the textbook (Berman and Paul) |
| 03.09.2012 | Stein Krogdahl (SK) | OJD 3437 Sem.rom C | Dynamic Programming |
Ch. 9 and 20.5 in textbook |
| 10.09.2012 | PK and guest lecturer Torbj?rn Rognes from the group for Bio-informatics (at the Dep of Informatics). | OJD 3437 Sem.rom C |
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 (are not copied here) and Ch. 6.5 and 6.7 in Mark Allan Weiss (see below) |
| 17.09.2012 | SK | OJD 3437 Sem.rom C |
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. |
| 24.09.2012 | PK and guest lecturer Rune Djurhuus | OJD 3437 Sem.rom C |
First hour: About two-player-games and alpha/beta-cutoff (pruning). Second hour: 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! About chess-playing programs: How good are they? How do they work? What about programs playing other games? |
Ch. 23.5 in textbook. |
| 01.10.2012 | DK | OJD 3437 Sem.rom C | 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. |
| 08.10.2012 | DK | OJD 3437 Sem.rom C | 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. |
| 15.10.2012 | DK | OJD 3437 Sem.rom C | Proving NP-completeness |
Lecture 6 pages 148-159; Lecture 7 pages 160- 183 in Dino Karabeg og Rune Djurhuus' Kompendium til IN210. The solutions are provided in Kompendium. |
| 22.10.2012 | SK | OJD 3437 Sem.rom C | Matching and Flow in Networks |
Chapter 14 |
| 29.10.2012 | PK | OJD 3437 Sem.rom C |
The rest from last time (by SK) Triangulation and convex hull |
First: The rest of the slides from last time Then: Triangulation of point sets (the slides are the curriculum), and the convex hull of a point set (Ch. 8.6.2). |
| 05.11.2012 | DK | OJD 3437 Sem.rom C |
The rest of the slides fom last time (PK) Coping with NP Completeness I: Smart exhaustive search; approximation; heuristics |
Lecture 10 pages 236-261 in Kompendium til IN210 by Karabeg/Djurhuus. Exercises for November 13: No. 32, 34 and 36 in Kompendium til IN210 by Karabeg/Djurhuus. The solutions are provided in Kompendium. |
| 12.11.2012 | DK | OJD 3437 Sem.rom C | 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. The solutions and the answers are provided in Kompendium. Last regular lecture (but at 26/11 there will be a lectue where one can ask questions and we look at the exam from 2012) |
| 19.11.2012 | No lecture |
|
||
| 26.11.2012 | DK, PK and SK | OJD 3437 Sem.rom C | Go through last year's exam, and answer questions | |
| 16.12.2012 | Exam |
|
||