Datalogisk Institut
Københavns Universitet

Videregående algoritmik, blok 2B, 2004

(Eng. title) Advanced Algorithms.

Meddelelser

[25.1] Vejledende løsninger til eksamen, spørgsmål 1-10 findes her
[24.1] Kære VA-studerende!
Som aftalt fik David og jeg bedømt samtlige 88 besvarelser "dagen derpå", og censormødet fandt sted i fredags. Karaktererne blev efterfølgende afleveret til DIKUs studieadministration.
Davids løsning af Q11-Q20 findes allerede på hjemmesiden. Min løsning (Q1-Q10) blev ophængt på opslagstavlen, men flere har bedt om at også den del kommer på hjemmesiden. Jeg vil prøve snarest at få dette arrangeret. Der er ikke fundet direkte fejl i teksten til Q1-Q10, men - uden at dette var tilsigtet - blev to spørgsmål (Q7, Q10.1) lettere, end jeg oprindeligt havde forestillet mig.
Q7: Flere bemærkede, at svarmulighederne 7A) og 7B) er identiske, men heldigvis ikke korrekte. At der til hvert spørgsmål er et og kun et korrekt svar gælder således også Q7, hvorved både 7A) og 7B) udelukkes. 7D) _er_ det korrekte svar.
Q10: På nederste linie i opgavetekstens side 3 er kapaciteterne defi- neret som
c(v_i_,v_j_) = 2j - 1 hvilket umiddelbart giver max flow = 21; min cut: S={v_1_}, T=V\S.
I mit udkast til opgaven stod imidlertid
c(v_i_,v_j_) = 2j - i hvilket gør opgaven lidt vanskeligere, således som det også fremgår af min løsning.
At "i" blev til "1" i den endelige udgave af teksten betød blot, at næsten alle fik max points i 10.1.
Det var en fornøjelse at forelæse over [CLRS, Ch.26, Ch.29.] og en glæde, at så mange slap gennem nåleøjet. Til dem, der har fået lyst til mere: På gensyn på videregående kurser!
Venlige hilsener,
Jakob
[21.1] Der er en del studerende som er blevet forvirret af at ingen værdi af C(M) blev oplyst i opgave 19. Det rigtige svar blev dermed at man skulle skrive en formel, som angav hvorledes M udregnes. Alle besvarelser som blot finder Alice's hemmelige nøgle, får fuldt point.
I opgave 20 burde det være understreget at approximationsalgoritmen kører i polynomiel tid. Derfor er denne opgave bedømt mildt. (Cormen bogen opererer dog kun med polynomiel-tids approximationsalgoritmer, og FPTAS opgaverne på hjemmesiden definerer også absolut performance garanti på den rigtige måde).
[21.1] Karakterer er tilgængelige i førstedelen.
[20.1] Eksamensopgaverne vil som altid blive bedømt generøst :-). Såfremt nogen ikke består, vil der være reeksamen til sommer, hvor eksamenssættet vil tage udgangspunkt i de samme projektopgaver. Re-reaksamen til januar 2006 vil formentlig tage udgangspunkt i de nye projektopgaver som bliver stillet i VA vinterkurset.
[19.1] Vejledende løsninger til eksamen findes her (kun sidste 10 spørgsmål). Download venligst nyeste version, da der havde indsneget sig en fejl i den forrige.
[17.1] P4 opgave 8,9,11,19,23,26,28,33,34,35,36,37,38,41 kan afhentes i 1. delen efter middag
[16.1] Sætter-nisserne var på spil i projektopgave 3: det første eksempel, der viser en instans af MAX-CUT problemet. Den optimale løsning er S={2,4,6} og T={1,3,5} med løsningsværdi 8, og ikke den tidligere angivne løsning S={1,2,3} og T={4,5,6} med løsningsværdi 6. Enkelte studerende har som følge af fejlen i eksemplet troet at MAX-CUT skal dele grafen i to sammenhængende delgrafer. Dette er på ingen måde tilfældet. Et snit er alene en opdeling af grafens knuder i to mængder.
[13.1] Der afholdes en ekstra øvelsesgang for alle øvelseshold mandag 17/1. Hold 1 mødes 12.15 - 14.00 i N014. Programmet her er FPTAS-opgaven og prøveeksamenssættet. Resterende tid kan bruges på generelle spørgsmål.
Hold 3 mødes 9:15 - 11:00 i N026. Program: FPTAS-opgaven samt udvalgte approximationsopgaver. Derudover vil der også blive afsat tid til spørgsmål.
[11.1] Mindre rettelser til prøveeksamenssættet. Hent en ny version!
[10.1] Prøveeksamenssæt findes her. Sættet omfatter kun anden halvdel af kurset (og det er lidt kortere end hvad man vil forvente til eksamen). Eksamenssættet kommer til at bestå af 16 multiple-choice spørgsmål, og 4 tekst-spørgsmål.
[5.1] Optimal løsningsværdi for nogle af instanserne i P4 findes her.
[3.1] Nogle hints til P3 findes her.
[26.12] Optimal løsningsværdi for nogle af instanserne i P3 findes her.
[20.12] Grundet eksamen i blok 2 er der lidt lokalerokering:
Fredag d. 7. januar rykkes øvelseshold 5 (kl. 10-12) fra N022 til N037.
Fredag d. 14. januar rykkes øvelseshold 7 (kl. 8-10) fra N030 til N022.
[18.12] Mindre rettelse til opgave 7 i P3.
[13.12] Ramme program til P3 og P4 findes her. Benyt tar -xf ramme.tar til at pakke ud og læs README.txt
[10.12] Projektopgaverne P3 og P4 findes her.
[9.12] Øvelseshold 7 bliver lukket grundet manglende fremmøde - benyt et af de tilbageværende hold.
[5.11] Første uge holdes kun den sidste øvelsesgang på hvert hold.

Undervisere

Professor David Pisinger
Professor Jakob Krarup

Instruktorer

Lærebøger

[CLRS]	Cormen, Leiserson, Rivest, Stein: Introduction to Algorithms, Second Edition, MIT Press, Cambridge (2001).
[KB1]	Kursusbog: Branch-and-bound og Generelle optimeringsheuristikker (Fås i 1. delen).

Skemaoplysninger

Forelæsninger:: Mandag 14-16, torsdag 13-15 (begge gange i Auditorium 2, HCØ)
Øvelseshold:: studienævnet har kun bevilget penge til 4 øvelseshold:

Punktsætning

Kursets omfang svarer til 7.5 ECTS.

Bedømmelse

Undervejs i kurset stilles fire godkendelsesopgaver, som skal besvares i grupper på 2-3 personer (grupper med 1 person kræver accept fra instruktoren). For at blive godkendt skal opgaverne afspejle at der er gjort et reelt forsøg på at besvare hele sættet.

Godkendelse af samtlige opgavebesvarelser er en forudsætning for tilmelding til skriftlig eksamen. Genaflevering af ikke-godkendte besvarelser kan grundet den stramme tidsplan ikke finde sted.

Kurset afsluttes med en fire timers skriftlig eksamen, hvor lærebøger og egne noter må medtages. Omkring 2/3 af opgaverne vil tage udgangspunkt i de fire godkendelsesopgaver, og kan besvares med multiple-choice valg. Omkring 1/3 af opgaverne er tekstspørgsmål som går fagligt dybt i stoffet.

Elektronisk materiale

Ordbog over alle begreber fra lærebogen findes her.
Liste over rettelser til lærebogen findes her
Kompendium over NP-hårde problemer findes her.
Diskussion af kvantecomputeren og NP-fuldstændighed findes her og yderligere her.

Undervisningsplan

Foreløbig plan for kurset. Forbehold for ændringer.

Dato	Lærer	Indhold/Emne	Projektopgave	Litteratur	Plancher	Opgaver
ma:15/11 to:18/11	JK	Maximum flow i netværk	VA-P1 stilles 18/11	Cormen 26.1-26.4	Udleveres ved forelæsningen	26.1-1,26.1-2,26.1-4, 26.1-6,26.2-1, 26.2-3, 26.2-6,26.2-7,26-1(a)
ma:22/11 to:25/11	JK	Lineær optimering	VA-P1 afleveres 25/11	Cormen 29.1-29.5	Udleveres ved forelæsningen	26.2-2,26.4-6,26-1(b) 26-4,26-5 29.1-2,29.1-4,29.1-5 29.1-6,29.1-7,29.2-5 29.2-6,29.3-4
ma:29/11 to:2/12	JK	Lineær optimering	VA-P2 stilles 2/12	Cormen 29.1-29.5	Udleveres ved forelæsningen	29.4-1,29.4-2,29.4-3 29.4-5, 29.4-6,29-2 29.5-5,29.5-6,29-3,VA-P2, BBB Q1-Q12,PB Q1-Q12
ma:6/12 to:9/12	DP	Talteoretiske algoritmer, RSA kryptosystemet Primtalstest (randomiserede algoritmer)	VA-P2 afleveres 9/12	Cormen 31.1-31.7	ma:pdf 4pdf to:pdf 4pdf	a: 31.2-2, 31.2-3, 31.2-4, 31.2-6, 31.2-8, 31.3-1, 31.3-4. b: 31.4-1, 31.4-2, 31.6-3, 31.7-1, 31.7-2.
ma:13/12 to:16/12	DP	NP-fuldstændighed	VA-P3 stilles 16/12	Cormen 34.1-34.5	ma:pdf 4pdf to:pdf 4pdf	a: 34.1-1, 34.1-4, 34.1-6, 34.2-1, 34.2-4, 34.2-6, 34.2-8, 34-3 a)+b)+c) b: 34.1-2, 34.5-2, projektopgave 3
ma:3/1 to:6/1	DP	NP-fuldstændighed Branch and bound	VA-P3 afleveres 6/1 VA-P4 stilles 6/1	Cormen 34.1-34.5 Kursusbog, del 1	ma:pdf 4pdf to:pdf 4pdf	a: 34.3-3, 34.4-5, 34.4-6, 34.4-7, 34.5-1, 34.5-5, 34.5-6, 34-3 d)+e)+f) b: b&b opg. 1,7, projektopgave 4
ma:10/1 to:13/1	DP	Approximations algoritmer, Heuristikker	VA-P4 afleveres 13/1	Cormen 35.1-35.5 Kursusbog, del 2	ma:pdf 4pdf to:pdf 4pdf	a: b&b opg. 2,4,5,6,8,9 b: 35.1-1, 35.1-2, 35.1-4, 35.1-5, 35-1, FPTAS-opgave (pdf)
ma:17/1 to:20/1		Eksamen 19.januar

Litteratur

Cormen et al.:: 31.1-31.7, 26.1-26.4, 29.1-29.5, 34.1-34.5, 35.1-35.5
Kursusbog 1:: Del 1 (branch-and-bound), Del 2