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. I början av varje föreläsningstillfälle får du kryssa i vilka uppgifter du gjort. Därefter diskuterar vi dagens avsnitt och sedan lottar jag vilka som får redovisa sina lösningar för klassen.

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

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

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

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 samordnare för 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å i zoom 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 man får ihop 7-10 poäng får man en extra chans att redovisa i tentamensperioden. Om man inte blir godkänd får man redovisa alla uppgifter vid kursens omtentatillfälle. 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 där ni skriver på er dator uppstartad i en tentamensmiljö där ni har tillgång till eclipse, netbeans och  Java’s API men inte internet.  Ni loggar in med ett speciellt tentamenskonto. Ni får vid tentamen en JAVA snabbreferensguide. Inga andra hjälpmedel förutom penna och tomma papper är tillåtna. Tentan kommer bestå av två teorifrågor följt av ett antal programmeringsuppgifter.

Krysstal

I början av varje föreläsningstillfälle får man fylla i att man lyssnat igenom dagens föreläsning, formulerat en fråga på materialet och vilka uppgifter man löst. 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å TEN1. Observera att lösta uppgifter endast räknas om man också har lyssnat igenom föreläsningen och formulerat en fråga. Dessutom måste man kunna redovisa sin lösning om man blir lottad. Kan man inte redovisa på ett bra sätt så får man inte räkna några uppgifter den gången. Har man inte gjort uppgift man kryssat i så måste man göra första uppgiften på tentamen. Observera att om man försökt att lösa en uppgift men endast lyckats delvis eller inte alls så får man inte kryssa 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.

Normalt finns möjlighet att plussa. Tag kontakt med examinator och studentexpeditionen i god tid före tentamen.

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