02105+02326 Algoritmer og Datastrukturer |
Øvelsestimer. Torsdage 8.00-10.30.
| Hold | Lokale | Retning | Type | Underviser |
|---|---|---|---|---|
| 1 | 308/holdområde 1. sal syd (+ 308/aud. 13 kl. 10.00-10.30) | diplom | regne | Lasse Kokholm |
| 2 | 308/holdområde 1. sal nord (+ 308/aud. 12 kl. 10.00-10.30) | diplom | regne | Anders Palmelund |
| 3 | 324/030 | civil | regne | Emil Imbert Villumsen |
| 4 | 324/040 (+ 306/aud. 33 kl. 10.00-10.30) | civil | regne | Mathias Kaas-Olsen |
| 5 | 324/060 | civil | regne | Nicolai Andre Brogaard Riis |
| 6 | 324/020 | civil/diplom | gennemgang | Frederik Rye Skjoldjensen |
Til kurserne er der også reserveret foyerområder i 324 (F003, F004, F005, F008) og et holdlokale 070 som frit kan benyttes. Se kort over områder og lokaler i 308 og 324. Udover de 6 undervisere ovenfor vil Simon Graverholt Søkilde og Anders Roy Christiansen bevæge sig frit rundt i alle lokaler og områder. Som et ekstra tilbud vil der være et undervisninghold med hjælpelærer tilstede i 324/040 torsdage 13.00-14.30. Der vil være særligt fokus på programmering.
Forelæsninger. Torsdage 10.45-12.00 i 116/aud. 81.
Ugeplanen er tentativ. Den vil blive opdateret i løbet af semestret. Der arbejdes med opgaver fra uge x i uge x+1.
Litteratur "Introduction to Algorithms", 3rd edition (CLRS) af Cormen, Leierson, Rivest og Stein og noter. Man er meget velkommen til at også at benytte supplerende bøger og andre kilder. Se forslag her.
Råd. Slides er designet til forelæsning. Bogen er den primære reference til stoffet. Vi anbefaler at skimme bogen før forelæsning og læse den grundigt efterfølgende. Vi anbefaler at printe slides og skrive noter i dem under forlæsningen.
| Uge | Emner | Slides | Ugeseddel | Litteratur | Demoer |
|---|---|---|---|---|---|
| 0 | Opvarmning: forberedelse, programmeringsforståelse. | Opvarmning | Kursusguide | ||
| 1 | Basale begreber I: introduktion, algoritmer, datastrukturer, toppunkter. | 1x1 · 4x1 | Introduktion | CLRS kap. 1 | Rekursiv toppunktsalgoritme |
| 2 | Basale begreber II: søgning, sortering. | 1x1 · 4x1 | Søgning og sortering | CLRS kap. 2 | Binær søgning · Indsættelsessortering · Fletning · Flettesortering |
| 3 | Basale begreber III: kompleksitet, O-notation, empirisk analyse. | 1x1 · 4x1 | Analyse af algoritmer | CLRS kap. 3 | |
| 4 | Datastrukturer I: stakke, køer, hægtede lister, træer. | 1x1 · 4x1 | Introduktion til datastrukturer | CLRS intro til del III + kap. 10 | Stak med tabel · Kø med tabel · Dynamisk tabel 1 · Dynamisk tabel 2 |
| 5 | Datastrukturer II: Prioritetskøer og hobe. | 1x1 · 4x1 | Prioritetskøer og hobe | CLRS kap. 6 + appendix B.5 | Bobl op og ned |
| 6 | Grafalgoritmer I: Grafer, repræsentation, søgning, modellering. | 1x1 · 4x1 | Introduktion til grafer | CLRS introduktion til del VI + kap. 22.1-22.4 + appendix B.4-B.5. | DFS · BFS |
| 7 | Grafalgoritmer II: topologisk sortering, implicitte grafer. | 1x1 · 4x1 | Orienterede grafer | CLRS introduktion til del VI + kap. 22.1-22.4 + appendix B.4-B.5. | Topologisk sortering |
| 8 | Datastrukturer III: foren og find, dynamiske sammenhængskomponenter. | 1x1 · 4x1 | Foren og find | CLRS kap. 21 pånær 21.4. + Algorithms, 4ed. kap. 1.5 | Hurtig forening · Vægtet forening |
| 9 | Grafalgoritmer III: mindste udspændende træ, Prims algoritme, Kruskals algoritme. | 1x1 · 4x1 | Mindste udspændende træ | CLRS kap. 23. | Prims algoritme · Kruskals algoritme |
| 10 | Grafalgoritmer IV: Dijkstras algoritme, korteste veje i vægtede grafer, korteste veje i DAGs. | 1x1 · 4x1 | Korteste veje | CLRS kap. 24 pånær 24.1 og 24.4. | Dijkstras algoritme |
| 11 | Datastrukturer IV: ordbøger, hashing. | 1x1 · 4x1 | Hashing | CLRS kap. 11 pånær 11.5. | hægtet hashing · lineær probering |
| 12 | Datastrukturer V: algoritmer på træer, predecessor datastrukturer, binære søgetræer. | 1x1 · 4x1 | Binære søgetræer | CLRS kap. 12 pånær 12.4. | Binære søgetræer |
| 13 | Opsamling: spørgetime, gennemregning af gammelt eksamenssæt, videregående kurser i algoritmik. |
| Civil | Civil - vejledende løsning | Diplom | Diplom - vejledende løsning |
|---|---|---|---|
| 02105-2009 | 02105-2009-vejledende | ||
| 02105-2010 | 02105-2010-vejledende | 02326-2010 | 02326-2010-vejledende |
| 02105-2011 | 02105-2011-vejledende | 02326-2011 | 02326-2011-vejledende |
| 02105-2012 | 02105-2012-vejledende | 02326-2012 | 02326-2012-vejledende |
| 02105-2013 | 02105-2013-vejledende | 02326-2013 | 02326-2013-vejledende |
| 02105-2014 | 02326-2014 |
CodeJudge. Kurset benytter CodeJudge systemet til afprøvning af kode. CodeJudge kan tilgås her.
Piazza. Kurset benytter Piazza som onlineforum til diskussion og hjælp med opgaver. Piazza kan tilgås her.
Hvilke programmerings- og matematikforudsætninger kræver kurset? De generelle forudsætninger er at man har gennemført (eller er godt i gang med) et indledende kursus i programmering og matematik. Mere specifikt skal man kunne anvende standard programmeringssprogskonstruktioner i imperative sprog som løkker, betinget udførsel, funktionskald, etc. Man kan frit vælge blandt et par standard programmeringssprog (fx Java og C++) til implementationsopgaverne. Kurset benytter og introducerer diverse emner fra diskret matematik (fx grafer) og det er derfor en fordel at have et kursus i diskret matematik, men ikke et krav. Det er ofte meget individuelt hvor meget programmering og matematik man behøver. Hvis man er tvivl om man har nok, anbefaler vi at bruge lidt tid på at arbejde med pensum og opgaverne fra de første par uger og vurdere derefter.
Jeg trænger til hurtigt at få genopfrisket mine programmeringskundskaber. Hvad anbefaler i? Vi anbefaler bogen "Introduction to Programming in Java", Sedgewick og Wayne. Bogen er skrevet af algoritmikere, er meget kompakt, målrettet mod teknisk programmering og dækker næsten alt det relevante for kurserne i kapitel 1, som kan hentes gratis på bogens hjemmeside.
Jeg får fejl X når jeg uploader mit program til CodeJudge. Hvad skal jeg gøre?/hvordan finder jeg ud af hvad fejlen er?/hjælp!? CodeJudge bør primært bruges som et sidste check for at ens kode virker korrekt (producerer et korrekt output svarende til input) og kører hurtigt. For at finde fejl og debugge din kode anbefaler vi at man konstruerer små testeksempler, afprøver ens kode på dem og arbejder med at finde fejlene.
Hvilke supplerende bøger/materialer anbefaler i? Vi anbefaler følgende glimrende kilder:
Er der vejledende løsninger til opgaverne? Der er vejledende løsninger til et stort udvalg af eksamensopgaverne (se ovenfor) som du kan bruge som gode eksempler på opgavebesvarelser. Til opgaverne på ugesedlen kan du til ethvert tidspunkt få hjælp, vejledning og hints fra en underviser. Det gælder også opgaver fra andre uger end den nuværende. Du er også meget velkommen til at aflevere skriftlige besvarelser på enhver opgave på ugesedlerne (ikke kun de frivillige afleveringsopgaver) til en underviser og dermed få feedback på dit skriftlige arbejde. Endelig er de fleste af de sværere opgaver på ugesedlerne klassiske opgaver, som der findes meget materiale om (både online og i bøger), som vi glædeligt vil være behjælpelige med at pege jer i retning af.
Hvad betyder "giv en algoritme"? Det betyder at man præsenterer en effektiv løsning, beskriver sin løsning kort, præcist og entydigt og argumenterer for korrekthed.
Hvornår afholdes den skriftlige eksamen? Dato og tid kan findes på Campusnet/Portalen. Typisk er dato bestemt vha. skemagruppen for kurset.