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

Slides (partly updated after the lecture)

Exercises for Tuesday Sept. 1

Answers to the exercises

2/9-2015 Petter Kristiansen (PK) OJD 3437 Sem.rom C String Matching

(Rest of) Ch. 20



Exercises for tuesday Sept. 8.

Proposed solutions.

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


Exercises for tuesday Sept. 15.

Proposed solutions.

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)

Note on heights

Slides to guest lecture on bioinformatics

Exercises for Tuesday Sept. 22.

Proposed solutions.

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


Exercises for Tuesday Sept. 29

Proposed solutions

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.



Proposed solutions

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.



Proposed solutions

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.


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


Exercises for tuesday Nov. 17

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!!

Preliminary slides

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

Exam 2014

Answers to exam 2014 (Now with all answers in English)


kl. 09:00



Publisert 26. juni 2015 15:30 - Sist endret 7. feb. 2020 15:58