Till KTH:s startsida Till KTH:s startsida

- KursPM

Kursen DD1320 har två obligatoriska moment:

  • Tio laborationer - LAB1, 3 hp
  • Skriftlig tenta - TEN1, 3 hp

Kursen DD1325 har utöver dessa även:

  • Etikmoment - LAB2, 1,5 hp

Betyg

Slutbetyget i kursen är medelvärdet av betygen på moment LAB1 och TEN1, avrundat uppåt.

betyg på LAB1 betyg på TEN1
  A B C D E
A A A B B C
C B B C C D
E C C D D E

Betygskriterier - översikt

För betyg E ska man kunna avgöra vilken algoritm som löser ett givet problem, kunna beskriva algoritmen och demonstrera den steg för steg med givna data, samt implementera den. Motsvarande gäller för datastrukturer.

För betyg C ska kraven för betyg E vara uppfyllda, och dessutom ska man kunna jämföra algoritmer och datastrukturer och bedöma dessas lämplighet för ett givet problem. Här ställs också krav på tidsplanering. Se tidsgränser för aktuell kursomgång under Laborationer.

För betyg A ska kraven för betyg C vara uppfyllda, och man ska dessutom kunna modifiera/kombinera algoritmer och datastrukturer för att lösa nya problem. Här ställs också höga krav på tydlighet i algoritmbeskrivningar.

Funktionsnedsättning

Stöd via Funka
Om du har en funktionsnedsättning, kan du få stöd via Funka. 
https://www.kth.se/en/student/studentliv/funktionsnedsattning

Informera dessutom kursledaren om du har särskilda behov. Visa då upp intyg från Funka.

Föreläsningsar

Här är en preliminär plan över kursens föreläsninga:

  • Föreläsning 1 - Introduktion till kursen
  • Föreläsning 2 - Abstrakta datatyper
  • Föreläsning 3 - Komplexitetsanalys, sökning, rekursion
  • Föreläsning 4 - Binära träd
  • Föreläsning 5 - Grafer
  • Föreläsning 6 - Hashning, bloomfilter 
  • Föreläsning 7 - Sortering
  • Föreläsning 8 - Prioritetskö, trappa (heap), bästaförstsökning, heapsort
  • Föreläsning 9 - Automater, textsökning
  • Föreläsning 10 - Syntax, rekursiv medåkning, testning
  • Föreläsning 11 - Datakomprimering
  • Föreläsning 12 - Kryptering, datasäkerhet
  • Föreläsning 13 - Repetition inför tentan
  • Föreläsning 14 - Kattis, syntaxträd, tentagenomgång

Kursanalys

Kursansvariga studenter sökes!

Kursbok

cormen

  1. Thomas H. Cormen, Algorithms Unlocked  (kostar 255:- i kårbokhandeln)
  2. Kompletterande material om datastrukturer från Miller&Ranum, Problem Solving with Algorithms and Data Structures Using Python (webbok)
  3. Två artiklar om syntax av Matt Might
  4. Föreläsningsanteckningar

Läsanvisningar

Cormen | Miller Ranum (webbok)| Matt Might (artiklar)
Introduktion till kursen kap 1
 Abstrakta datatyper Basic Data Structures
 Binära träd, rekursion kap 2

Trees and Tree Algorithms 

(utom Priority Queues, Heap och AVL Tree)

 Komplexitetsanalys, sökning kap 2, 3
 Problemträd kap 5
 Hashning Hashing
 Sortering kap 4
 Prioritetskö, trappa (heap) kap 6
 Automater, textsökning kap 7
 Syntax, rekursiv medåkning
 Datakomprimering kap 9
 Kryptering kap 8

Labbar

Moment LAB1 består av:

  • E-del med tio laborationer. Dessa räcker för att bli godkänd på LAB1.
  • C-del (delas ut efter tentan) för att höja till betyg C på LAB1. 
  • A-del (delas ut efter tentan) för att höja till betyg A på LAB1.

Regler

E-labbarna får gärna göras i par (men inte i större grupp). C- och A-labben görs individuellt.

För att få göra C-labben måste man ha redovisat varje E-labb utom labb 1 på schemalagd labbtid enligt tabellen nedan. För att få göra A-labben måste man ha gjort C-labben.

Laboration Inlämning  Redovisning
Lab 1: Filer, klasser och listor i Python
Lab 2: Datastrukturer: kö dagen innan 20:00 vecka 4 2017
Lab 3: Binära träd dagen innan 20:00 vecka 5 2017
Lab 4: Grafer, breddenförst dagen innan 20:00 vecka 6 2017
Lab 5: Breddenförstsökning, visa vägen dagen innan 20:00 vecka 7 2017
Lab 6: Sökning och sortering dagen innan 20:00 vecka 8 2017
Lab 7: Hashtabeller dagen innan 20:00 vecka 10 2017
Lab 8: Kattis dagen innan 20:00 vecka 12 2017
Lab 9: Formelkoll dagen innan 20:00 vecka 13 2017
Lab 10: Molekylvikter dagen innan 20:00 vecka 14 2017
Lab för betyg C vecka 14 2017 vecka 15 2017
Lab för betyg A vecka 17 2017 vecka 18 2017

Lärare

NamnDatorpostadress (@kth.se)
Kursledare/föreläsare Alexander Baltatzis alba
Övningsassistent
Övningsassistent

Tenta

Kursens andra moment, TEN1, utgörs av en tentamen i datastrukturer och algoritmer.

Tentaanmälan görs via Mina sidor. Förbered dig inför tentamen med hjälp av kursmaterialet (glöm inte övningsuppgifter som inte hanns med på övningarna), och extentorna från webben, se Tentabank i menyn.

Hjälpmedel

Tillåtna hjälpmedel på tentan VT 2017 är:

  • Upp till fem egenhändigt handskrivna formelblad (fem A4).
    • Du får skriva precis vad du vill på fram- och baksidan.
    • Du får inte ta med ett formelblad som någon annan har skrivit.
    • Formelbladet ska lämnas in tillsammans med tentan.
    • Det går att söka dispans hos kursledaren om du har särskilda önskemål kring de handskrivna bladen. Sök i god tid innan tentamen.
  • Vårterminen 2017 får inte bok tas med på tentamen.

Betyg på TEN1

  • Tentan består av en E-del med sex uppgifter (E/F), en C-del med två uppgifter (C/D) och en A-del med en uppgift (A/B)
  • För godkänt krävs att alla E-uppgifter är godkända.
  • C-delen kan höja tentabetyget till D eller C, enligt tabellen nedan.
  • Den som har fått C kan med A-delen höja tentabetyget till B eller A.
  • Upp till två E-uppgifter, samt en C-uppgift kan kompletteras. 
Ena C-uppgiftenAndra C-uppgiftenBetyg på C-delen
C C C
C D C
C Fx Fx kan kompletteras till D vilket ger betyg C
C F E
D D D
D Fx Fx kan kompletteras till D vilket ger betyg D.
D F E

A-uppgiften rättas bara om man har eller kan få C på C-delen eller på begäran. Efter komplettering räknas hela tentans betyg om.

Övningar

Övningsalarna H32 och H33 ligger på Teknikringen 1 (fd Röda Korsets Högskola). Se bild.

Preliminär plan för övningarna

Övning nr Innehåll
1 Pythonuppgifter, abstrakta datatyper
2 Komplexitet, binära sökträd, rekursion
3 Problemträd, breddenförst, djupetförst
4 Hashning, sortering, prioritetskö, bästaförstsökning
5 Automater, reguljära uttryck, syntax
6 Komprimering, kryptering, testning
7 Repetition inför tentan