| Dato | Undervises av | Sted | Tema | Kommentarer / ressurser |
|
23/8-2016
|
Dino Karabeg (DK) |
Lille Aud, KN |
Introduction to Algorithms and Complexity
NOTE: There are no "gruppeøvelser" this first week (24/8 and 26/8)!! |
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). |
|
30/8-2016
|
Petter Kristiansen (PK)
|
Lille Aud, KN
|
String Matching
|
Ch 20, except 20.5
|
|
6/9-2016
|
Stein Krogdahl (SK)
|
Lille Aud, KN
|
Dynamic Programming
|
Ch 9, and Ch. 20.5
|
|
13/9-2016
|
PK
|
Lille Aud, KN
|
Search strategies: Depth-first, breadth-first, priority, and A* search. |
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.
|
|
20/9-2016
|
SK and Rune Djurhuus
|
Lille Aud, KN
|
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?
|
|
|
27/9-2016
|
PK and Torbjørn Rognes
|
Lille Aud, KN
|
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) |
First hour: Ch. 6 in textbook (B&P) and
Ch. 6.5 and 6.7 in Mark Allan Weiss |
|
4/10-2016
|
DK
|
Lille Aud, KN
|
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.
|
|
11/10-2016
|
DK
|
Lille Aud, KN
|
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.
|
|
18/10-2016
|
DK
|
Lille Aud, KN
|
Proving NP-completeness
|
Lecture 6 pages 148-159; Lecture 7 pages 160- 183 in Dino Karabeg og Rune Djurhuus' Kompendium til IN210.
|
|
25/10-2016
|
SK
|
Lille Aud, KN
|
Matching and flow in networks
|
Ch. 14
|
|
1/11
|
DK
|
Lille Aud, KN
|
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.
|
|
8/11
|
DK
|
Lille Aud, KN
|
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.
|
|
15/11
|
PK
|
Lille Aud, KN
|
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
|
| 22/11 | No lecture | |||
|
29/11
|
DK, PK and SK
|
Lille Aud, KN
|
Go through last year's exam, and answer questions
|
|
|
8/12-2016
kl. 09:00
|
EXAM 2016
|
|
|
|