Datastrukturer
Abstrakta datatyper, lista, iterator, stack, kö, träd, binära sökträd, heap, mängd, hashtabell, graf

Algoritmtekniker
Rekursion, backtracking, söndra och härska, Dijkstra’s algoritm, giriga algoritmer, dynamisk programmering

Analys av algoritmer
Komplexitet och empirisk analys av komplexitet

Sortering
Urvalssortering, instickssortering, shellsort, mergesort, quicksort, heapsort och lite om icke jämförande sorteringsalgoritmer

För godkänt betyg ska studenten:

1.       kunna implementera datastrukturer objektorienterat, använda och anpassa algoritmtekniker och datastrukturer samt designa egna algoritmer för att hitta effektiva lösningar på kända och nya problem

2.       kunna utvärdera algoritmers effektivitet och ha kännedom om komplexitetsbegreppet och kunna använda sig av detta vid val av algoritmer och datastrukturer

För att du ska lyckas med den här kursen och lära dig så mycket som möjligt inför ditt framtida yrkesliv är det viktigt att du deltar aktivt i undervisningsaktiviteterna, läser boken, programmerar mycket och att du gör detta kontinuerligt. Inför varje föreläsningstillfälle är det meningen att du ska ha sett föreläsningen aktivt, läst boken och programmerat flera av övnings-uppgifterna som hör till. Till tillfälle 2 hör föreläsning 1, till tillfälle 3 hör föreläsning 2, osv. För att premiera detta finns krysstal som ger bonus till ordinarie tentamen. Detaljerna hittar du under examination och på canvas.

Koffman and Wolfgang, Data Structures: Abstraction and Design Using Java 2nd Edition, ISBN-13: 978-0470128701

eller

Koffman and Wolfgang, Data Structures: Abstraction and Design Using Java 4th Edition, ISBN-13: 978-1119703617

Du behöver en fungerande programmeringsmiljö för Java på din dator.

Om du har en funktionsnedsättning kan du få stöd via Funka:

Funka- stöd för studenter med funktionsnedsättningar

A, B, C, D, E, FX, F

• LABA - Laborationer, 4,0 hp, Betygsskala: P, F
• TEN1 - Tentamen, 4,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.

För slutbetyg krävs godkänd tentamen (TEN1) och godkända laborationer (LABA). Slutbetyget grundas på momentet TEN1 med betygsskalan A, B, C, D, E, FX, F.

Möjlighet till plussning

Ja i mån av plats

Laborationer ( LABA )

LABA examinerar mål 1 och 2 med betyg P/F.

För att bli godkänd på momentet LABA skall du självständigt göra specifika uppgifter utlagda på canvas. Den första ska inlämnas skriftligt och man måste få godkänt för att få godkänt på momentet. Man får två åter innan man får underkänt och får göra denna i omtentaperioden. För att bli godkänd måste man också närvara vid redovisningarna för övriga uppgifter och där kunna redogöra för sina självständigt gjorda uppgifter. Vid varje redovisningstillfälle redovisas angivna uppgifter. De går inte att redovisa vid ett senare tillfälle. Beroende på hur väl man löst en uppgift och hur bra man kan redovisa uppgiften får man 0, 1 eller 2 poäng. Om man totalt får ihop 11 poäng eller mer av maximalt 16 poäng får man godkänt på momentet om uppgift ett är godkänd. Om man får ihop 7-10 poäng och har godkänd på uppgift 1 får man en extra chans att redovisa i tentamensperioden. Om man inte blir godkänd får man redovisa uppgifter vid kursens omtentatillfälle och/eller lämna in uppgift 1. Tider att boka kommer att finnas på canvas någon vecka innan. Är man inte godkänd efter detta får man göra om momentet nästa kursomgång.

Tentamen ( TEN1 )

TEN1 examinerar främst mål 1 men även mål 2 med betyget A-F och kommer att ha två delar. På del 1 kan man få betyget C, D, E, Fx eller F. Del 2 bedöms endast om man visat att man når upp till betyget C på del 1 och bedöms då med betyget A, B eller C.

TEN1 är en salsskrivning på skolans datorer uppstartad i en tentamensmiljö där ni har tillgång till eclipse, netbeans, IntelliJ och  Java’s API men inte internet.  Ni loggar in med ett speciellt tentamenskonto. Ni får vid tentamen en JAVA snabbreferensguide digitalt. Inga andra hjälpmedel förutom penna och tomma papper är tillåtna. Tentamen kommer bestå av två teorifrågor följt av ett antal programmeringsuppgifter.

Krysstal

Inför varje föreläsning finns ett antal uppgifter som man kan lämna in lösningar till i canvas innan föreläsningen börjat. Om man deltar på föreläsningen (ställer fråga om lottad, deltar i diskussion, redovisar uppgift för mig om lottad) får man räkna de uppgifter som är korrekta. Rättning kommer att ske med stickprov i efterhand och med individuell redovisning för mig via lottning. Om någon uppgift då inte är ett seriöst försök eller är uppenbart plagierad får man inte vara med i bonussystemet. Är en uppgift felaktig får man inte räkna just denna uppgift. Om man vid kursens slut har löst minst 35 uppgifter (varav minst 10 uppgifter till tillfälle 8-15) så får man som bonus hoppa över första programmeringsuppgiften på ordinarie TEN1.  Observera att om man försökt att lösa en uppgift men endast lyckats delvis får man inte lämna in i uppgiften. Observera också att bonusen endast gäller första ordinarie tentamen.

Lärandemål 2 examineras med betygsskalan P,F. Lärande mål 1 examineras med betygsskalan A, B, C, D, E, FX, F:

E – Utifrån ett enklare eller allmänt känt algoritmiskt problem använda och anpassa algoritmtekniker och skapa och använda datastrukturer för att lösa problemet inom väl tilltagen tid och med en effektiv lösning med hänseende på tid och minnesåtgång och med endast mindre kvalitetsavvikelser.

C – Utifrån ett något svårare eller allmänt känt algoritmiskt problem använda och anpassa algoritmtekniker och skapa och använda datastrukturer för att lösa problemet inom något begränsad tid och med en effektiv lösning med hänseende på tid och minnesåtgång.

A – Utifrån ett komplext eller ett svårare allmänt känt algoritmiskt problem använda och anpassa algoritmtekniker och skapa och använda datastrukturer för att lösa problemet inom begränsad tid och med en effektiv lösning med hänseende på tid och minnesåtgång.

Betyget Fx ges om man är mycket nära att uppnå betyget E. Betyget D ges om man delvis uppnår kraven för betyget C. Betyget B ges om man delvis uppnår kraven för betyget A.

För plussning kontakta studentexpeditionen inom anmälningstiden. Förutsatt att det finns plats och vi inte har coronarestriktioner kommer man att kunna plussa.

• 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.

För kursinformation se kurswebben HI1029. Där hittar man också länk till senaste kursomgångens canvassida.