Kursens mål

att implementera ett antal datastrukturer (ni är redan bekanta med t ex list,dict)
m h a algoritmer (punkt för punkt steg-förklaring för att angripa ett problem)
som sedan genom abstraktion (dölja implementering) exponerar dessas funktionalitet
Analys av tidskomplexitet algoritmer emellan.

Genomförande

Kursen innehåller följande undervisningsmoment.

Föreläsningar
- på campus, valfria.
- introducerar ny terminologi (med främst datastrukturer och algoritmer).
- Endast under period 3.
- 12 st
Övningar
- på campus, valfria.
- innehåller exempel relaterade till kommande KS:ar och Labbar.
- Ges i dubbel uppsättning (= samma innehåll) p g a schemakrockar.
- Endast under period 3.
- 7 st
Labbarna
- på campus och/eller distans
- ett obligatorisk presentationstillfälle per labbuppgift.
- Ges i dubbel uppsättning (=examinerar samma labb) p g a schemakrockar.
- Under period 3 & 4.
- 10 st
Kontrolllskrivningar
- på campus och/eller distans
- obligatoriska
- Ges på måndagar kl 17.15 (40 min skrivtid)
- Under period 3.
- Anledning: Det är redan tio labbar och för att det inte ska bli än fler så examineras delas av kursinnehållet med KS:ar
Betygshöjande moment
- Labbar med egenarbete
  - 2 st, för betyg C och A
- Munta
  - 2 delar, för betyg C och A
- Under period 4

Föreläsning 1 - Introduktion till kursen och repetition av förkunskaper
Föreläsning 2 - Abstrakta datatyper, lista, kö --> Examineras på laboration 2
Föreläsning 3 - Komplexitetsanalys, sökning, rekursion --> Examineras på KS1
Föreläsning 4 - Binära träd --> Examineras på laboration 3
Föreläsning 5 - Kryptering, datasäkerhet --> Examineras på KS2
Föreläsning 6 - Grafer, problemträd --> Examineras på laboration 4, 5
Föreläsning 7 - Prioritetskö, trappa (heap), bästaförstsökning, heapsort --> Examineras på KS3
Föreläsning 8 - Sortering --> Examineras på laboration 6
Föreläsning 9 - Datakomprimering --> Examineras på KS4
Föreläsning 10 - Hashning, bloomfilter --> Examineras på laboration 7
Föreläsning 11 - Automater, textsökning --> Examineras på KS5
Föreläsning 12 - (Kattis), Syntax, rekursiv medåkning, (testning), syntaxträd --> Examineras på laboration 8, 9, 10

Examination

Kursen DD1320 har två LADOK-moment:

Laborationer (de tio obligatoriska laborationerna + två betygshöjande laborationer) - LABD, 3 hp
Tenta (består av fem kontrollskrivningar + munta för högre betyg) - KONT, 3 hp

Betyg

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

		KONT
L A B D		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.

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.

Labbar

Moment LABD består av:

E-del med tio laborationer. Dessa räcker för att bli godkänd på labbkursen med betyg E.
C-del för att höja till betyg C på LABD.
A-del för att höja till betyg A på LABD.

Regler för E-labbarna

E-labbarna bör göras i par (och att vara fler är ej tillåtet).
Redovisningstid bokas via bokningssidan.
Lösningen ska laddas upp på Canvas senast dagen före redovisning, kl 20:00.
För att annonsera era mötesrum använder vi kösystemet, kurs "Tilda". I kommentarsfältet anger ni redovisningstiden när ni bokade. Syftet med bokningen är att ni ska slippa vänta lång tid i kön. Tiderna är dock ungefärliga.
För att få göra labbarna för högre betyg måste man ha redovisat varje E-labb i tid där tiderna framgår av kursens kalender/översikt. Om ni har förhinder vid något tillfälle, kontakta kursledaren i god tid och motivera varför ni har förhinder.
Redovisningar av veckans laboration är alltid prioriterat men i mån av tid kan ni vid redovisningstillfällena även få hjälp och / eller redovisa extra laborationer.
För att få hjälp så finns även:
- Ett hjälptillfälle på måndagar kl 17-19 (3-4 assistenter arbetar då).
- Allmänhandledningen, se https://www.kth.se/social/group/allmanhandledning

Betyg på LABD

C-labben och A-labben görs individuellt under period 4.
- För att få göra C-labben måste man ha redovisat varje E-labb i tid.
  - För att få göra A-labben måste man först ha blivit godkänd på C-labben.
C-labben och A-labben ska senast lämnas in på Canvas de datum som framgår av kursens kalender.
Redovisningar görs på separata bokningsbara tider under period 4 (dessa schemalägges ej då några i taget hanteras).
Labbdelen kan inte plussas.

Tenta

Kursens andra moment, KONT, utgörs av

Fem kontrollskrivningar (P/F) som ger betyg E om de blir godkända (krävs 4,0 av 6 poäng).
För högre betyg krävs muntlig tentamen i datastrukturer och algoritmer.

Tentan sker under P4 och får ett nytt format detta år (vi kan ej ha den på distans längre p g a bl a ChatGPT). Förbered dig inför tentamen genom repetition av kursmaterialet och extentorna från webben, se Tentabank.

Hjälpmedel

Tillåtna hjälpmedel på tentamen är:

Ett egenhändigt skrivet formelblad
- Formelbladet får vara max 2 A4-blad, dvs fyra sidor.
- Du får skriva precis vad du vill på fram- och baksidorna av båda dina papper.
- Formelbladet behöver inte vara handskrivet.
- Formelbladet ska lämnas in tillsammans med tentamen.
- Du får inte
  - ha ett formelblad som någon annan har skrivit.
  - göra kopiering av vare sig bilder eller text till formelbladet.
  - ha ett formelblad skapat gemensamt med andra.

=> det ska vara din skapelse och syftet är att du lär dig av det du skriver ned och repeterar!

Betyg på KONT

Fem godkända kontrollskrivningar ger betyg E.
C-delen kan höja tentabetyget till D eller C.
Den som har fått C kan med A-delen höja tentabetyget till B eller A.

Kurslitteratur

Miller & Ranum, Problem Solving with Algorithms and Data Structures Using Python (Länkar till en externa sida.)(interaktiv webbok)

Gerry Jenkins har gjort en serie videor (Länkar till en externa sida.) för varje avsnitt i boken.

Läsanvisningar

Avsnitt	interactive version (Länkar till en externa sida.)	Kompletterande material
Introduktion till kursen	1. Introduction (Länkar till en externa sida.)
	2. A Proper Class (Länkar till en externa sida.)
Abstrakta datatyper	4. Basic Data Structures (Länkar till en externa sida.)
Binära träd, rekursion	7.1-7.5, 7.7, 7.11-7.15. Trees and Tree Algorithms (Länkar till en externa sida.) (Länkar till en externa sida.) (Länkar till en externa sida.) 5. Recursion (Länkar till en externa sida.)(utom 4.12)
Komplexitetsanalys, sökning	3. Analysis (Länkar till en externa sida.) 6.2-6.4. Searching (Länkar till en externa sida.)
Problemträd	8.1-8.16. Graphs and Graph Algorithms (Länkar till en externa sida.)
Hashning	6.5. Hashing (Länkar till en externa sida.)
Sortering	6.6-6.14. Sorting (Länkar till en externa sida.)
Prioritetskö, trappa (heap)	7.8 - 7.10. Priority Queues with Binary Heaps (Länkar till en externa sida.)
Automater, textsökning	-	Aziz, Cackler, Young: Basics of Automata Theory (Länkar till en externa sida.) Georgy Gimel’farb: String Matching Algorithms (Länkar till en externa sida.)
Syntax, rekursiv medåkning	7.6. Parse Tree (Länkar till en externa sida.)	Matt Might: The language of languages (Länkar till en externa sida.) Parsing regex with recursive descent (Länkar till en externa sida.)
Datakomprimering	-	Debra A. Lelewer and Daniel S. Hirschberg: Data Compression (Länkar till en externa sida.)
Kryptering	-	Fördjupning: Aumasson, J., & Green, M. (2018). Serious cryptography : A practical introduction to modern encryption (1st ed.). (Länkar till en externa sida.)Kap 1, 2, 10 (digitalt läsbar via KTHB)

Kursanalys

Efter kursen kommer en kursanalys att göras. Kontakta kursledaren om du vill vara med i kursnämnden.