Sidst opdateret: 28. maj, 14.35

Datalogisk Institut
Københavns Universitet

Datalogi 2A: Algoritmik
2002-2003

G2-genafleveringerne er nu færdigrettede og ligger klar til afhentning i 1.-delen; alle opgaver blev godkendt. Dermed ligger eksamenstidspunkterne også fast:
2. juni, N018
2. juni, N026
2. juni, N034
3. juni, N018
3. juni, N026
3. juni, N034
4. juni, N026
4. juni, N034

Fristen for indlevering af evalueringsskemaer er nu udløbet, og de ialt 45 skemaer er blevet opsummeret.

Som genaflevering af G2-opgaverne afleveres en ny besvarelse. Den oprindelige besvarelse og det udleverede rette-ark vedlægges.

G2-opgaverne er nu færdigrettede og ligger klar til afhentning i 1.-delen. Af 48 opgaver er 3 dumpet og 12 til genaflevering; de sidste 33 er godkendt. Der er dog stadig en del skønhedsfejl! Bemærk at der udover det anvendte retteskema er rettet inde i rapporterne; hvis man ikke kan læse krage-tæerne (eller iøvrigt har andre kommentarer) er man naturligvis velkommen til at henvende sig.

Grupper vi ikke husker at kunne sætte ansigt på ved forelæsningen d. 7. maj (hvor der blev evalueret) har desuden fået udleveret evalueringsskemaer. Vores hukommelse er naturligvis ikke fejlfri, så der kan være forekommet smuttere. Det vigtigste er imidlertid at så stor en del af de studerende som muligt deltager i evalueringen. Vi vil derfor meget opfordre til at man giver sin mening til kende (hvis man da ikke allerede har gjort det). Afleveringsfristen for aflevering af evalueringsskemaerne er derfor blevet udskudt til mandag d.19. maj!

Bedømmelse af G2-opgaverne vil ligge klar i 1.-delen torsdag d. 15. maj.

UDSÆTTELSE AF ØVELSER: På grund af det tilsyneladende store sammenfald med opgaver i andre kurser udskydes mandags-øvelserne en uge. Dette betyder, at der ikke afholdes øvelser mandag d. 12 maj, men i stedet mandag d. 19. maj. Sidste mandags-øvelser bliver dermed d. 26. maj. Torsdags-holdet fortsætter som normalt; "mandags-gængere" er naturligvis meget velkomne!

EVALUERING AF 2A: Det er blivet tid til den afsluttende evaluering af kurset. Vi opfordrer alle til at udfylde og aflevere det udarbejdede evalueringsskema [ ps | pdf ]

Øvelser i G2-opgaveperioden fordeler sig som følger:

Endnu en lille smutter: Opgave 34.4-7 har på mystisk vis indsneget sig på læsevejledningen og også på hjemmesiden; den overspringes til øvelserne!

Kursusbog 1 er nu udkommet og klar til salg. Pris: kr. 40,-

En lille smutter: Opgave 25-2(d) kan overspringes, idet resultatet delvis baserer sig på Johnsons algoritme, der sandsynligvis ikke er i pensum (men beskrevet i afsnit 25.3 for eventuelt interesserede).

Det er vigtigt at gøre sig formålet med de enkelte forelæsninger klart; de bør opfattes som supplement til bogens præsentation. Er man i forberedelsesmæssig tidsnød, bør man prioritere bogens fremstilling.

Opgaver til gennemgang ved øvelserne vil læne sig op ad stoffet i bogen, idet de mest centrale dele af pensum søges dækket.

Spørgsmål er som altid velkomne.

I erkendelse af at det nuværende system med genafleveringsmulighed for godkendelsesopgaver ikke virker efter hensigten og som følge heraf kræver uhensigtsmæssigt mange ressourcer, vil (gen-)afleveringskravene for kommende opgaver blive justeret: For det første gennem en præcisering af kravene til godkendelse. For det andet gennem en stramning af mulighederne for genaflevering; med andre ord hæves accept-grænsen for et "ærligt" forsøg. Nærmere detaljer følger i forbindelse med opgaverne.

Baggrunden for denne beslutning er bl.a. det forholdsvis store antal G1-opgaver, hvor dele af besvarelserne er meget mangelfulde, og hvor man tilsyneladende bevidst har kalkuleret med genafleveringsmuligheden.

G1-opgaverne er nu færdigrettede og ligger klar til afhentning i 1.-delen; af 42 genafleveringer er 38 blevet godkendt. Som tidligere nævnt foreligger der ikke en egentlig tilbagemelding, men man er naturligvis altid velkommen til at komme og diskutere sin besvarelse (og bedømmelsen af denne) med opgavestillerne.

Internt arbejdes der på en evaluering af opgaven (herunder vejledende kommentarer) til brug for både studienævn og studerende. I den forbindelse er kritik (både ris og ros) af opgaven og af forløbet generelt meget velkommen.

Formalia

Undervisere

• Kursusansvarlig i forårssemesteret, professor David Pisinger
• Professor Jakob Krarup
• Lektor Martin Zachariasen
• Lektor Pawel Winter

Undervisningsassistent

Lærebøger

Skemaoplysninger

Forelæsninger:

Onsdag 13-15 i aud. 4 (HCØ)

Øvelseshold:

Hold 1: Mandag 10-12 i N014 (DIKU)

Hold 2: Mandag 14-16 i N004 (DIKU)

Hold 3: Onsdag 10-12 NEDLAGT!

Hold 4: Torsdag 10-12 i N004 (DIKU)

Hold 5: Torsdag 14-16 NEDLAGT!

Spørgeåbent:

Kom og spørg om hvad som helst. Der er ikke tale om spørgetimer i traditionel forstand, men om et (individuelt) tilbud, hvis man skulle være kørt fast (eller ellers har noget på hjertet). Som udgangspunkt kan man kigge forbi når som helst, men det er ikke sikkert, at der er nogen. Det vil der dog være på nedenstående tidspunkter:

Tirsdag 11-12 i N323

Onsdag 11-12 i N323

Fredag 11-12 i N323

Punktsætning

Bedømmelse

Der stilles i løbet af kurset to G-opgaver (en i hvert semester), der skal godkendes (med mulighed for genaflevering). Godkendelse er en forudsætning for at kunne gå til eksamen!

Kurset afsluttes med en mundtlig, karaktergivende eksamen (i på forhånd kendte spørgsmål).

Programmeringssprog

Forelæsningsplan

Opgaver gennemgås ved øvelserne den følgende uge (første gang er i uge 7). Læs mere om opgaver og vejledninger her.

Forelæsningsplanen er vejledende og ret til ændringer forbeholdes!

Eksamensspørgsmål

Eksamens-HOWTO [ ps | pdf ]

1. Sorting (heapsort and quicksort in particular)
2. Binary Search Trees (red-black trees in particular)
3. Divide-and-Conquer (general principles and their application to the Closest Pair Problem)
4. Minimum Spanning Trees and use of heaps, disjoint sets
5. Segment Intersection Problem using Plane Sweep
6. Strongly connected components
7. Single-source shortest paths: Bellman-Ford's algorithm
8. Single-source shortest paths: Dijkstra's algorithm
9. All-pairs shortest paths
10. Maximum flow
11. NP-completeness: concepts and definitions
12. NP-completeness: an example of a proof
13. Branch-and-bound
14. Approximation algorithms
15. A fully-polynomial-time approximation scheme

Der kan ved eksamen stilles supplerende spørgsmål indenfor alle dele af pensum, f.eks.

• Greedy Paradigm
• Dynamic Programming
• Amortized analysis
• Heaps
• Non-computable problems (halting, totality, equivalence)
• Heuristics (simulated annealing, tabu search, genetic algorithms)

Dispositioner

Pensum

Cormen et al.:

1, 2, 3, 4.1-4.3, 6, 7, 8.1, 12.1-12.3, 13, 15.1-15.4, 16.1-16.3, 17, 19, 20, 21.1-21.3, 22.2-22.5, 23, 24 (ikke 24.4), 25.1-25.2, 26.1-26.3, 26.4 (kun til og med Lemma 26.15 (pp. 669-674)), 26.5 (kun figurerne 26.9, 26.10 samt definition af de deri benyttede begreber (pp. 681-689)), 33, 34 (ej Lemma 34.6), 35.0-35.3, 35.5.

Kursusbog 1:

Del 1

L. Goldschlager, A. Lister, "Computer Science", Prentice Hall, 1982:

3.1.1-3.1.4

Kursorisk stof

Cormen et al.:

Bevis for Lemma 34.6

Kursusbog 1:

Del 2