TDDI16 Datastrukturer och algoritmer

Examination

• Givet en algoritm, analysera tidskomplexiten. Ge en exakt lösning. (Använd metoden/reglerna från den första och andra föreläsningen - exempel: fråga 1 på 09okt och 11aug-tentorna.)
• Använda och behärska definitionerna för asymptotisk tidskomplexitet. (Ordo, Omega och Theta.)
• Lös en rekursiv ekvation. (exempel: fråga 8 i 09okt och 11aug tentorna.)
• Definiera ADT X (modell + operationerna - förklara vad operationerna gör), där X är en ADT som vi tog upp i kursen. (exempel: fråga 2 i 09okt tentan.)
• Definiera ADT X, där X är en ADT som vi inte tog upp i kursen. (exempel: fråga 2 i 11aug tentan.)
• Ange/Beskriv en implementation av ADT X och ange tidskomplexitet för varje operation. (exempel: fråga 2 i 09okt och 11aug tentorna.)
• Traversering i träd. (exempel: fråga 3 i 09okt tentan.)
• Skriv en algoritm i pseudokod som löser ett givet problem. Använd ADT X. Välj sedan en implementation för ADT X och ange tidskomplexitet för din algoritm. (exempel: fråga 3 i 09okt och 11aug tentorna.)
• Skriv en algotim i pseudokod som löser ett givet problem. Se till att din algoritm har tidskomplexitet Y. (Kräver oftast användandet av någon känd datastruktur/algoritm eller att man modifierar en känd datastruktur/algoritm.)
• Givet en hashtabell. Lägg in och ta bort värden för hashtabellen. Antag öppen hashing / stängd hashning med given kollisionshanteringsstrategi. (exempel: fråga 4 i 09okt och 11aug tentorna.)
• Visa insättning och borttagning i binära sökträd / AVL-träd / 2-3-träd / prioritetskö.
• Visa sortering av en given lista mha olika sorteringsalgoritmer. (exempel: fråga 7 i 09okt och 11aug tentorna.)
• Ni ska kunna ange tidskomplexiteten för alla implementationer av operationer för alla ADT som vi tog upp i kurser, samt för alla sorteringsalgoritmer som vi tog upp i kursen.
• Förklara olika begrepp. (exempel: fråga 4b, 6 i 09okt tentan och 5 i 11aug tentan.)

Sidansvarig: Filip Strömbäck
Senast uppdaterad: 2020-08-11