Algoritmer, datastrukturer och komplexitet, hösten 2012

Före detta senaste nytt

Tack för att ni har jobbat så bra med kursen! Det har varit riktigt roligt att hålla kursen. Tack också för att ni har svarat på alla forskningsenkäter som jag har delat ut. Nu är det bara en enkät kvar, nämligen kursutvärderingen, som har andra frågor än forskningsenkäterna. Jag hoppas att alla fyller i kursutvärderingen! I utbyte ser jag till att tentaresultaten blir klara under kvällen samma dag som tentan.
Viggo

Restlabbsredovisning 8 januari 2013

Restlabbar i ADK kan redovisas 8 januari klockan 13-15 i Spelhallen och Sporthallen. Nästa restlabbstillfälle blir i labbveckan i juni.

Ommästarprov
Ommästarprov 1 och ommästarprov 2 är till för den som ännu inte har godkänt på mästarprovsmomenten i kursen. Uppgifterna ska redovisas skriftligt senast 7 januari och muntligt 10 respektive 11 januari 2013.

Teoritentan rättad

Teoritentan 2012-12-13 (lösningsförslag) är nu rättad och resultaten finns i Rapp. Studentexpeditionen har julstängt så tentorna kan tyvärr inte hämtas förrän 7 januari. Tentaresultatet var bra med bara 5% betyg F. Den som fått FX kommer att få en kompletteringsuppgift per e-post att redovisa om tre veckor.
Den som vill ha mer förklaring om uppgift tre på tentan kan titta på anteckningarna till föreläsning 20 där kakelläggningsproblemet och verifiering av nej-instanster gicks igenom. Det står också i Harels kapitel i supplementet under rubriken "Finite Certificates for Undecidable Problems".

Diskussion om bedömningen av mästarprov 2
På sista föreläsningen ville några elever diskutera bedömningen av mästarprov 2. Jag har diskuterat saken med assarna. Det hela fick en oväntad utgång. Den som vill läsa mer om detta kan klicka här.

Fortsättningskurser i teoretisk datalogi
Lista över kurser i teoretisk datalogi som du kan läsa som fortsättning på ADK.

ADK-kalender december 2012-januari 2013

13 december kl 9-12: teoritenta med kamraträttning
13 december: dags att fylla i kursutvärderingen
17 december kl 9-12: redovisning av restlabbar och extralabben
17-19 december: munta för högre betyg (anmälan efter teoritentan men senast 14 december)
8 januari kl 13-15: redovisning av restlabbar, Spelhallen och Sporthallen
10-11 januari: muntliga redovisningar av ommästarproven (uppgifterna finns på kurswebben senast 11 december)

Labbrestredovisning
Den som inte har redovisat alla labbar än kan redovisa resterna den 17 december klockan 9-12 i Spelhallen och Sporthallen. Detta tillfälle är också enda tillfället att redovisa den betygshöjande extralabben till labb 4.

Kursansvariga studenter för ADK12 är Max Nordlund och David Karlbom . Om du har synpunkter på kursen och inte vill tala direkt med Viggo ska du prata med Max eller David.

Boka tid för munta

Muntan genomförs 17-19 december 2012.
Om du blev godkänd på teoritentan 2012-12-13 och (efter eventuell redovisning av extralabben) har minst betyg C på två av dom tre betygsatta momenten och minst betyg E på det tredje kan du anmäla dej till munta för att få högre slutbetyg. Ange vilket slutbetyg du önskar i bokningen. Bokning måste göras senast 2012-12-14 klockan 24. Avbokning kan göras fram till 2012-12-17 klockan 13 (då du vet om du är godkänd på extralabben).

Lösning till mästarprov 2 finns här.

Bokning av muntlig redovisning av mästarprov 2
Senast 19 november klockan 15 ska du boka in en individuell redovisningstid för mästarprov 2.

Mästarprov 2 finns tillgängligt. Skriftlig inlämning görs på CSC-studentexpeditionen, som har flyttat till plan 4 i E-huset, eller i Viggos postfack på samma plan.
Här är två förtydliganden till lydelsen:
Uppgift 1: Det går bra att anta att instansen till mängdpartitionering består av tal som är mindre än 2ⁿ (vilket följer av reduktionen till delmängdssumma i visualiseringssystemet AlViE (se schemasidan under föreläsning 22) tillsammans med reduktionen av delmängdssumma till mängdpartitionering som gavs på föreläsning 26).
Uppgift 2: Resekostnaderna kan vara olika mellan olika personer men behöver inte vara det.

Labb 26 oktober kl 8.15-12.00

Salar som är bokade för labben är:
Röd, Grön och Brun kl 8-12
dessutom Orange kl 10-12

Mästarprov 1

Lösningsförslag till mästarprov 1 gås igenom på övningen 25 oktober.

Visualiseringsdemonstration måndag 24 oktober 14-15 i K1

Efter lunch efter ADK-föreläsningen på måndag 22 oktober är det prosamföreläsning i samma sal (K1). Den föreläsningen är schemalagd 2 timmar men kommer bara att ta en timme. Därför lägger jag klockan 14-15 in en demonstration av visualiseringar av NP-reduktioner som min italienska kollega Pierluigi Crescenzi har utvecklat. Jag tror att demonstrationen är mycket klargörande om hur NP-reduktioner fungerar och hur dom bevisas. Demonstrationen är förstås helt frivillig. Alviesystemet och visualiseringarna kan laddas ner och köras lokalt, se schemasidan. Bokning av muntlig redovisning av mästarprov 1
Senast 8 oktober klockan 11 ska du boka in en individuell redovisningstid för mästarprov 1.

Förtydligande till uppgift 2 på mästarprov 1
Exakt m rutor ska skördas i skördeturen. I varje steg kan skördemaskinen gå till vänster, till höger eller rakt nedåt (fast inte till en ruta som redan skördats).
Mästarprovet ska lösas helt individuellt utan varje form av samarbete. Det ska redovisas både skriftligt och muntligt.

Övningen 4 oktober kl 10-12
På grund av D-dagen ges övningen på torsdag i två stora salar enligt följande:
sal K2 Cecilia Roes
sal H1 Marcus Dicander
Emmas grupp rekommenderas att gå till Cecilias sal K2 denna gång. Den som inte brukar följa någon särskild grupp rekommenderas att välja Marcus sal H1.

Supplementet separat (dvs utan Kleinberg-Tardos) är nu beställt till Kårbokhandeln och bör finnas för försäljning från måndag 10 september.

Invarianterna för exemplen på föreläsning 5 finns här.

Labbpartnermatchning efter föreläsningen 3 september 2012
Direkt efter föreläsningen kan den som inte har en labbpartner i ADK-kursen hitta en sån.

Köp av föreläsningsbilder och övningsuppgifter
Vid föreläsningarna 3 och 5 september kommer buntar med föreläsningsbilderna och övningsuppgifterna att säljas för 50 kronor. Ta med jämna pengar om du vill köpa en bunt eller gå ihop med en kompis och köp två för 100 kronor! Övningshäftet kommer inte att kunna hämtas förrän 5 september (mot uppvisande av föreläsningshäftet).

Kursstart!
Kursen börjar onsdag 29 augusti 2012 klockan 15.15-17.00 i sal F1. Välkommen!