Nada

^ Upp till kursens ingångssida.

Information om DD1352, Algoritmer, datastrukturer och komplexitet våren 1999

Senaste nytt

Redovisning av restlabbar

Det går bra att redovisa restlabbar på ordinarie terminalövningar för vårens kursomgång. Extra terminalövning! Sista tillfället att redovisa labbar och teoriuppgifter före tentan blir torsdag den 27 maj klockan 13-15 i Röd sal. Ingen anmälan. Nästa redovisningstillfälle blir i augustiomtentaperioden.

Sortering av aåä i labb 3. För att aåä ska sorteras som olika bokstäver i Solaris 2.6 som körs i t ex Brun sal så måste man ge kommandot

setenv LC_COLLATE C

innan man kör sort. Då sorteras bokstäverna i ordningen abc...xyzäåö. I det gamla operativsystemet kan man alternativt skriva

setlocale c

Varning för missbruk av RedBlackNode-pekare i labb 2! Den som använder rödsvarta träd bör se upp med följande. Funktionerna nodeSearch, insert, Succ, Pred, first och last returnerar pekare till noder inuti trädet. Använd bara dessa pekare medan trädet är oförändrat! Insättning i och borttagning ur trädet flyttar om innehållet i noderna så att pekare in i trädet plötsligt kan peka på andra noder än förut. Detta kan ge svårupptäckta fel.

Extraerbjudande till den som redovisar labb 2 i tid (senast 18 mars): det räcker att ditt program hittar en skärningspunkt, det vill säga, det räcker att du implementerar den algoritm som står i CLR. Du går dock miste om den bonuspoäng som du får om du redovisar hela labbuppgiften i tid. Du kan bara utnyttja detta erbjudande om du redovisar senast den 18 mars.

Implementationer av röd-svarta träd till labb 2 finns i Java på /info/adk01/RBtree/ och i C på /info/adk01/thomasn/newredblacktree.c. I labblydelsen står att man kan använda skipplistor istället, men det blir inte så bra eftersom man måste kunna hitta ett elements närmast föregående element, och den operationen finns inte i skipplistor.

Tips för den som labbar i Java om programmet tar för lång tid: Förmodligen använder du någon Javabiblioteksklass som Vector eller LinkedList. Tänk då på att metoderna add och remove har tidskomplexiteten O(n) utom då man sätter in eller tar bort först eller sist i en LinkedList. Metoderna set och get på en LinkedList tar också tid O(n). Använd alltså inte dessa metoder inuti slingor eller procedurer som anropas många gånger!

Sist på denna webbsida finns en uppsättning trevliga webblänkar om algoritmer, datastrukturer och komplexitet.

I första uppgiften i hemtal 1 står tiden ska vara polynomisk i n, k och s. Stryk k, dvs ändra till tiden ska vara polynomisk i n och s. k kan vara olika för olika reaktioner och ska inte ingå i tidskomplexitetsuttrycket. Jag vill också förtydliga att det kan finnas flera reaktioner som framställer samma ämne.

För att labbredovisningsdatumet inte ska krocka med uppsatsinlämningen i Diskret matematik senareläggs sista bonusdatumet för labb 1 med en vecka till den 17/19 februari. Det går förstås bra att redovisa labben tidigare i alla fall. Tänk på att bonusdagen för labb 2 inte ändras.

Regler för komplettering av gamla ADK (2D1353).

Du får också se senaste nytt när du loggar in om du gett kommandot course join adk01, se nedan.

Lärare

Kursledare och föreläsare är Viggo Kann, viggo@nada.kth.se. Mottagningstid är fredagar klockan 11.00-12.00, telefon 08-790 62 92. Övningsassistenter för dom fyra grupperna är
  1. Öjvind Johansson, ojvind@nada.kth.se
  2. Staffan Ulfberg, staffanu@nada.kth.se
  3. Lars Ivansson, ivan@nada.kth.se
  4. Viggo Kann, viggo@nada.kth.se

Kurslitteratur

Kurslitteraturen ska läsas på egen hand parallellt med kursen. Föreläsningar och övningar täcker endast en del av kursmaterialet.

Kursböcker

En detaljerad läsanvisning inför tentan finns.

Kursbunt

Kursbunten kan köpas på Nadas elevexpedition för 10 kr. Papper som delas ut under kursens gång kommer att finnas i en pärm i hyllan utanför expeditionen.

Schema

Schema för vecka 3, 1999

TidMåndagTisdagOnsdagTorsdagFredag
8
9
10
11Föreläsning
D1
12
13
14Föreläsning
D1
Övning
D31-34
15
16
17

Schema för vecka 4-8, 1999

TidMåndagTisdagOnsdagTorsdagFredag
8
9
10
11Föreläsning
D1
12Terminalövning
gr 3-4, Brun, Gul
13
14Föreläsning
D1
Övning
D31-34
15
16Terminalövning
gr 1-2, Brun, Gul
17

Schema för vecka 9, 1999

TidMåndagTisdagOnsdagTorsdagFredag
8
9
10
11
12
13
14Terminalövning
gr 3-4, Brun, Gul
15
16Terminalövning
gr 1-2, Brun, Gul
17

Schema för vecka 11-12, 16, 1999

TidMåndagTisdagOnsdagTorsdagFredag
8
9Terminalövning
gr 3-4, Röd, Orange
10
11Föreläsning
D1
12
13
14Föreläsning
D1
Övning
D31-34
15
16Terminalövning
gr 1-2, Brun, Gul
17

Schema för vecka 17-19, 1999

TidMåndagTisdagOnsdagTorsdagFredag
8
9
10
11Föreläsning
D1
12
13
14Föreläsning
D1
Övning
D31-34
15
16
17

Detaljschema

Kursen består av 24 föreläsningar och 12 övningar. Följande tabell visar vad som preliminärt kommer att behandlas under föreläsningarna och övningarna.
Period 3
F1 19 januari
Introduktion, repetition av algoritmanalys, beräkningsmodeller, bitkostnad och enhetskostnad, undre och övre gränser. (Har 6)
F2 20 januari
Repetition av sortering, undre gräns för sortering, korrekthet. (Har 5)
Ö1 20 januari
Algoritmanalys.
F3 26 januari
Repetition av datastrukturer (heapar, binära träd), balanserade träd. (CLR 14)
F4 27 januari
Grafer: representation, sökning, maximala flöden. (CLR 23,25.1-25.2, se också Biggs)
Ö2 27 januari
Grafalgoritmer.
F5 2 februari
Grafalgoritmer: minimala spännande träd, kortaste stigar. (CLR 24,27.1-27.3, se också Biggs)
F6 3 februari
Algoritmkonstruktion: dekomposition, dynamisk programmering och giriga algoritmer. (Har 4 samt CLR 16)
Ö3 3 februari
Dekomposition och dynamisk programmering.
F7 9 februari
Algoritmkonstruktion: totalsökning, exempel på dekomposition och dynamisk programmering. Sortering i linjär tid. (Har 4 samt CLR 16)
F8 10 februari
Geometriska algoritmer. (CLR 35)
Ö4 10 februari
Dekomposition och dynamisk programmering.
Labb 1 17 och 19 februari
Flöden och matchningar, redovisning.
F9 16 februari
FFT - snabb Fouriertransform. (CLR 32)
F10 17 februari
Kinesiska restsatsen, översikt över algoritmer. (CLR 33.5)
Ö5 17 februari
Algoritmkonstruktion.
Hemtal 1, senast måndag 22 februari
Algoritmer.
F11 23 februari
Datastrukturer: skipplistor, praktiska datastrukturer.
F12 24 februari
Datastrukturer: bloomfilter. Tillämpning: rättstavning.
Ö6 24 februari
Datastrukturer.
Period 4
F13 16 mars
Introduktion till komplexitet. (Har 7)
F14 17 mars
Reduktioner.
Ö7 17 mars
Reduktioner.
Labb 2 17 och 18 mars
Skärning mellan linjesegment, redovisning.
F15 23 mars
Oavgörbarhet. (Har 8)
F16 24 mars
Enkla beräkningsmodeller (turingmaskiner, ändliga automater) och deras kraftfullhet. (Har 9)
Ö8 24 mars
Oavgörbarhet.
F17 20 april
Formell definition av NP och co-NP, polynomisk reduktion, Cooks sats. (Har 7 samt CLR 36.3-36.4)
F18 21 april
NP-fullständighetsbevis.
Ö9 21 april
NP-fullständighetsbevis.
Labb 3 21 och 22 april
Konkordans, redovisning.
F19 27 april
NP-fullständighetsreduktioner.
F20 28 april
Komplexitetsklasser.
Ö10 28 april
NP-fullständighetsbevis.
F21 4 maj
Approximationsalgoritmer. (CLR 37)
F22 5 maj
Mer om approximation. (CLR 37)
Ö11 5 maj
Komplexitetsklasser, approximationsalgoritmer.
Hemtal 2, senast måndag 10 maj
Komplexitet.
F23 11 maj
Parallella och probabilistiska algoritmer och komplexitet. (Har 10-11)
F24 12 maj
Repetition.
Ö12 12 maj
Repetition.

Kursregistrering

Alla som vill gå kursen måste registrera sig på den. Detta görs med kommandot

res checkin adk01

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 adk01

Detta kommando gör två saker:

När du är klar med kursen ger du kommandot

course leave adk01

för att återställa allt.

Från och med hösten 1998 gäller att endast dom teknologer som delfakulteten lagt in i Ladok som studerande på en kurs kan godkännas på kursen. Om ADK inte är obligatorisk för dig (det vill säga om du inte går i D2) måste du först välja kursen vid ditt fakultetskansli som måste godkänna ditt val.

Obligatoriska moment

Kursen har tre obligatoriska moment i Ladok:
TEN1
Tenta, 3 poäng
HEM1
Hemtal, 1 poäng
LAB1
Datorlaborationer, 2 poäng
Nedan finns detaljerad information om dessa moment.

Tenta

Ordinarietentan går lördagen den 5 juni 1999 klockan 14-19 i sal F41-F51.

Tentan består av en teoridel (om 20 poäng) utan hjälpmedel och en problemdel (om 30 poäng) med kursböckerna, föreläsningsanteckningar och egna anteckningar som hjälpmedel (men inga lösta tentor). För godkänt krävs minst 25 poäng. Den som presterat bra lösningar till båda hemtalen kan ha klarat av 12 poäng på problemdelen i förväg. Den som redovisat datorlabbarna i tid och har svarat rätt på teoriuppgifterna på labbarna får 9 poängs bonus på tentan. Frågorna på teoridelen behandlar bara det som tagits upp på föreläsningarna och nämnts i dom utdelade föreläsningsanteckningarna.

Nästa tentatillfälle blir onsdag den 18 augusti 1999 klockan 8-13 i sal L51.

Tentaresultatet anslås högst tre veckor efter tentan på institutionens anslagstavla på plan 3 (rakt under elevexpeditionen).

Klagomål på rättning av tentan lämnas in skriftligen till kursledaren inom tre veckor från det att tentaresultatet anslagits.

Anmälan till tentan

Du behöver inte anmäla dig till tentan.

Hemtal

Två obligatoriska hemtal kommer att delas ut. Dessa ska lösas individuellt och redovisas både skriftligt och muntligt. Skriftliga lösningar till dessa uppgifter ska lämnas till någon av lärarna eller lämnas in i bokhyllan utanför elevexpeditionen senast klockan 17.00 det datum som anges på uppgiftslydelsen. Klockan 17.00 låses dörrarna till Nadas korridorer. Den muntliga redovisningen kommer att ske senare samma vecka för någon av assistenterna på en tid som ska bokas i förväg.

Varje hemtal består av två uppgifter. För godkänt på det obligatoriska momentet HEM1 krävs att minst hälften av uppgifterna löses rätt (alltså 2 av totalt 4).

Varje hemtal motsvarar också två 3-poängstal på problemdelen av tentan. Den som klarar en hemtalsuppgift slipper göra motsvarande tal på tentan. Detta gäller på alla tentor som går inom ett kalenderår räknat från kursstart.

Den som inte klarat momentet HEM1 på hemtalen kan istället få det godkänt genom att klara (eller komplettera med) motsvarande tal på tentan.

Du kan se hur många poäng du fått på hemtalen om du ger kommandot

res show adk01

på någon av Nadas Unixdatorer.

Labbar

Tre obligatoriska datorlabbar ingår i kursen. Dessa utgör momentet LAB1. Labbarna ska helst göras i tvåpersonsgrupper. En- och trepersonsgrupper kan godkännas i undantagsfall. Varje labb som redovisas senast det labbtillfälle som finns angivet på labben ger en bonuspoäng på tentan. På varje labb finns dessutom ett antal frivilliga teoriuppgifter. Den som vid redovisningen av en labb kan redogöra för lösningarna på teoriuppgifterna får två bonuspoäng.

Sammanlagt kan alltså labbarna ge 3+6=9 bonuspoäng på tentan. Bonuspoängen gäller på alla tentor på kursen som går inom ett kalenderår räknat från kursstart.

Det finns schemalagda labbtillfällen från och med andra veckan av kursen och till och med den vecka då labb 3 ska redovisas. Det kommer att finnas handledare tillgängliga på dessa labbtillfällen. Börja att göra labbarna i god tid och fråga dom handledarna om du får problem. Du kan redovisa alla labbarna vid alla labbtillfällen, men under det sista labbtillfället för varje labb kan bara den labben redovisas.

Hederskodex

Skolan tillämpar en hederskodex i alla sina kurser och varje student förutsätts tillämpa hederskodexen. Om du inte har läst den eller inte minns den: läs den nu!

Kurskatalog

Kursen har en katalog på Nadas Unixdatorer: /info/adk01. På denna katalog finns textfiler, programskelett, program och liknande som har med kursen att göra.

Synpunkter på kursen

Eftersom denna kurs kommer att ges för många elever under flera års tid är vi tacksamma för synpunkter på kursen. En datorstödd kursutvärdering kommer utföras. Synpunkter kan lämnas till lärarna.

Diverse länkar

Skicka gärna brev till Viggo om du har tips på lämpliga länkar för denna lista.

^ Upp till kursens ingångssida.


Sidansvarig: Viggo Kann <viggo@nada.kth.se>
Senast ändrad 16 januari 2010
Tekniskt stöd: <webmaster@nada.kth.se>