| Dato | Undervises av | Sted | Tema | Kommentarer / ressurser |
|
21/8-2017
|
Dino Karabeg (DK) |
Introduction to Algorithms and Complexity
|
Lecture 1 pages 14-33 and Lecture 2 pages 36-42 and 46-55 in Kompendium til IN210 by Karabeg/Djurhuus. Weekly assignments (ukeoppgaver): Number 3,4,5 and 6 from the Kompendium (Ch. 4). The solutions are provided in the Kompendium. |
|
|
28/8-2017
|
Petter Kristiansen (PK)
|
String Matching
|
Ch 20, except 20.5 (see "Pensum/L?ringskrav")
|
|
|
4/9-2017
|
Stein Krogdahl (SK)
|
Dynamic Programming
|
Ch 9, and Ch. 20.5
|
|
| 11/9-2017 | SK | OJD Rom 2452 Pascal | Matching and flow in networks |
Ch. 14. |
| 18/9-2017 | PK | OJD Rom 2452 Pascal | 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. For Ch.10 see "Pensum/l?ringskrav". |
|
25/9-2017 |
SK and Rune Djurhuus
|
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?
|
First hour: Ch. 23.5 in textbook
|
|
| 2/10-2017 | DK | OJD Rom 2452 Pascal | Undicidability |
Lecture 2 pages 52-55, Lecture 3 main ideas from pages 56-59, Universal Turing machine construction from pages 62-63, pages 66-67 and 70-78; Lecture 4 pages 80-83 in Dino Karabeg og Rune Djurhuus' Kompendium til IN210 . |
| 9/10-2017 | PK and Torbj?rn Rognes | OJD Rom 2452 Pascal |
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 |
|
16/10-2017 |
DK
|
NP-completeness
|
Lecture 5 pages 106-131, Lecture 6 pages 132 - 139, definition of Satisfiability and statement and proof idea of Cook's theorem on pages 140-148 in Dino Karabeg and Rune Djurhuus' Kompendium til IN210.
|
|
| 23/10-2017 | DK | OJD Rom 2452 Pascal | Proving NP-completeness |
Lecture 6 pages 150-159; Lecture 7 pages 160- 183 in Dino Karabeg og Rune Djurhuus' Kompendium til IN210. Solutions are in Kompendium |
|
30/10-2017 |
DK
|
Coping with NP Completeness I: Smart exhaustive search; approximation; heuristics
|
Lecture 9, definition and NP-completeness proof of the TSP problem, pages 214-217; Lecture 10, concepts and main ideas on pages 236-273 in Kompendium til IN210 by Karabeg/Djurhuus. Exerci. Nov. 2 & 3: No. 32, 34 and 36 in Kompendium.
|
|
|
6/11-2017
|
DK
|
Coping with NP Completeness II: Average-case analysis; algorithms that do well on average; probabilistic and parallel algorithms
|
Lecture 11 pages 274-287, the main ideas of the Hamiltonicity algorithm pages 288-289; Lecture 12 p. 290-295 and only main ideas of material on pages 308 and 312-315 in Kompendium til IN210 by Karabeg/Djurhuus.
Solutions to problems are provided in Kompendium. The ten questions are intended to help you review the material presented in class – and detailed in Kompendium (see above).
|
|
|
13/11-2017
|
PK
|
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
|
|
| 20/11-20 | No lecture | |||
|
27/11-2017 |
DK, PK and SK
|
Go through last year's exam, and answer questions
|
||
|
15/12-2017
kl. 09:00
|
EXAM 2017
|
|
|
|