Pensum/læringskrav

Lærebok: Algorithm Design and Applications av Michael T. Goodrich og Roberto Tamassia (ISBN 978-1-118-33591-8, 2014).

Alle algoritmer og datastrukturer i pensum skal kunne implementeres i Java.

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.

 

 

 

 

Publisert 30. aug. 2019 11:08 - Sist endret 31. okt. 2019 13:48