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.
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.
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
På /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
På
/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.