Information om DD2354, Algoritmer och komplexitet hösten 2007

Tenta

Lösning till tentan 2007-12-15 finns här

Komplettering

Tentan är rättad. De som har betyg C på den har möjlighet att göra en muntlig komplettering på den för högre betyg. Hör av dig om du är intresserad av detta. Jag föreslår tisdag den 8 januari kl 10 som en mötestid. Om tiden inte passar kan vi komma överns per mail om annan tid.

OBS: Tentan den 15 dec kommer att vara kl 10-13 (alltså 3 timmar). Tentan är en teoritenta och har inte riktigt samma form som tidigare. Som exempel ges här en teoritenta från kursen Algoritmer, datastrukturer och komplexitet.

Tenta

Lösningar

Aktuellt

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 ändras en del till detta läsår. Den är nu i möjligaste mån 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	Onsdag 15-17	V11	Introduktion. Presentation av grundläggande begrepp.
41	F2	Tisdag 10-12	V34	Grafalgoritmer.
	Ö1	Tisdag 15-17	D31	Introduktion.
42	F3	Måndag 10-12	D32	Giriga algoritmer.
	Ö2	Måndag 15-17	D33	Grafalgoritmer.
44	F4	Tisdag 10-12	E31	Divide and Conqueralgoritmer.
	Ö3	Tisdag 15-17	E36	Giriga algoritmer och Divide and Conqueralgoritmer.
	F5	Torsdag 8-10	D32	Dynamisk programmering.
45	F6	Tisdag 10-12	E52	Flödesalgoritmer.
	Ö4	Onsdag 8-10	D32	Dynamisk Programmering.
45	F7	Torsdag 8-10	D32	Komplexitet: Introduktion till NP-problem.
46	F8	Tisdag 10-12	E52	Mer om NP-problem.
	Ö5	Tisdag 13-15	B23	NP-problem.
47	F9	Tisdag 10-12	E52	Turing-maskiner. Oavgörbarhet.
	Ö6	Tisdag 13-15 10-12	E36	Oavgörbarhet. Mer om NP-reduktioner.
	F10	Torsdag 10-12	D35	PSPACE-problem.
	Ö7	Torsdag 13-15	E51	NP-reduktioner.
	F11	Fredag 10-12	D33	Approximationsalgoritmer.
48	F12	Tisdag 13-15	Q13	Approximationsalgoritmer forts.
	Ö8	Torsdag 10-12	D31	Approximationsalgoritmer.
49	F13	Tisdag 10-12	E52	Linjärprogrammering.
	Ö9	Tisdag 13-15	E53	Repetition.
	F14	Onsdag 8-10	E33	Randomiserade algoritmer.
	F15	Torsdag 10-12	D35	Parallella algoritmer.

Mästarprov

Mästarprov 1

8 nov: En liten korrigering har gjorts

Mästarprov 2

Föreläsningsanteckningar

Föreläsning 1

Övningar

Läsanvisningar

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 algokomp07

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 algokomp07

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 algokomp07

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.