Datalogi C, efterår 2003 : Datastrukturer og Algoritmer

Forelæsninger finder sted tirsdag 9-12 i bygning 43, møderum-43-2.43 bortset fra 21. og 28. oktober hvor vi er i møderum 44.2.

Øvelser finder sted i 13.2 teorilokale + Datastue 13.2, bortset fra 3/10, 31/10, 7/11, og 5/12, 9/1 hvor det er i 42-1.37 (møderum i 42).

Kursusplanen revideres løbende som kurset skrider frem med opgaver og evt. justeringer.

Planen er er endnu ikke fyldt ud; de sidste detaljerne er på vej.

Overheads og Powerpoint o.lignende vil på vidt muligt bliver lagt ud på denne side, så de kan hentes som pdf.

Afleveringsopgaver: Se Aktuel status 19/1-2004 for godkendte opgaver og kursusbeståelse.

Dato	Forelæsningsemne	Øvelser
16/9-2003 9.00-12.00	Objekter, klasser og nedarvning: Indpakning af datastrukturer og algoritmer, gen(brug) og beskyttelse, Dele af kap. 1-4. (fortsættes næste gang) Dagens OHer som pdf
19/9-2003 13.00-16.00		Opgaver som pdf; Benytter følgende filer: EasyFile.java, duckling, stopwords. Beskrivelse af en løsning (pdf)
23/9-2003 9.00-12.00	Objekter, klasser og nedarvning (fortsat) Kap. 4. Dagens OHer som pdf
26/9-2003		INGEN ØVELSER: ÅRSFEST Opgaver til stoffet fra 23/9 som pdf.
30/9-2003 9.00-12.00	Tid- og pladsforbrug. Store-O-notation, eksempler Kapitel 5 Dagens OHer som pdf (Rettet version 1/10-2003!!)
3/10-2003 13.00-16.00		Opgaver til stoffet fra 30/9 som pdf. OBS: Opgave 2 i sættet er afleveringsopgave med frist tirsdag 14 oktober. NBNBNB: Lokalet er 42.1-37!!!!
7/10-2003 9.00-12.00	Java, nedarvning, dataabstraktion, Java Platform, konventioner og Collections API m.v. Kapitel 6 (m. reference til kap. 1-4) Forelæsningsnotat som html m. links til online Java-dokumentation
10/10-2003 13.00-16.00		Opgave til stoffet fra 7/10 som pdf.
14/10-2003 9.00-12.00	Om rekursion og design af algoritmer Dele af kap. 7 (ikke 7.4 og 7.7) Se læsevejledning! Dagens OHer som pdf
17/10-2003 13.00-16.00		Opgave til stoffet fra 14/10 som pdf. NB: Der henvises til bogens byttepengeprogram, som du kan hente her: http://www.cs.fiu.edu/~weiss/dsj2/code/MakeChange.java. En af opgaverne handlede om Fibonacci-tal. Tak til Christian Bohr-Halling og Nicolai Munk Petersen for at fremskaffe disse link som, som giver mere baggrund: http://research.microsoft.com/users/lovasz/dmbook.ps (specielt afsnit 6), http://www.cl.cam.ac.uk/~mgk25/kuhn-fa.pdf.
21/10-2003 9.00-12.00	Sortering: En klassisk lærestykke Kap. 8 (detaljerede beviser ikke eksamenspensum) Dagens OHer som pdf Se også kommentar til afleveringsopgave 1 OBS: møderum 44.2. SE KORT!
24/10-2003 13.00-16.00		Opgaver til stoffet fra 21/10 som pdf. OBS: Opgave 3 i sættet er afleveringsopgave med frist tirsdag 4 november. NB: Der henvises til bogens sorteringsprogram, incl. quicksort, som du kan hente her: http://www.cs.fiu.edu/~weiss/dsj2/code/Sort.java.
28/10-2003 9.00-12.00	Grafalgoritmer Kap. 14 minus 14.4 Dagens OHer som pdf (seneste udgave 27/10-2003 18:23) OBS: Også denne gang i møderum 44.2. SE KORT!
31/10-2003 13.00-16.00		Opgaver til stoffet fra 28/10 som pdf. NB: Der henvises til bogens grafalgoritmeprogram, som kan hentes her: http://www.cs.fiu.edu/~weiss/dsj2/code/Graph.java. NB: For at køre den, skal du også have andre file i samme katalog: Christian Bohr-Halling har været så venlig at samle dem (og rette små fejl i dem, så det hele kan compileres): http://akira.ruc.dk/~cbh/off/AlleFiler.zip. (de tidligere links pså i denne rubrik var gale.) Foregår i 42-1.37 (møderum i 42; vi har været der før) og vi har tilgang til computere i grupperum 42.2.20.
4/11-2003 9.00-12.00	Stakke, køer, hægtede lister Kap. 16, 17 og 11.1 (og for specielt interesserede: kap. 21) Dagens OHer som pdf
7/11-2003 13.00-16.00		Opgaver til stoffet fra 4/11 som pdf; spørgsmål 2.2 er afleveringsopgave med frist 18/11. Foregår i 42-1.37 (møderum i 42; vi har været der før) og vi har tilgang til computere i grupperum 42.2.20. OBS: Rettelse til afleveringsopgaven
11/11-2003 9.00-12.00	Træer, specielt søgetræer til repræsentation af mængder og afbildninger Kap. 18, minus de dele af 18.2 som handler om Huffman-koder og om metoden merge. Kap. 19, minus 19.2 og 19.3. Der lægges vægt på 19.4. Resten af kapitlet som baggrundsorientering; spring over Java-detaljerne. Dagens overheads som pdf. Kildetekster til program brugt i forel.: ExpressionTree.java, PlusTree.java, TimesTree.java, NumberTree.java, TestExpressionTree.java. Denne og alle følgende forelæsninger foregår i bygning 43, møderum-43-2.43
14/11-2003 13.00-16.00		Opgaver til stoffet fra 11/11 som pdf; Der henvises til følgende kildetekst: BinTree.java;
18/11-2003 9.00-12.00	Hashing Kap. 20. Spring over diverse matematiske detaljer. Dagens OHer som pdf (OBS: Rettet efter forelæsningen!)
21/11-2003 13.00-16.00		Opgaver til stoffet fra 18/11 som pdf. OBS: Opgave 2 i sættet er afleveringsopgave med frist tirsdag 5. december. Følgende filer skal bruges ved afleveringsopgaven: hamlet, shorthamlet.
25/11-2003 9.00-12.00	Prioritetskøer. Eksempel på anvendelse: Simulering. Kap. 21 minus 21.6. Kap. 13 minus 13.1. Dagens OHer som pdf
28/11-2003 13.00-16.00		Opgaver til stoffet fra 25/11 som pdf
2/12-2003 9.00-12.00	Eksempel på en helt andet slags programmeringssprog: Prolog. I Bratko, kap. 1-2. Overheads til BEGGE forelæsninger som pdf; se et par detaljer her.
5/12-2003 13.00-16.00		Opgaver til stoffet fra 2/12 som pdf; indeholder en overkommelig afleveringsopgave med frist 6/1. Eksempelprogrammer brugt i forelæsningerne: family (rettet 3/12-2003), predecessor, kredsloeb, vertihori, diverse. OBS-OBS: Kort vejledning om brug af SICStus Prolog Øvelserne foregår i 42-1.37 (møderum i 42; vi har været der før); der er sørget for gæste-logins, så I kan køre Prolog på Datalogis maskiner.
6/1-2004 9.00-12.00	Et programmeringssprog som er helt anderledes: Prolog, "programmering i logik", fortsat Bratko. kap. 3, 5. Overheads; se forrige forelæsning.
9/1-2004 13.00-16.00		Bl.a.: Evaluering, afslutning, mulige projektforslag. Opgaver til stoffet fra 6/1 som pdf Øvelserne foregår i 42-1.37 (møderum i 42; vi har været der før); der er sørget for gæste-logins, så I kan køre Prolog på Datalogis maskiner.
13/1-2004 9.00-12.00	INGEN FORELÆSNING!!!

Litteratur:

Links: Rettelsesliste, bogens programeksempler, og forfatterens hjemmeside med mange gode links.