| Dato | Undervises av | Sted | Tema | Kommentarer / ressurser |
| 19/8-2015 | 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 the Kompendium. |
| 26/8-2015 | Stein Krogdahl (SK) | OJD 3437 Sem.rom C | Dynamic programming |
Ch. 9 and 20.5 |
| 2/9-2015 | Petter Kristiansen (PK) | OJD 3437 Sem.rom C | String Matching |
(Rest of) Ch. 20 |
| 9/9-2015 | PK | 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 |
| 16/9-2015 | PK and guest lecturer Torbj?rn Rognes from the group for Bio-informatics (at the Dept 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 (B&P) and Ch. 6.5 and 6.7 in Mark Allan Weiss (a copy of this will appear here) Slides first hour (revised) Relevant pages from Weiss (textbook for INF2220) Slides to guest lecture on bioinformatics |
| 23/9-2015 | SK and guest lecturer Rune Djurhuus | OJD 3437 Sem.rom C |
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! |
First hour: Ch. 23.5 in textbook The slides used by guest lecturer Rune Djurhuus
|
| 30/9-2015 | 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. |
| 7/10-2015 | 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. |
| 14/10-2015 | 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. Solutions are provided in Kompendium. |
|
21/10-2015 |
SK | OJD 3437 Sem.rom C |
Matching and flow in networks |
Ch. 14 exercises for October 27 Proposed solutions (New at 28/10. The answer to exercise 5 was wrong) |
| 28/10-2015 | DK | OJD 3437 Sem.rom C |
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. |
| 4/11-2015 | 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. |
| 11/11-2015 | PK | OJD 3437 Sem.rom C | Two-dimensional point sets: Triangulation and the convex hull |
For triangulation the slides are the curriculum. The convex hull algorithm is described in chapter 8.6.2 |
| 18/11-2015 | SK | OJD 3437 Sem.rom C |
Extra Lecture about Linear Programming (also called Linear Optimazation), and the Simplex algorithm. NB: We hope that many students will turn up to this lecture and will afterwards tell us (e.g. in a mail to steinkr@if.uio.no) how much of it you think can be included in an ordinary (two-hour) lecture e.g. in 2016!! |
Note: This is NOT part of the curriculum this year, but it is trial lecture testing what can be incuded about this topic in a normal (two-hour) lecture. There will be no exercises connected to this lecture. Thus, there will probably be no problem-solving session at Tuesday 24/11. |
| 25/11-2015 | NO LECTURE | |||
| 2/12-2015 | DK, PK and SK | OJD 3437 Sem.rom C | Go through last year's exam, and answer questions |
Answers to exam 2014 (Now with all answers in English) |
|
14/12-2015 kl. 09:00 |
EKSAMEN |