Detaljert pensumliste til med kommentarer
Kapittel 1 er pensum.
- ? forst? og kunne bruke O-notasjon (Big-Oh) er viktig gjennom hele IN2010.
- Big-Omega og Big-Theta (s. 14) er pensum ? kjenne til/forst?, men ikke kunne bruke selv.
- Little-Oh og Little-Omega (s. 16) er ikke pensum.
- Kapittel 1.2 gir matematisk bakgrunn for resten av boken. Ikke direkte pensum, men leses ved behov. Se eventuelt ogs? Appendiks A (generelt lite brukt i IN2010).
- Amortisert kj?retid (kapittel 1.4) er pensum ? kjenne til/forst?, men ikke kunne gj?re selv. Kapittel 1.4.1-1.4.2 er ikke pensum.
Kapittel 2 er pensum.
- Lister, stakker og k?er (kapittel 2.1 og 2.2) forutsettes i hovedsak kjent fra IN1010 og leses p? egenh?nd.
- Tr?r (kapittel 2.3) er sentralt pensum.
Kapittel 3 er pensum.
- Bin?rs?k og bin?re s?ketr?r er sentralt pensum. Kjernestoffet er i kapittel 3.1, mens kapittel 3.2-3.3 viser flere varianter av s?king i bin?re s?ketr?r.
- Kapittel 3.4 er ikke pensum.
Kapittel 4 er delvis pensum.
- Rotasjoner (kapittel 4.1) er pensum.
- R?d-svarte tr?r (kapittel 4.3) er pensum. Rang-basert definisjon av r?d-svarte tr?r (fra nederst s. 127 til s. 129) er relevant, men ikke pensum i seg selv. Derimot er innsetting i r?d-svarte tr?r pensum selv om det ikke st?r direkte i l?reboken.
- AVL-tr?r (kapittel 4.2 og 4.4) og splay-tr?r (kapittel 4.5) er ikke pensum.
Kapittel 5 er pensum.
- Prioritetsk?er og heap (kapittel 5.1 og 5.3) er pensum. Utvidede prioritetsk?er (kapittel 5.5) er ogs? pensum, men litt mindre sentralt.
- Sorteringsalgoritmene i kapittel 5.2 og 5.4 er pensum.
Kapittel 6 er delvis pensum.
- Maps (kapittel 6.1) er pensum.
- For hashfunksjoner (kapittel 6.2) er det viktigste ? kjenne prinsippene. Kapittel 6.2.3 og 6.2.5 er ikke pensum.
- Kollisjonsh?ndtering (kapittel 6.3) er pensum, bortsett fra den detaljerte analysen p? side 202-203.
- Cuckoo hashing (kapittel 6.4) og universell hashing (kapittel 6.5) er ikke pensum.
Kapittel 7 er ikke pensum.
Kapittel 8 er pensum.
- For hele kapittelet gjelder at det er viktig ? kunne gjengi resultatene av kj?retidsanalysene og gi en intuitiv forklaring p? disse, men det forventes ikke at man kan reprodusere de matematiske utledningene.
Kapittel 9 er delvis pensum.
- Innledningen og kapittel 9.1 (bucket-sort og radix-sort) er pensum.
- Resten av kapittelet er ikke pensum.
Kapittel 10 er delvis pensum.
- Huffman (kapittel 10.3) er pensum.
- Resten av kapittelet er ikke pensum.
Kapittel 11-12 er ikke pensum.
Kapittel 13 er delvis pensum.
- 13.4.3 er ikke pensum.
- 13.4.2 er ikke pensum.
- 13.5 motivasjonen og den delen som handler om ? finne separation vertices eller sjekker at grafen er biconnected er pensum. Algoritmen st?r i foilene. Finne biconnected components er ikke pensum.
Kapittel 14 er delvis pensum.
- 14.5.2 er ikke pensum
Kapittel 15 er pensum.
Kapittel 16 er ikke pensum.
Kapittel 17 er delvis pensum.
- Kapittel 17.1 er pensum.
- NP-kompletthet er pensum, men mindre formelt enn kapittel 17.2. Interesserte anbefales ? lese hele kapittel 17.2, men selve pensum er bare innledningen og det som tas p? forelesninger og i ukeoppgaver.
- Fra resten av kapittelet er det forventet at man kan beskrive de NP-komplette problemene VERTEX-COVER, SUBSET-SUM, HAMILTONIAN-CYCLE og TSP.
Kapittel 18 er delvis pensum.
- Innledningen er pensum.
- Kapittel 18.4 er pensum, men ikke algoritmen for CNF-SAT p? s. 523. Se i stedet notatet om kombinatorisk s?king (revidert november 2018).
- Resten av kapittelet er ikke pensum.
Kapittel 19-22 er ikke pensum.
Kapittel 23 er delvis pensum.
- Kapittel 23.1 - 23.3 er pensum
Kapittel 24-26 er ikke pensum.
Alle algoritmer og datastrukturer i pensum skal kunne implementeres i Java.