ID1020 Algoritmer och datastrukturer 7,5 hp
Denna kurs är avvecklad.
Sista planerade examination: HT 2022
Avvecklingsbeslut:
Kursen avvecklas vid utgången av HT 2022 enligt skolchefsbeslut: J-2022-0503.
Beslutsdatum: 2022-03-02
Kursen gavs sista gången HT 2020. Sista möjlighet till examination i kursen ges HT 2022.
Examination av TENA och ARBA erbjuds i period 2 2022.
Sista möjligheten att examineras i kursen (tentamen och laborationer) sker i P2 HT2022. Kursen har ersatts med kursen ID1021 (with a smaller scope). Vid intresse att delta i omexamination i ID1020 i P2 kontakta Robert Rönngren (mail)
Innehåll och lärandemål
Kursinnehåll
Grundläggande algoritmanalys:
- Enklare analys avseende algoritmers resursbehov i form av tid och minne.
Grundläggande algoritmer:
- enkla numeriska algoritmer
- sekventiella och binära sökalgoritmer
- djupet först- och bredden först-sökning
- sorteringsalgoritmer: urvalssortering, insättningssortering, Quicksort, heapsort, mergesort.
Grundläggande datastrukturer:
- linjära listor, stackar, köer, hashtabeller, binära träd, heapar, binära sökträd och problemträd.
Programkonstruktion:
- design och implementering av program som använder grundläggande algoritmer och datastrukturer för att lösa datalogiska problem.
Lärandemål
Efter godkänd kurs ska studenterna kunna
- beskriva ett antal vanliga algoritmer för sökning och sortering och deras egenskaper
- jämföra algoritmer med avseende på tids- och minnesåtgång
- implementera datastrukturer som linjära listor, stackar, köer, hashtabeller, binära träd och sökträd
- identifiera problem där datastrukturerna ovan är användbara och konstruera enkla algoritmer med dessa
- skriva program som använder algoritmer och datastrukturer med hjälp av goda programmeringsprinciper som t.ex. systematiska tester och abstraktion
- modellera problem som sökproblem och implementera algoritmer för breddenförstsökning, djupetförstsökning eller bästaförstsökning
i syfte att
- kunna konstruera program som löser problem genom att använda vanligt förekommande algoritmer och datastrukturer
- ha tillräckliga förkunskaper för att kunna läsa fortsättningskurser i datalogi.
Kurslitteratur och förberedelser
Särskild behörighet
Slutförd kurs i programmering motsvarande ID1018.
Aktivt deltagande i kursomgång vars slutexamination ännu inte är Ladokrapporterad jämställs med slutförd kurs. Detta gäller endast för student som är förstagångsregistrerad på den behörighetsgivande kursomgången eller har både denna och den sökta kursomgången i sin individuella studieplan.
Rekommenderade förkunskaper
Utrustning
Kurslitteratur
Examination och slutförande
När kurs inte längre ges har student möjlighet att examineras under ytterligare två läsår.
Betygsskala
Examination
- ARBA - Kursarbete, 4,5 hp, betygsskala: P, F
- TENA - Skriftlig tentamen, 3,0 hp, betygsskala: A, B, C, D, E, FX, F
Examinator beslutar, baserat på rekommendation från KTH:s handläggare av stöd till studenter med funktionsnedsättning, om eventuell anpassad examination för studenter med dokumenterad, varaktig funktionsnedsättning.
Examinator får medge annan examinationsform vid omexamination av enstaka studenter.
Möjlighet till komplettering
Möjlighet till plussning
Examinator
Etiskt förhållningssätt
- Vid grupparbete har alla i gruppen ansvar för gruppens arbete.
- Vid examination ska varje student ärligt redovisa hjälp som erhållits och källor som använts.
- Vid muntlig examination ska varje student kunna redogöra för hela uppgiften och hela lösningen.
Ytterligare information
Kursrum i Canvas
Ges av
Huvudområde
Utbildningsnivå
Påbyggnad
Kontaktperson
Övrig information
I denna kurs tillämpas EECS hederskodex, se: http://www.kth.se/eecs/utbildning/hederskodex.