Algoritmer, datastrukturer och komplexitet våren 2008

Tidigare aktuell information

Restlabbsredovisning
Under skolans labbvecka 9-13 juni 2008 så kommer det att gå att redovisa ADK-restlabbar. Anmäl dej på labbveckans webbsida. Nästa tillfälle att redovisa restlabbar blir sista veckan i augusti 2008.

Munta
Du som har godkänt på båda mästarproven och teoritentan och dessutom har minst betyg C på minst två av dessa moment (inräknat betygshöjningar från extralabbar) få anmäla dej till munta den 20 maj. Du anger vid bokningen vilket betyg du vill satsa på. Muntan är individuell och tar 90 minuter. Du får en uppgift på varje moment som du behöver höja ditt betyg på (1, 2 eller 3). Sedan får du fundera i lugn och ro under en timme med kursboken som hjälpmedel. Slutligen redovisar du muntligt under en halvtimme. Du måste få godkänt på alla uppgifter för att få det betyg du satsade på.

Tryck här för att hämta bokningslistor för muntan:

Ommästarprov 2
Den som har mästarprov 2 kvar ska lösa ommästarprov 2 och redovisa den 12-13 maj.

Tryck här för att hämta bokningslistor för ommästarprovet:

Teoritentan
Teoritentan är den 13 maj klockan 9.00 i sal F1. Ingen föranmälan. Inga hjälpmedel. Skrivtiden är två timmar. Direkt efter tentan vidtar obligatorisk tentagenomgång och kamraträttning. Det hela beräknas vara klart omkring 12.15. Ingen förhandsanmälan till tentan!

Regler för högre betyg
Här kan du se hur man gör för att få högre betyg i kursen. Där finns också ett kalendarium över den återstående delen av kursen.

Extrauppgift i labb 4
Den som vill göra extrauppgiften i labb 4 för att (utan munta) få betyg A eller B på lärandemålet som har med hantering av problem med hög komplexitet att göra kan redovisa den på restlabbsredovisningstillfällena 8-9 maj, se nedan. Därefter är det försent. Labblydelsen är nu förtydligad, så använd den nya versionen. Notera att extralabben ska göras individuellt eller i tvåmannagrupper.

Ommästarprov 1 och betygskomplettering av mästarprov 1
Den som har mästarprov 1 kvar ska lösa ommästarprov 1 och redovisa den 12-13 maj.

Tryck här för att hämta bokningslistor för ommästarprovet:

Den som vill ha högre betyg på mästarprov 1 kan lösa denna uppgift och redovisa den på ett restlabbsredovisningstillfälle 8-9 maj. Notera att denna uppgift ska göras individuellt eller i tvåmannagrupper. Ett förtydligande till uppgiftslydelsen: den dolda styrkan ska vara olika för alla n spelare.
Här är kortfattade kriterier för bedömningen av sportturneringsuppgiften:
Betyg C: För att programmet ska godkännas måste det följa specifikationen och klara av att göra statistik upp till åtminstone n=64 på rimlig tid.
Betyg B: Programmet måste dessutom använda någon smart algoritm eller datastruktur som snabbar upp det.
Betyg A: Programmet ska genomgående använda väl valda algoritmer och datastrukturer och klara av att göra statistik upp till åtminstone n=1024 på rimlig tid (cirka en sekund för en 1024-turnering).

Restlabbsredovisning
Sista tillfällena under kursens gång att redovisa labbar blir 8 maj kl 15-17 och 9 maj kl 10-12, i Spelhallen som vanligt.

Mästarprov 2
Nu är det dags att boka redovisningstid till mästarprov 2. Gör telnet eller ssh till hippograff.nada.kth.se och ge kommandot bok new adk08

Labb 4
Eftersom det är ett NP-fullständigt problem kan det ta väldigt lång tid att lösa en reducerad instans, ifall reduktionen har gjort den stor. Om Kattis inte lyckas lösa instansen inom en rimlig tid kommer hon att avbryta sin körning och svara Judge Error. Det kan alltså vara så att reduktionen är korrekt trots att Kattis ger Judge error. Den som får det och kan bevisa reduktions korrekthet vid redovisningen får godkänt utan Kattis godkännande. Enklast är nog ändå att förenkla reduktionen så att Kattis accepterar den.

Mästarprov 2 finns nu tillgängligt.

Handledarbrist på ADK-labb 2
En stor del av labbhandledarna som skulle ha tagit emot redovisningar på ADK idag 28 mars var tvungna att lämna återbud på ett mycket sent stadium. Därför blev labben underbemannad, vilket jag ber om ursäkt för.
Av den anledningen utsträcks bonustiden, så att den som redovisar på labbtiden på torsdag 3 april OCH har fått godkänt av Kattis på alla tre labbmomenten senast klockan 24 idag 28 mars kommer att få bonuspoäng på labben.

På /info/adk08/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 med lösningsförslag.

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