bild
Skolan för
elektroteknik
och datavetenskap
KTH / CSC / Kurser / DD1352 / adk09

Algoritmer, datastrukturer och komplexitet, våren 2009

Före detta senaste nytt

Restlabbar Den som har någon labb kvar att redovisa kan göra det på labbveckan. tisdag 9 juni klockan 16.30-18.30.

Kursutvärderingsenkät
Jag är mycket tacksam om du ägnar några minuter åt att fylla i kursutvärderingsenkäten. Den är det viktigaste redskapet för att samla in grund för vilka ändringar som ska göras i kursen till nästa år.

Tryck här för att hämta kursenkäten:

Tentan 2009-05-25 rättad
Tentan är nu rättad och kan hämtas ut på studentexpeditionen. Resultaten är inrapporterade i res. Slutbetygen på kursen kommer att rapporteras in efter muntan. Här är tentalydelse och lösningar.

Boka tid för munta
Du som har minst betyg C på minst två av dom tre betygsatta momenten i kursen och godkänt på det tredje kan få högre betyg genom att göra en munta 28-29 maj 2009.

Tryck här för att hämta bokningslistor till muntan:
Observera att den redovisningstid som du får kan vara en senare tid än hela redovisningspassets start, som är klockan 8.00 på torsdag och 12.00 på fredag. Mer information om muntan finns här.

Ommästarprov 2
Den som har mästarprov 2 kvar ska lösa ommästarprov 2 senast 25 maj.

Lösningsförslag till mästarprov 2 finns nu.

Instruktioner för högre betyg
Betygsättningen för kursen är målrelaterad. En beskrivning av hur man kan få betyg A, B och C finns här.

Extra redovisningstillfällen
Onsdag den 20 maj 2009 kl 15-17 och fredag den 22 maj kl 10-12 går det att redovisa labbar (även extralabben till labb 4) i Spelhallen.

Förtydligande till utdataformatet i extralabben till labb 4
Första raden i utdata talar om antalet skådespelare som fått roller.

Förtydligande av ommästarprov 1
Med "maximum possible window" i ledningen avses "minimum time gap" som ju ska vara så stort som möjligt. Det ska inte blandas ihop med tidsfönstren i indata.
För varje möjlig landningsordning av flygplanen i totalsökningen så ska man göra en binärsökning över "minimum time gap", och för varje landningsordning och tidsavstånd så ska man med en girig algoritm testa om det är möjligt att genomföra ett landningsschema med dom förutsättningarna.

Ommästarprov 1
Den som har mästarprov 1 kvar ska lösa ommästarprov 1 senast 13 maj.

Muntlig redovisning av mästarprov 2
Nu är det dags att boka tid för muntlig redovisning av mästarprov 2. Gör telnet till hippograff.nada.kth.se och ge kommandona module add resultat och bok new adk09

Svar på vanlig fråga om mästarprov 2
Flera har undrat om man får ändra på indata i kända NP-fullständiga problem. Svaret är nej, för även små ändringar av problemdefinitionen kan ändra komplexiteten radikalt; minns till exempel ormkaklingsproblemet som blir avgörbart om man inte begränsar sig till positiva halvplanet.
När man visar att ett problem B är NP-svårt genom att reducera ett känt NP-svårt problem A till det så är det alltså viktigt att man respekterar definitionen av A exakt. Det är inte tillåtet att till exempel modifiera indata. Om man behöver en annan definition av A i reduktionen så måste man först visa att A med den modifierade definitionen fortfarande är NP-svårt, till exempel genom att reducera A med det vanliga definitionen till A med den modifierade definitionen.
Som problem A i mästarprovet får bara användas problem som står som NP-fullständiga i föreläsningsanteckningarna, övningsanteckningarna eller kurslitteraturen.

Förtydligande till uppgift 1 på mästarprov 2
Den generella version av handelsresandeproblemet som åsyftas är denna:
Indata: Oriktad fullständig graf G med positiva heltalskantvikter, positivt heltal M
Fråga: Finns det en tur runt hörnen som passerar varje hörn i G exakt en gång och som har en sammanlagd kantviktssumma på högst M?

Lydelse till mästarprov 2
finns här. Mästarprovet ska lösas helt individuellt, och skriftliga lösningar ska vara inlämnade senast den 27 april klockan 10.15.

Lösningsförslag till mästarprov 1
finns här.

Labb 2
/info/adk09/labb2/exempelprogram/ finns exempelprogram som visar hur in- och utmatningen i första uppgiften i labb 2 bör läggas upp i Java, C och C++.

Ett testfall till labb 4 Graffärgning följer inte syntaxen
Kattis har fel på testfall 33 i problemet Graffärgning. Felet är att dom tre första talen (V E m) inte ligger på varsin rad utan på samma rad i detta testfall. Det blir alltså rätt om man läser in talvis men fel om man läser in radvis. Felet ska åtgärdas snart, men den som vill få sitt program godkänt av Kattis innan dess måste se till att programmet inte läser radvis. (Nu är felet åtgärdat.)

Mästarprov 1
Nu är det dags att boka tid för muntlig redovisning av mästarprov 1. Gör telnet eller ssh till hippograff.nada.kth.se och ge kommandot bok new adk09
Mästarprovet ska lösas helt individuellt, och skriftliga lösningar ska vara inlämnade senast den 2 mars klockan 10.15.

Andra föreläsningen som är torsdag 22 januari 10-12 repeterar sortering och datastrukturer. Stefan Nilssons gästföreläsning om effektiv kodning blir på föreläsningen på måndag (26 januari 2009).

All information om kursen finns på kurswebbsidorna. Den finns också samlad i kurs-PM som delas ut första föreläsningen och som finns här.

Kursen startar måndag den 19 januari klockan 10.15 i sal D1. Välkommen!

Köp kursbok på KTH-bokhandeln. Om du har Indakursboken räcker det att köpa ett supplement för 120 kronor!

Elever från tidigare kursomgångar som har moment kvar att redovisa i ADK ska titta här.

ADK samläses med kursen Algoritmer och komplexitet (SUALKO) på matte-datalinjens årskurs 3 på SU. SUALKO har en mindre labbkurs än ADK (och får 7,5 hp istället för 9). I övrigt är kurserna identiska.

Aktuell information

Labb 2
/info/adk09/labb2/exempelprogram/ finns exempelprogram som visar hur in- och utmatningen i första uppgiften i labb 2 bör läggas upp i Java, C och C++.

Mästarprov 1
Nu är det dags att boka tid för muntlig redovisning av mästarprov 1. Gör telnet eller ssh till hippograff.nada.kth.se och ge kommandot bok new adk09
Mästarprovet ska lösas helt individuellt, och skriftliga lösningar ska vara inlämnade senast den 2 mars klockan 10.15.

Copyright © Sidansvarig: Viggo Kann <viggo@nada.kth.se>
Uppdaterad 2009-08-25