Undervisningsplan

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.

Slides

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)

Slides

The relevant pages from Berman & Paul

Note on O-notation

Exercises for September 5

Solution exercises

03.09.2012 Stein Krogdahl (SK) OJD 3437 Sem.rom C Dynamic Programming

Ch. 9 and 20.5 in textbook

Slides

Exercises for September 12

Solutions for Exercises

The relevant pages from Berman & Paul

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)

Slides

Slides for second hour

Relevant pages from Weiss (textbook for INF2220)

Note on heights

Exercises for September 19

Solutions for Exercises

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.

Slides

Exercises for September 26

Solutions

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.

Slides

Slides about chess, Rune Djurhuus

Exercises for October 3

Solutions

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.

Slides

Exercises for October 10

Solutions

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.

Slides

Exercises for October 17

Solutions

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.

Slides

Exercises for October 24

The solutions are provided in Kompendium.

22.10.2012 SK OJD 3437 Sem.rom C Matching and Flow in Networks

Chapter 14

slides

Exercises for October 31

Solutions

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).

Slides

Exercises for November 6

Solutions

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.

Slides

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.

Slides

Exercises for November 20

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

Exam for 2012

Exam 2012 with answers

Slides and comments on Assignment 1

16.12.2012 Exam    

 

         

 

Publisert 21. juni 2013 13:57 - Sist endret 7. feb. 2020 15:58