Information om DD2354, Algoritmer och komplexitet hösten 2009

Aktuellt

Tentaresultat

Tentaresultat finns inlagda i res (för DD2354). Tentorna kommer att finnas på expeditionen den 7 jan. Samma dag kommer en sammanställning av slutbetyg att göras och läggas ut i res.

Högre betyg?

Vill du ha högre betyg på kursen? Om du har fått minst betyg C på två av dom betygsatta kursmomentet (teoritentan, mästarprov 1, mästarprov 2) och minst betyg E på det tredje så får du kontakta mig för en muntlig tenta.

Lösningar till tentan: Lösningar

Två extentor:

Tider för redovisning av Mästarprov 2:

Den som har kvar Mästarprov 2 får kontakta mig via email. Möjlighet att redovisa kommer att finnas den 15 och 16 december.

Mästarprov 2 finns nu. Skall vara inlämnat den 7 dec: Mästarprov 2

Mästarprov 1: Mästarprov 1

For English-speaking students there is a rough translation of the home assignement here. It should be handed in November 16th at latest: Mästarprov 1 (English)

Kursinformation

Kursledare, föreläsare och övningsassistent är Johan Karlander, johank@nada.kth.se.

Kurslitteratur

Kurslitteraturen ska läsas på egen hand parallellt med kursen. Föreläsningar och övningar täcker endast en del av kursmaterialet.

Kursbok

Kleinberg, Tardos; Algorithm Design, Pearson Addison-Wesley.

Examination

Examinationsformen är anpassad till kursen DD1352 Algoritmer, datastrukturer och komplexitet. Examination

Kursbunt

Kursprogram (i stort sett denna text).
Kapitel 8 ur "David Harel: Algorithmics - the spirit of computing.
Tre exempeltentor.

Kursbunten kan köpas på Nadas elevexpedition. Papper som delas ut under kursens gång kommer att finnas i en pärm i hyllan utanför expeditionen. Kursen kommer att gå i period 1-2. Huvudvikten av undervisningen kommer att ligga i period 2.

Schema

Vecka		Tid	Plats	Innehåll
40	F1	Tisdag 15-17	E52	Introduktion. Presentation av grundläggande begrepp. Grafalgoritmer: Sökning.
	F2	Torsdag 13-15	E52	Grafalgoritmer: Kortaste vägar.
41	Ö1	Torsdag 13-15	E51	Grafalgoritmer.
42	F3	Tisdag 15-17	E31	Divide and Conquer-algoritmer.
	Ö2	Torsdag 13-15	D34	Divide and Conquer-algoritmer.
44	F4	Måndag 13-15	D32	Giriga algoritmer. Introduktion till dynamisk programmering.
	Ö3	Tisdag 13-15	D35	Giriga algoritmer och Divide and Conqueralgoritmer.
	F5	Onsdag 10-12	E51	Dynamisk programmering, fortsättning.
	Ö4	Fredag 10-12	D32	Dynamisk programmering.
45	F6	Måndag 13-15	Q24	Flödesalgoritmer. Introduktion till linjärprogrammering.
	Ö5	Tisdag 13-15	D42	Flödesalgoritmer och linjärprogrammering.
	F7	Fredag 13-15	D32	Linjärprogrammering, forts.
46	F8	Fredag 13-15	D31	Komplexitet: Introduktion till NP-problem.
47	F9	Måndag 13-15	D32	Mer om NP-problem.
	Ö6	Fredag 13-15	D32	NP-problem.
48	F10	Tisdag 10-12	K53	Turing-maskiner. Oavgörbarhet.
	Ö7	Tisdag 13-15	D35	Oavgörbarhet.
	F11	Onsdag 13-15	D41	PSPACE-problem.
49	F12	Måndag 13-15	D32	Approximationsalgoritmer.
	Ö8	Tisdag 13-15	D35	Approximationsalgoritmer.
	F13	Onsdag 13-15	D31	Approximationsalgoritmer, fortsättning.
50	F14	Tisdag 10-12	E51	Randomiserade algoritmer. Lokal sökning.
	Ö9	Tisdag 13-15	D42	Repetition.
	F15	Onsdag 13-15	D32	Introduktion till parallella algoritmer och kvantalgoritmer.

Hemuppgifter (Mästarprov)

Hemtal ett kommer att publiceras på denna sida måndagen den 2 nov och skall vara inlämnat senast måndag den 16 nov.

Föreläsningsanteckningar

Här kommer föreläsningsanteckningar att finnas. De redogör för innehållet i föreläsningarna i kortfattad form och utgör ett komplement till kurslitteraturen.

Övningar

Övning 1

Övning 2

Uppgifter att titta på inför övning 3

Övning 4

Uppgifter att titta på inför övning 5

Övning 6

Övning 7

Övning 8

Uppgifter att titta på inför övning 9

Läsanvisningar

Preliminärt skall ni läsa följande kapitel i läroboken.

Kap 1.
Kap 2: Framför allt 2.1, 2.2, 2.4.
Kap 3: Hela kapitlet.
Kap 4: Hela kapitlet utom 4.8-4.9.
Kap 5: Hela kapitlet.
Kap 6: 6.1, 6.2, 6.3, 6.4, 6.5, 6.8, 6.10 (kursivt)
Kap 7: 7.1, 7.2, 7.3, 7.5 resten av kapitlet kan läsas kursivt.
Kap 8: Hela kapitlet.
Kap 9: Hela kapitlet.
Kap 11: 11.1, 11.4 (en variant på problemet från föreläsningen), 11.5 t.o.m. sid 627, 11.8. Avsnitt 11.2 och 11.3 kan läsas kursivt.
Till föreläsning 13: Kap 11.6, 11.7 och föreläsningsanteckningar.
Kap 13: 13.2, 13.33, 13.4, 13.5

Kursregistrering

Alla som vill gå kursen måste registrera sig på den. Detta görs med kommandot


res checkin algokomp09

på någon av Nadas unixdatorer. Registrera dig så snart som möjligt efter att kursen börjat!

Du bör också ge kommandot

course join algokomp09

Detta kommando gör tre saker:

Du får se eventuella nya meddelanden från kursledaren varje gång du loggar in.
Du får kursens användarmiljö, det vill säga alla initieringar ensom kursledaren tycker att kursdeltagarna bör ha görs vid varje inloggning.
Du får en speciell kurshemsida som startsida i Netscape.

När du är klar med kursen ger du kommandot


course leave algokomp09

för att återställa allt.

Hederskodex

Grundregeln är att det jobb du gör i kursen (inlämningsuppgifter, tentor m.m.) ska du göra själv.

Ibland, speciellt när man skriver program, kan det vara nödvändigt att fråga någon annan (en kamrat eller en handledare) om hjälp med att hitta fel. Detta är tillåtet förutsatt att du uppfyller följande villkor.

Du måste förstå hela den färdiga lösningen, även de delar du fått hjälp med.

Varje annan form av samarbete och utnyttjande av andras lösningar betraktas som ett brott mot hederskodexen och kan bestraffas, t ex genom att du förlorar alla bonuspoäng eller får göra en ny uppgift.

Detta är en översatt och omarbetad version av den hederskodex som används i kursen Introduction to computer science vid Stanford University. Den tillämpas i många av Nadas kurser.