Detaljert pensumliste til med kommentarer
Under er det listet opp hva som er pensum.
Stoff som er gjennomg?tt p? forelesningene er pensum.
Tekstalgoritmer (kap. 23) tas ut av pensum i forhold til pensum i 2018.
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).
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 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.
Kapittel 13 er delvis pensum.
- 13.5 motivasjonen og algoritmen fra forelesningen som finner separasjonsnoder og sjekker om en graf er 2-sammenhengende er pensum. Algoritmen st?r i foilene. Finne biconnected components er ikke pensum.
- I tillegg er algoritmen for ? finne sterkt sammenhengende komponenter pensum.
- 13.4.2 og 13.4.3 er ikke pensum.
Kapittel 14 er delvis pensum.
- 14.5 er ikke pensum
Kapittel 15 er 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 SUBSET-SUM, HAMILTONIAN-CYCLE og TSP.
- I tillegg skal men kjenne til og kunne beskrive problemene fra forelesningen og ukesoppgavene om kompleksitet og beregnbarhet, herunder PARTITON, (SUB)GRAPH-ISOMORPHISM, SAT.
- Man skal kjenne til hvorfor stoppeproblemet (HALT) er uavgj?rbart, uten at det forventes at man skal kunne f?re beviet selv.