Information om DD2354, Algoritmer och komplexitet hösten 2008

Aktuellt

Omtenta

Den 25 aug kl 9-11 är det omtenta i DD1352. Den fungerar också som omtenta för DD2354.

Tentan 081216

Lösningar

Tenta

Tentan är som tidigare sagts 3 timmar lång. Den är den 16 dec kl 14-17.

En extenta

Lösning

Redovisning av hemtal 2

Tider

Lärare

Kursledare, föreläsare och övningsassistent är Johan Karlander, johank@nada.kth.se. Telefon 070-686 74 66.

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

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.

Föreläsning 7 del 2 Anteckningar från en annan kurs jag håll en gång som också behandlade Linjärprogrammering.

Föreläsning 15 (del 1)

Föreläsning 15 (del 2)

Övningar

Övning 1

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 algokomp08

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 algokomp08

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 algokomp08

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.