Kursusansvarlig Philip Bille, phbi@dtu.dk, kontortid mandag + torsdag 12.30-13.00.
Underviser Hjalte Wedel Vildhøj.
Ø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. 13 kl. 10.00-10.30) | Diplom | Regne | Signe Kudsk Colding-Jørgensen |
| 3 | 324/040 (+ 306/aud. 37 kl. 10.00-10.30) | Civil | Regne | Marcus Skov Hansen |
| 4 | 324/050 | Civil | Regne | Gandalf Saxe |
| 5 | 324/060 | Civil | Regne | Andreas Halkjær From |
| 6 | 324/020 | Civil/Diplom | Gennemgang | Mikko Berggren Etienne |
Til kurserne er der også reserveret foyerområder i 324 (F003, F004, F005) som frit kan benyttes. Se kort over områder og lokaler i 308 og 324. Udover de 6 undervisere ovenfor vil Asger Juul Brunshøj og Anders Roy Christiansen bevæge sig frit rundt i alle lokaler og områder.
Forelæsninger Torsdage 10.45-12.00 i 116/81.
Litteratur "Introduction to Algorithms", 3rd edition (CLRS) af Cormen, Leierson, Rivest og Stein og noter. Vi anbefaler, at man anskaffer bogen i fysisk form, så man kan medbringe den til eksamen. Man er meget velkommen til også at benytte supplerende bøger og andre kilder. Se forslag her.
Peergrade Kurset benytter Peergrade.io til aflevering af obligatoriske opgaver og til at give og modtage feedback fra medstuderende. Peergrade.io kan tilgås her.
CodeJudge Kurset benytter CodeJudge 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.
Ugeplanen er tentativ Den vil blive opdateret i løbet af semestret. Vi arbejder med opgaverne fra ugeseddel x til øvelserne i uge x+1.
Slides 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 Programmeringsforberedelse | ||
| 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: orienterede grafer, 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, udvalgte opgaver fra et gammelt eksamenssæt, videregående kurser i algoritmik. |
Hver uge fra uge 1 til 9 er der en obligatorisk afleveringsopgave. Opgaverne bliver derefter rettet af en hjælpelærer, der vurderer opgaven og giver mundtlig feedback. Derudover giver og modtager man feedback fra andre studerende. Opgaverne skal laves individuelt (se samarbejdspolitik) og vurderes bestået/ikke bestået. For at gå til den skriftlige eksamen er det krav, at man har bestået mindst 3 af opgaverne og for hver afleveret opgave givet feedback på 3 opgaver. Den obligatoriske afleveringsopgave på ugeseddel x skal afleveres via Peergrade.io senest søndag i uge x+1 kl. 20.00 (dvs. søndagen umiddelbart efter øvelsestimen om opgaverne på ugeseddel x). Feedback på andres opgaver skal afleveres via Peergrade.io senest onsdag i uge x+2 kl. 20.00. Besvarelsen skal afleveres som en enkelt pdf-fil og være tydeligt markeret med navn og studienummer. Du er velkommen til at aflevere mere end 3 opgaver. Hjælpelæreren retter alle de opgaver du afleverer.
Format Besvarelsen af opgaverne skal være kort og præcis. De fleste opgaver kan besvares perfekt på 1-2 sider. Skriv jeres navn og studienummer øverst på første side. Lad være med at lave en forside og lad være med at gentage opgaveteksten. Vi anbefaler, at I bruger følgende-LaTeX skabelon template.tex (se fx http://www.latex-tutorial.com/ for en introduktion til LaTeX). Hvis du ikke ønsker at bruge/lære LaTeX kan du også aflevere en pdf fra andre programmer (Word, Pages, ...)
Samarbejdspolitik De obligatoriske opgaver skal laves enkeltvis. Det er ikke tilladt at samarbejde om opgaven, udover at diskutere opgaveteksten med undervisere og medstuderende, der tager kurset i samme semester. Man må under ingen omstændigheder udveksle, udlevere eller på anden måde kommunikere løsninger på (dele af) opgaven. Man må heller ikke bruge løsninger fra tidligere år, løsninger fra tilsvarende kurser, eller løsninger fundet på internettet eller andetsteds.
| 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 | ||
| 02105-2015 | 02326-2015 |
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.
Hvilke supplerende bøger/materialer anbefaler i? Vi anbefaler følgende glimrende kilder:
Hvad betyder "giv en algoritme"? Det betyder, at man beskriver sin (forhåbentligt) effektive løsning kort, præcist og entydigt, argumenterer for korrekthed af løsningen og analyserer kompleksiteten af løsningen. Medmindre andet er specificeret bør beskrivelsen være i naturligt sprog og ikke pseudokode.
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.
Jeg nåede ikke afleveringsfristen på en obligatorisk opgave/peergrading. Kan jeg aflevere senere? Det kan man ikke. Der kan være helt særlige omstændigheder (fx sygdom) hvor det er muligt at lave en undtagelse. I så fald kan skal man henvende sig til kursusansvarlig ifb. timerne eller til kontortid.
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 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.
Hvornår og hvor afholdes den skriftlige eksamen? Dato og tid kan findes på Campusnet/Portalen. Typisk er dato bestemt vha. skemagruppen for kurset. Adminstration står for booking af tid og lokale og jeg har ikke noget med det at gøre. Snak med dem eller dine medstuderende hvis du er i tvivl om tid eller sted.