Læringsmål

Oversikt over læringsmål dekket i IN2010 Algoritmer og datastrukturer

Kilde: Læringsmålene er utformet av Skolesaga på grunnlag av emnets eksamensoppgaver, sensorveiledninger og emnebeskrivelse. De er ikke institusjonens offisielle læringsutbyttebeskrivelser.

168 kompetansemål42 av 42 kapitler har kompetansemål

Alle kompetansemål

•kunne gjøre rede for hvordan IN2010-eksamen er bygd opp, og hva hver av de tre delene krever av deg
0.1Eksamenskartet — slik testes IN2010
•kunne regne ut hva en antigjettings-skalering på en sant/usant-blokk betyr for din egen poengsum
0.1Eksamenskartet — slik testes IN2010
•kunne forklare hvorfor et algoritmevalg med lavere kjøretid gir flere poeng enn et tregere valg på samme oppgave
0.1Eksamenskartet — slik testes IN2010
•kunne legge en leseplan for boka ut fra hvor ofte hvert tema faktisk har kommet på eksamen
0.1Eksamenskartet — slik testes IN2010
•kunne forklare hva $O(g(n))$ betyr ved hjelp av konstanten $c$ og terskelen $n_0$
1.1Asymptotisk notasjon — O (og kort Ω, Θ)
•kunne forenkle et kjøretidsuttrykk til det strammeste $O$-uttrykket ved å finne det dominerende leddet
1.1Asymptotisk notasjon — O (og kort Ω, Θ)
•kunne plassere de vanlige kjøretidsklassene i riktig vekstrekkefølge uten oppslag
1.1Asymptotisk notasjon — O (og kort Ω, Θ)
•kunne avgjøre sant/usant-påstander om asymptotisk sammenligning, og begrunne dem med én setning
1.1Asymptotisk notasjon — O (og kort Ω, Θ)
•kunne telle løkker i en pseudokodesnutt og gange for nøsting, legge sammen for sekvens
1.2Kjøretidsanalyse fra kode — løkketelling
•kunne kjenne igjen at en løkke som dobler eller halverer tellevariabelen bidrar med en logaritmisk faktor
1.2Kjøretidsanalyse fra kode — løkketelling
•kunne skille en konstant indre løkke fra en løkke som vokser med problemstørrelsen
1.2Kjøretidsanalyse fra kode — løkketelling
•kunne levere svaret som ett strammest mulig O-uttrykk, med en setning om hva $n$ teller
1.2Kjøretidsanalyse fra kode — løkketelling
•kunne bestemme rekkevidden til hver løkke i en pseudokodesnutt og skille konstante grenser fra grenser som vokser med $n$
1.3DRILL — Kode → O-notasjon
•kunne gange for nøsting og legge sammen for sekvens, og lande på ett strammest mulig O-uttrykk
1.3DRILL — Kode → O-notasjon
•kunne kontrollere svaret med spørsmålet «hva skjer når $n$ dobles?»
1.3DRILL — Kode → O-notasjon
•kunne analysere en enkel rekursiv prosedyre ved å telle kall og nivåer, uten rekurrensligninger
1.3DRILL — Kode → O-notasjon
•kunne avgjøre de faste sant/usant-påstandene om kjøretid, heap og kompleksitetsteori, og begrunne hver med én setning
1.4Kjøretids- og teori-fakta — sant/usant og antigjettings-strategi
•kunne regne ut hva en gitt antigjettings-skalering gir i poeng for et bestemt antall sikre svar
1.4Kjøretids- og teori-fakta — sant/usant og antigjettings-strategi
•kunne forklare hvorfor det å bygge en heap er lineært, mens innsetting og uthenting er logaritmiske
1.4Kjøretids- og teori-fakta — sant/usant og antigjettings-strategi
•kunne skille reduksjonsretningen i $A \leq_p B$ og si hvilket problem som er vanskeligst
1.4Kjøretids- og teori-fakta — sant/usant og antigjettings-strategi
•kunne lese O-kjøretiden ut av en pseudokodesnutt under tidspress, og levere ett strammest mulig uttrykk
1.PPrøver til del 1: Asymptotisk analyse og kjøretidsfakta
•kunne rangere vanlige kjøretidsuttrykk etter vekst uten oppslag
1.PPrøver til del 1: Asymptotisk analyse og kjøretidsfakta
•kunne avgjøre de faste sant/usant-påstandene om kjøretid, heap og kompleksitetsteori og begrunne hver med én setning
1.PPrøver til del 1: Asymptotisk analyse og kjøretidsfakta
•kunne regne ut hva en antigjettings-skalering gir i poeng, og bruke det til å planlegge lesingen
1.PPrøver til del 1: Asymptotisk analyse og kjøretidsfakta
•kunne oppgi hvilke elementer som står garantert på endelig plass etter et gitt antall iterasjoner av boblesortering, utvalgssortering og innsettingssortering
2.1Sammenligningsbaserte sorteringer og invarianter
•kunne avgjøre om en sortering er stabil og om den arbeider på stedet, og begrunne svaret i én setning
2.1Sammenligningsbaserte sorteringer og invarianter
•kunne gjengi beste og verste kjøretid for de tre kvadratiske sorteringene hjelpemiddelfritt
2.1Sammenligningsbaserte sorteringer og invarianter
•kunne velge sorteringsalgoritme ut fra en oppgitt begrensning og oppgi kjøretiden som følger av valget
2.1Sammenligningsbaserte sorteringer og invarianter
•kunne gjengi beste, verste og forventet kjøretid for flettesortering, heapsort og kvikksortering, og si hvilke av dem som er stabile og hvilke som arbeider på stedet
2.2Effektive sorteringer og nedre grense
•kunne begrunne kjøretiden til flettesortering og kvikksortering ved å telle nivåer og arbeid per nivå
2.2Effektive sorteringer og nedre grense
•kunne skissere hvorfor ingen sammenligningsbasert sortering kommer under en nedre grense på n log n, med beslutningstreet som argument
2.2Effektive sorteringer og nedre grense
•kunne velge effektiv sortering ut fra et oppgitt krav om stabilitet, minnebruk eller garantert kjøretid, og oppgi kjøretiden som følger
2.2Effektive sorteringer og nedre grense
•kunne kjøre counting sort på et lite array og forklare hvorfor utplasseringen går bakfra
2.3Lineær sortering — bucket, counting og radix
•kunne forklare hvorfor radix sort sorterer på minst signifikante siffer først, og hvorfor hvert pass må være stabilt
2.3Lineær sortering — bucket, counting og radix
•kunne avgjøre om en oppgitt situasjon tillater lineær sortering, og oppgi forutsetningen som gjør valget lovlig
2.3Lineær sortering — bucket, counting og radix
•kunne lese egenskapene stabil, på stedet og kjøretid ut av pseudokoden til en sorteringsalgoritme du ikke har sett før
2.3Lineær sortering — bucket, counting og radix
•kunne oppgi tilstanden og de garanterte plasseringene etter et gitt antall iterasjoner for de tre kvadratiske sorteringene, uten å måtte utlede invarianten på nytt
2.4DRILL — Sorteringsegenskaper, invarianter og valg
•kunne gjengi kjøretids- og egenskapstabellen for alle sju sorteringene hjelpemiddelfritt og uten opphold
2.4DRILL — Sorteringsegenskaper, invarianter og valg
•kunne velge sortering ut fra en oppgitt begrensning og skrive ut forutsetningen som gjør valget lovlig
2.4DRILL — Sorteringsegenskaper, invarianter og valg
•kunne lese stabilitet, minnebruk og kjøretid ut av pseudokoden til en sorteringsalgoritme du ikke har sett før
2.4DRILL — Sorteringsegenskaper, invarianter og valg
•kunne håndkjøre boblesortering, utvalgssortering og innsettingssortering og oppgi hva som er garantert på plass etter hver iterasjon
2.PPrøver til del 2: Sortering og stabilitet
•kunne svare sikkert på sant/usant om kjøretid, stabilitet og minnebruk under antigjettings-skalering, og regne ut terskelen for netto poeng
2.PPrøver til del 2: Sortering og stabilitet
•kunne kjøre counting sort og radix sort på et lite array og forklare hvorfor stabiliteten er nødvendig
2.PPrøver til del 2: Sortering og stabilitet
•kunne velge sorteringsalgoritme ut fra en oppgitt begrensning, oppgi kjøretiden og skrive ut forutsetningen som gjør valget lovlig
2.PPrøver til del 2: Sortering og stabilitet
•kunne håndkjøre innsetting i en hashtabell med lineær probing og oppgi hele tabellen som sluttilstand, med markering av tomme plasser
3.1Hashtabeller og lukket hashing (linear probing)
•kunne skrive innsettingsprosedyren i pseudokode med korrekt wraparound og korrekt håndtering av en nøkkel som allerede finnes
3.1Hashtabeller og lukket hashing (linear probing)
•kunne forklare hvorfor et søk kan avsluttes på en tom plass, og hva den forklaringen forutsetter
3.1Hashtabeller og lukket hashing (linear probing)
•kunne oppgi forventet og verste kjøretid for oppslag i en hashtabell, og si hva som skiller de to tilfellene
3.1Hashtabeller og lukket hashing (linear probing)
•kunne regne ut load-faktoren og forklare hva den sier om forventet kjøretid
3.2Load-faktor, rehashing og hashmap/-set som verktøy
•kunne håndkjøre en rehashing til dobbel tabellstørrelse og forklare hvorfor de gamle indeksene ikke kan gjenbrukes
3.2Load-faktor, rehashing og hashmap/-set som verktøy
•kunne velge hashmap eller hash-set som verktøy i en pseudokodebesvarelse og oppgi forventet og verste kjøretid
3.2Load-faktor, rehashing og hashmap/-set som verktøy
•kunne sette opp poengtrappen for et søkeproblem og begrunne hvorfor den lineære løsningen står øverst
3.2Load-faktor, rehashing og hashmap/-set som verktøy
•kunne håndkjøre en innsettingsrekke i en hashtabell med lineær probing feilfritt, inkludert wraparound og gjentatt nøkkel
3.3DRILL — Linear-probing håndkjøring og insert-pseudokode
•kunne levere sluttilstanden i eksamensformatet: hele tabellen, kommaseparert, med tomme plasser markert
3.3DRILL — Linear-probing håndkjøring og insert-pseudokode
•kunne skrive innsettings- og søkeprosedyren i pseudokode med korrekt kjøretid for både forventet og verste tilfelle
3.3DRILL — Linear-probing håndkjøring og insert-pseudokode
•kunne kjenne igjen og rette de to detaljene i probing-løkka som sensor trekker for
3.3DRILL — Linear-probing håndkjøring og insert-pseudokode
•kunne skrive binærsøk i pseudokode og si eksplisitt hva som må endres for at det skal returnere en indeks
3.4Søk i pseudokode — binærsøk, finn duplikat og finn par
•kunne løse duplikat- og parsøk med hash-set og oppgi kjøretiden med det nødvendige forbeholdet om forventet tilfelle
3.4Søk i pseudokode — binærsøk, finn duplikat og finn par
•kunne bruke to-peker-teknikken på et sortert array og begrunne hvorfor hver flytting utelukker en hel rad av mulige par
3.4Søk i pseudokode — binærsøk, finn duplikat og finn par
•kunne sette opp poengtrappen for en søkeoppgave og begrunne hvorfor den valgte løsningen er lavest mulig
3.4Søk i pseudokode — binærsøk, finn duplikat og finn par
•kunne håndkjøre en innsettingsrekke med lineær probing og levere hele tabellen i eksamensformatet
3.PPrøver til del 3: Hashing og søk
•kunne svare sikkert på sant/usant om load-faktor, rehashing og hashkjøretider under antigjettings-skalering
3.PPrøver til del 3: Hashing og søk
•kunne skrive innsettings- og søkeprosedyren i pseudokode fra hukommelsen, med begge kjøretidstilfellene oppgitt
3.PPrøver til del 3: Hashing og søk
•kunne velge mellom hash-set, to pekere og sortering i en søkeoppgave, og begrunne valget med poengtrappen
3.PPrøver til del 3: Hashing og søk
•kunne håndkjøre innsetting i et binært søketre og oppgi in-order-utskriften og rotverdien som sluttilstand
4.1Binære søketrær (BST)
•kunne forklare hvorfor in-order-traversering av et søketre gir verdiene i stigende rekkefølge
4.1Binære søketrær (BST)
•kunne skrive innsetting, søk, minste og største verdi i pseudokode og oppgi kjøretiden som høyden på treet
4.1Binære søketrær (BST)
•kunne slette en verdi i alle tre tilfellene, inkludert å finne in-order-etterfølgeren når noden har to barn
4.1Binære søketrær (BST)
•kunne skrive et beskåret intervallsøk i et binært søketre og begrunne hvorfor det er raskere enn en full traversering
4.2Tre-algoritmer i pseudokode — beskjæring og lineær rekursjon
•kunne regne ut den lengste stien i et tre med én gjennomgang, og forklare hvorfor varianten med en høydeberegning per node blir kvadratisk
4.2Tre-algoritmer i pseudokode — beskjæring og lineær rekursjon
•kunne finne nærmeste felles forfar til to verdier i et søketre og oppgi kjøretiden som høyden på treet
4.2Tre-algoritmer i pseudokode — beskjæring og lineær rekursjon
•kunne avgjøre om et tre er et gyldig søketre ved å sende et intervall nedover, og oppgi antagelser og kjøretid slik en Del 2-besvarelse krever
4.2Tre-algoritmer i pseudokode — beskjæring og lineær rekursjon
•kunne regne ut balansefaktoren til hver node i et binært søketre og avgjøre om treet er et gyldig AVL-tre
4.3Balanserte trær — AVL og rød-svart
•kunne håndkjøre en innsettingsrekke i et AVL-tre og oppgi antall enkle rotasjoner, rotverdien til slutt og om resultatet er gyldig
4.3Balanserte trær — AVL og rød-svart
•kunne kjenne igjen hvilket av de fire ubalansetilfellene som foreligger, og vite at en dobbelrotasjon består av to enkle rotasjoner
4.3Balanserte trær — AVL og rød-svart
•kunne begrunne hvorfor et høydebalansert søketre har logaritmisk høyde, og gjengi fargeinvariantene i et rød-svart-tre
4.3Balanserte trær — AVL og rød-svart
•kunne regne ut forelder- og barneindeksene i en heap som ligger som array med indeks fra 0, og avgjøre når et barn ikke finnes
4.4Heap og prioritetskø
•kunne håndkjøre innsetting og uthenting av minste element i en min-heap og oppgi hele arrayet som sluttilstand
4.4Heap og prioritetskø
•kunne skrive innsettings- og nedsynkingsprosedyrene i pseudokode, med sjekk på at barnet finnes og med riktig kjøretid
4.4Heap og prioritetskø
•kunne begrunne hvorfor det å bygge en heap fra et vilkårlig array er lineært, og gjengi de faste heap-faktaene med begrunnelse
4.4Heap og prioritetskø
•kunne håndkjøre innsetting og fjerning av minsteelementet i en min-heap lagret som array med indeks fra 0, og oppgi arrayet som sluttsvar
4.5DRILL — Håndkjøring av heap og AVL
•kunne utføre down-heap korrekt: alltid mot det minste barnet, og alltid med en sjekk av at barnet finnes
4.5DRILL — Håndkjøring av heap og AVL
•kunne telle enkle rotasjoner i et AVL-tre, der en dobbelrotasjon teller som to, og oppgi rotverdien og gyldigheten til slutt
4.5DRILL — Håndkjøring av heap og AVL
•kunne avgjøre om en gitt struktur er en gyldig min-heap eller et gyldig AVL-tre, og peke ut det konkrete bruddet når den ikke er det
4.5DRILL — Håndkjøring av heap og AVL
•kunne håndkjøre innsetting, søk og sletting i et binært søketre og levere in-order-utskriften og rotverdien som sluttsvar
4.PPrøver til del 4: Trær: søketrær, balanserte trær og heap
•kunne håndkjøre innsetting og fjerning av minsteelementet i en min-heap lagret som array med indeks fra 0
4.PPrøver til del 4: Trær: søketrær, balanserte trær og heap
•kunne skrive de faste tre-algoritmene i pseudokode med antagelser og kjøretid, og velge den løsningen som gir lavest kjøretid
4.PPrøver til del 4: Trær: søketrær, balanserte trær og heap
•kunne telle enkle rotasjoner i et AVL-tre og svare sikkert på fakta om balanserte trær og heap under antigjettings-skalering
4.PPrøver til del 4: Trær: søketrær, balanserte trær og heap
•kunne lese og skrive den samme grafen både som naboliste og som nabomatrise, og oppgi plassforbruket for begge
5.1Grafrepresentasjon og grunnbegreper
•kunne avgjøre om en graf er enkel, om den er sammenhengende, om den inneholder en sykel og om den er et tre
5.1Grafrepresentasjon og grunnbegreper
•kunne regne med grad, inngrad og utgrad, og bruke at gradsummen i en urettet graf er dobbelt så stor som antall kanter
5.1Grafrepresentasjon og grunnbegreper
•kunne velge representasjon ut fra hvilke operasjoner algoritmen bruker mest, og alltid oppgi valget i en besvarelse
5.1Grafrepresentasjon og grunnbegreper
•kunne håndkjøre bredde-først med kø og dybde-først med kallstakk, og oppgi besøksrekkefølge, lag og ferdigrekkefølge
5.2BFS og DFS — traversering
•kunne skrive bredde-først, rekursivt dybde-først og dybde-først over hele grafen i pseudokode, med antagelser og kjøretid
5.2BFS og DFS — traversering
•kunne begrunne hvorfor dybde-først fra én node og dybde-først over hele grafen har forskjellig kjøretid, og oppgi riktig uttrykk for hver
5.2BFS og DFS — traversering
•kunne velge riktig traversering når en oppgave ber om korteste vei målt i antall kanter, og si hvorfor den andre ikke duger
5.2BFS og DFS — traversering
•kunne telle sammenhengende komponenter i en urettet graf med en dybde-først-traversering og begrunne kjøretiden ved løkketelling
5.3Komponenter, 2-fargelegging og sykeldeteksjon
•kunne skrive 2-fargeleggingen i pseudokode og forklare hvorfor en konflikt beviser at grafen ikke er bipartitt
5.3Komponenter, 2-fargelegging og sykeldeteksjon
•kunne oppdage en sykel i en urettet graf med en dybde-først-traversering, og håndtere kanten tilbake til forelderen riktig
5.3Komponenter, 2-fargelegging og sykeldeteksjon
•kunne gjenkjenne komponentvis behandling fra en rot-mengde i en innpakket oppgavetekst og oppgi lavest mulig kjøretid
5.3Komponenter, 2-fargelegging og sykeldeteksjon
•kunne forklare hva en sterkt sammenhengende komponent er, og hvordan komponentgrafen bygges ved å krympe hver komponent til én node
5.4SCC og komponentgraf (kondensasjon) — UiO-signatur
•kunne beskrive de to dybde-først-gjennomløpene som finner komponentene, og begrunne kjøretiden ved løkketelling
5.4SCC og komponentgraf (kondensasjon) — UiO-signatur
•kunne oversette et spørsmål om hvem som kan nås fra hvem til inngrad eller utgrad i komponentgrafen, og oppgi det minste antallet startnoder
5.4SCC og komponentgraf (kondensasjon) — UiO-signatur
•kunne begrunne hvorfor den lineære løsningen slår den som traverserer fra hver enkelt node, og hva den forskjellen betyr for uttellingen
5.4SCC og komponentgraf (kondensasjon) — UiO-signatur
•kunne gjenkjenne hvilket klassisk grafproblem en innpakket oppgave egentlig er, og navngi det eksplisitt i besvarelsen
5.5DRILL — Grafalgoritmer i pseudokode: mønstergjenkjenning
•kunne skrive presis pseudokode for bredde-først-søk, avgrenset bredde-først-søk, dybde-først-søk over alle komponenter, tofarging og sterkt sammenhengende komponenter
5.5DRILL — Grafalgoritmer i pseudokode: mønstergjenkjenning
•kunne oppgi antagelser om representasjon og en kjøretid som matcher algoritmen du faktisk skrev, med antall noder og antall kanter definert
5.5DRILL — Grafalgoritmer i pseudokode: mønstergjenkjenning
•kunne velge løsningen med lavest kjøretid og begrunne i én setning hvorfor lavere ikke er mulig
5.5DRILL — Grafalgoritmer i pseudokode: mønstergjenkjenning
•kunne krysse av for grafegenskaper og for kjøretidene til naboliste og nabomatrise uten oppslag
5.PPrøver til del 5: Grafer: representasjon, traversering og komponenter
•kunne skrive bredde-først- og dybde-først-traversering i pseudokode fra hukommelsen, med riktig kjøretid for hver variant
5.PPrøver til del 5: Grafer: representasjon, traversering og komponenter
•kunne skrive tofarging og komponenttelling i pseudokode og kjøre dem for hånd på en oppgitt graf
5.PPrøver til del 5: Grafer: representasjon, traversering og komponenter
•kunne løse en «hvem når hvem»-oppgave med én kjøring av komponentalgoritmen og begrunne at kjøretiden er lavest mulig
5.PPrøver til del 5: Grafer: representasjon, traversering og komponenter
•kunne håndkjøre Kahns algoritme på en rettet graf og oppgi rekkefølgen, eller melde at grafen er syklisk
6.1Topologisk sortering og DAG-egenskaper
•kunne skrive topologisk sortering i pseudokode med inngradstabell, kø og sykelsjekk
6.1Topologisk sortering og DAG-egenskaper
•kunne begrunne kjøretiden ved løkketelling, og forklare hvorfor den er en sum og ikke et produkt
6.1Topologisk sortering og DAG-egenskaper
•kunne gjenkjenne at et avhengighetsproblem skal løses med topologisk sortering, og oppgi lavest mulig kjøretid
6.1Topologisk sortering og DAG-egenskaper
•kunne velge riktig korteste-vei-algoritme ut fra graftypen, og oppgi kjøretiden for hver av de fire tilfellene
6.2Korteste vei — BFS, Dijkstra, DAG og reversert graf
•kunne håndkjøre Dijkstras algoritme og oppgi avstandstabellen ved terminering
6.2Korteste vei — BFS, Dijkstra, DAG og reversert graf
•kunne skrive Dijkstra og DAG-metoden i pseudokode med antagelser, invariant og kjøretid
6.2Korteste vei — BFS, Dijkstra, DAG og reversert graf
•kunne forklare hvorfor én negativ kant er nok til å ødelegge Dijkstra, selv i en graf uten sykler
6.2Korteste vei — BFS, Dijkstra, DAG og reversert graf
•kunne håndkjøre Prim og Kruskal på en urettet vektet graf og oppgi kantene og totalvekten
6.3Minimale spenntrær — Prim, Kruskal, Borůvka
•kunne skrive Prim i pseudokode med antagelser, grunnidé og kjøretid, også for en komplett graf
6.3Minimale spenntrær — Prim, Kruskal, Borůvka
•kunne begrunne hvorfor bredde- og dybde-først-søk ikke finner minimale spenntrær
6.3Minimale spenntrær — Prim, Kruskal, Borůvka
•kunne gjenkjenne at «koble alt sammen billigst» er et spenntreproblem, og at korteste vei i det ferdige treet er en traversering
6.3Minimale spenntrær — Prim, Kruskal, Borůvka
•kunne bygge et Huffman-tre fra en frekvenstabell for hånd og oppgi kodelengden per symbol
6.4Huffman-koding
•kunne regne ut totalt antall bits og sammenligne med en fast koding
6.4Huffman-koding
•kunne forklare hvorfor kodene danner en prefikskode, og hva det betyr for dekoding
6.4Huffman-koding
•kunne oppgi kjøretiden og si hva størrelsen i den står for
6.4Huffman-koding
•kunne fylle inn korteste-avstander-matrisen og kjøretidstabellen for grafalgoritmene uten oppslag
6.5DRILL — Korteste-vei-matrisen og MST-modellering
•kunne gjenkjenne hvilket av Del 6-problemene en oppgavetekst beskriver, ut fra signalordene
6.5DRILL — Korteste-vei-matrisen og MST-modellering
•kunne skrive svaret i de fire leddene sensor krever, med kjøretid som matcher algoritmen
6.5DRILL — Korteste-vei-matrisen og MST-modellering
•kunne velge den raskeste korrekte algoritmen og begrunne hvorfor en tregere løsning gir færre poeng
6.5DRILL — Korteste-vei-matrisen og MST-modellering
•kunne velge riktig grafalgoritme ut fra oppgavetekstens signalord og oppgi kjøretiden
6.PPrøver til del 6: Korteste vei, spenntrær og grådighet
•kunne håndkjøre Dijkstra, Prim, Kruskal, Kahn og Huffman feilfritt og oppgi sluttilstanden
6.PPrøver til del 6: Korteste vei, spenntrær og grådighet
•kunne skrive en Del 2-besvarelse i de fire leddene sensor krever
6.PPrøver til del 6: Korteste vei, spenntrær og grådighet
•kunne regne ut hva en antigjettings-skalering krever av sikre svar
6.PPrøver til del 6: Korteste vei, spenntrær og grådighet
•kunne designe en mediankø med to heaps, formulere invarianten og oppgi kjøretid per operasjon
7.1ADT-design — mediankø, bøttekø og trie
•kunne velge bøttekø framfor heap når antall prioritetsnivåer er fast og lite, og begrunne valget
7.1ADT-design — mediankø, bøttekø og trie
•kunne forklare hvorfor et trie gir prefikssøk som et hashmap ikke gir, og hva det koster i minne
7.1ADT-design — mediankø, bøttekø og trie
•kunne kombinere to strukturer når ingen enkeltstruktur gir alle operasjonene billig
7.1ADT-design — mediankø, bøttekø og trie
•kunne definere hva $n$ står for i en drøftingsoppgave, og navngi de andre størrelsene som kjøretiden avhenger av
7.2Drøft to strategier
•kunne oppgi både verste og forventet kjøretid for to strategier, og sammenligne minnebruken deres
7.2Drøft to strategier
•kunne kjenne igjen kanttilfellene som avgjør sammenligningen — stort verdiområde, kollisjoner og ferdig ordnet inndata
7.2Drøft to strategier
•kunne konkludere med en betingelse i stedet for å stanse ved «det kommer an på»
7.2Drøft to strategier
•kunne skille mellom å løse et problem og å kontrollere et foreslått svar, og bruke skillet til å plassere et problem i $P$ eller $NP$
7.3NP-kompletthet — og hva som IKKE er IN2010-pensum
•kunne skrive en verifikator i pseudokode som kontrollerer et sertifikat i polynomisk tid, inkludert den siste kanten i en rundtur
7.3NP-kompletthet — og hva som IKKE er IN2010-pensum
•kunne begrunne hvilken vei en polynomisk reduksjon må gå for å vise at et problem er vanskelig
7.3NP-kompletthet — og hva som IKKE er IN2010-pensum
•kunne avgrense pensum og navngi de tunge algoritmetemaene som ikke testes i dette emnet
7.3NP-kompletthet — og hva som IKKE er IN2010-pensum
•kunne håndkjøre en mediankø og en bøttekø og oppgi sluttilstanden i det formatet eksamen krever
7.PPrøver til del 7: Datastruktur-design, drøfting og NP-teori
•kunne skrive en drøfting som treffer alle fire leddene sensor krever, og som ender i en betingelse
7.PPrøver til del 7: Datastruktur-design, drøfting og NP-teori
•kunne skrive en verifikator med korrekt behandling av den siste kanten i en rundtur
7.PPrøver til del 7: Datastruktur-design, drøfting og NP-teori
•kunne avgjøre hvilken vei en reduksjon må gå, og hvilke temaer som ikke er pensum i emnet
7.PPrøver til del 7: Datastruktur-design, drøfting og NP-teori
•kunne finne den raskeste korrekte løsningen på en Del 2-oppgave ved å gå gjennom de fem faste grepene
8.1DRILL — Del 2-strategi: velg lavest kjøretid (poengtrappen) og skriv presis pseudokode
•kunne skrive svaret i de fire leddene sensor krever, med kjøretid som matcher algoritmen og med n definert
8.1DRILL — Del 2-strategi: velg lavest kjøretid (poengtrappen) og skriv presis pseudokode
•kunne begrunne hvorfor en tregere korrekt løsning gir færre poeng, og hvor mye
8.1DRILL — Del 2-strategi: velg lavest kjøretid (poengtrappen) og skriv presis pseudokode
•kunne levere en besvarelse i klart naturlig språk som gir like mye uttelling som pseudokode
8.1DRILL — Del 2-strategi: velg lavest kjøretid (poengtrappen) og skriv presis pseudokode
•kunne gjennomføre et komplett firetimers sett uten hjelpemidler og fordele tiden mellom de tre delene
8.2Øvingseksamen 1 — bredt ordinært sett (epoke 3)
•kunne svare sikkert på auto-rettede kjøretids-, sorterings-, heap- og graf-fakta under antigjettings-skalering
8.2Øvingseksamen 1 — bredt ordinært sett (epoke 3)
•kunne håndkjøre min-heap og lineær probing og oppgi sluttilstanden i eksamensformatet
8.2Øvingseksamen 1 — bredt ordinært sett (epoke 3)
•kunne skrive presise pseudokodesvar for tre-, hashing- og grafoppgaver med kjøretid som matcher algoritmen
8.2Øvingseksamen 1 — bredt ordinært sett (epoke 3)
•kunne håndkjøre min-heap, lineær probing, AVL-rotasjoner og Huffman-koding feilfritt og levere sluttilstanden i riktig format
8.3Øvingseksamen 2 — håndkjørings- og hashing-tungt sett
•kunne skrive hashing- og søkealgoritmer i pseudokode med korrekt forbehold om forventet og verste kjøretid
8.3Øvingseksamen 2 — håndkjørings- og hashing-tungt sett
•kunne bruke søketre-egenskapen til å beskjære et søk i stedet for å traversere hele treet
8.3Øvingseksamen 2 — håndkjørings- og hashing-tungt sett
•kunne drøfte to strategier med definerte størrelser, verste og forventet kjøretid, minne og en betinget konklusjon
8.3Øvingseksamen 2 — håndkjørings- og hashing-tungt sett
•kunne gjenkjenne hvilken pensumalgoritme en åpen modelleringsoppgave beskriver, ut fra signalordene i teksten
8.4Øvingseksamen 3 — grafmodellerings-tungt topp-sett
•kunne velge den raskeste korrekte grafalgoritmen og begrunne hvorfor en tregere løsning gir færre poeng
8.4Øvingseksamen 3 — grafmodellerings-tungt topp-sett
•kunne kombinere topologisk sortering og sterkt sammenhengende komponenter i samme oppgave
8.4Øvingseksamen 3 — grafmodellerings-tungt topp-sett
•kunne designe en datastruktur av kjente byggeklosser og oppgi kjøretid per operasjon
8.4Øvingseksamen 3 — grafmodellerings-tungt topp-sett

Kapitler med kompetansemål

0Eksamenskart

0.1Eksamenskartet — slik testes IN2010
  • kunne gjøre rede for hvordan IN2010-eksamen er bygd opp, og hva hver av de tre delene krever av deg
  • kunne regne ut hva en antigjettings-skalering på en sant/usant-blokk betyr for din egen poengsum
  • kunne forklare hvorfor et algoritmevalg med lavere kjøretid gir flere poeng enn et tregere valg på samme oppgave
  • kunne legge en leseplan for boka ut fra hvor ofte hvert tema faktisk har kommet på eksamen

1Asymptotisk analyse og kjøretidsfakta

1.1Asymptotisk notasjon — O (og kort Ω, Θ)
  • kunne forklare hva $O(g(n))$ betyr ved hjelp av konstanten $c$ og terskelen $n_0$
  • kunne forenkle et kjøretidsuttrykk til det strammeste $O$-uttrykket ved å finne det dominerende leddet
  • kunne plassere de vanlige kjøretidsklassene i riktig vekstrekkefølge uten oppslag
  • kunne avgjøre sant/usant-påstander om asymptotisk sammenligning, og begrunne dem med én setning
1.2Kjøretidsanalyse fra kode — løkketelling
  • kunne telle løkker i en pseudokodesnutt og gange for nøsting, legge sammen for sekvens
  • kunne kjenne igjen at en løkke som dobler eller halverer tellevariabelen bidrar med en logaritmisk faktor
  • kunne skille en konstant indre løkke fra en løkke som vokser med problemstørrelsen
  • kunne levere svaret som ett strammest mulig O-uttrykk, med en setning om hva $n$ teller
1.3DRILL — Kode → O-notasjon
  • kunne bestemme rekkevidden til hver løkke i en pseudokodesnutt og skille konstante grenser fra grenser som vokser med $n$
  • kunne gange for nøsting og legge sammen for sekvens, og lande på ett strammest mulig O-uttrykk
  • kunne kontrollere svaret med spørsmålet «hva skjer når $n$ dobles?»
  • kunne analysere en enkel rekursiv prosedyre ved å telle kall og nivåer, uten rekurrensligninger
1.4Kjøretids- og teori-fakta — sant/usant og antigjettings-strategi
  • kunne avgjøre de faste sant/usant-påstandene om kjøretid, heap og kompleksitetsteori, og begrunne hver med én setning
  • kunne regne ut hva en gitt antigjettings-skalering gir i poeng for et bestemt antall sikre svar
  • kunne forklare hvorfor det å bygge en heap er lineært, mens innsetting og uthenting er logaritmiske
  • kunne skille reduksjonsretningen i $A \leq_p B$ og si hvilket problem som er vanskeligst
1.PPrøver til del 1: Asymptotisk analyse og kjøretidsfakta
  • kunne lese O-kjøretiden ut av en pseudokodesnutt under tidspress, og levere ett strammest mulig uttrykk
  • kunne rangere vanlige kjøretidsuttrykk etter vekst uten oppslag
  • kunne avgjøre de faste sant/usant-påstandene om kjøretid, heap og kompleksitetsteori og begrunne hver med én setning
  • kunne regne ut hva en antigjettings-skalering gir i poeng, og bruke det til å planlegge lesingen

2Sortering og stabilitet

2.1Sammenligningsbaserte sorteringer og invarianter
  • kunne oppgi hvilke elementer som står garantert på endelig plass etter et gitt antall iterasjoner av boblesortering, utvalgssortering og innsettingssortering
  • kunne avgjøre om en sortering er stabil og om den arbeider på stedet, og begrunne svaret i én setning
  • kunne gjengi beste og verste kjøretid for de tre kvadratiske sorteringene hjelpemiddelfritt
  • kunne velge sorteringsalgoritme ut fra en oppgitt begrensning og oppgi kjøretiden som følger av valget
2.2Effektive sorteringer og nedre grense
  • kunne gjengi beste, verste og forventet kjøretid for flettesortering, heapsort og kvikksortering, og si hvilke av dem som er stabile og hvilke som arbeider på stedet
  • kunne begrunne kjøretiden til flettesortering og kvikksortering ved å telle nivåer og arbeid per nivå
  • kunne skissere hvorfor ingen sammenligningsbasert sortering kommer under en nedre grense på n log n, med beslutningstreet som argument
  • kunne velge effektiv sortering ut fra et oppgitt krav om stabilitet, minnebruk eller garantert kjøretid, og oppgi kjøretiden som følger
2.3Lineær sortering — bucket, counting og radix
  • kunne kjøre counting sort på et lite array og forklare hvorfor utplasseringen går bakfra
  • kunne forklare hvorfor radix sort sorterer på minst signifikante siffer først, og hvorfor hvert pass må være stabilt
  • kunne avgjøre om en oppgitt situasjon tillater lineær sortering, og oppgi forutsetningen som gjør valget lovlig
  • kunne lese egenskapene stabil, på stedet og kjøretid ut av pseudokoden til en sorteringsalgoritme du ikke har sett før
2.4DRILL — Sorteringsegenskaper, invarianter og valg
  • kunne oppgi tilstanden og de garanterte plasseringene etter et gitt antall iterasjoner for de tre kvadratiske sorteringene, uten å måtte utlede invarianten på nytt
  • kunne gjengi kjøretids- og egenskapstabellen for alle sju sorteringene hjelpemiddelfritt og uten opphold
  • kunne velge sortering ut fra en oppgitt begrensning og skrive ut forutsetningen som gjør valget lovlig
  • kunne lese stabilitet, minnebruk og kjøretid ut av pseudokoden til en sorteringsalgoritme du ikke har sett før
2.PPrøver til del 2: Sortering og stabilitet
  • kunne håndkjøre boblesortering, utvalgssortering og innsettingssortering og oppgi hva som er garantert på plass etter hver iterasjon
  • kunne svare sikkert på sant/usant om kjøretid, stabilitet og minnebruk under antigjettings-skalering, og regne ut terskelen for netto poeng
  • kunne kjøre counting sort og radix sort på et lite array og forklare hvorfor stabiliteten er nødvendig
  • kunne velge sorteringsalgoritme ut fra en oppgitt begrensning, oppgi kjøretiden og skrive ut forutsetningen som gjør valget lovlig

3Hashing og søk

3.1Hashtabeller og lukket hashing (linear probing)
  • kunne håndkjøre innsetting i en hashtabell med lineær probing og oppgi hele tabellen som sluttilstand, med markering av tomme plasser
  • kunne skrive innsettingsprosedyren i pseudokode med korrekt wraparound og korrekt håndtering av en nøkkel som allerede finnes
  • kunne forklare hvorfor et søk kan avsluttes på en tom plass, og hva den forklaringen forutsetter
  • kunne oppgi forventet og verste kjøretid for oppslag i en hashtabell, og si hva som skiller de to tilfellene
3.2Load-faktor, rehashing og hashmap/-set som verktøy
  • kunne regne ut load-faktoren og forklare hva den sier om forventet kjøretid
  • kunne håndkjøre en rehashing til dobbel tabellstørrelse og forklare hvorfor de gamle indeksene ikke kan gjenbrukes
  • kunne velge hashmap eller hash-set som verktøy i en pseudokodebesvarelse og oppgi forventet og verste kjøretid
  • kunne sette opp poengtrappen for et søkeproblem og begrunne hvorfor den lineære løsningen står øverst
3.3DRILL — Linear-probing håndkjøring og insert-pseudokode
  • kunne håndkjøre en innsettingsrekke i en hashtabell med lineær probing feilfritt, inkludert wraparound og gjentatt nøkkel
  • kunne levere sluttilstanden i eksamensformatet: hele tabellen, kommaseparert, med tomme plasser markert
  • kunne skrive innsettings- og søkeprosedyren i pseudokode med korrekt kjøretid for både forventet og verste tilfelle
  • kunne kjenne igjen og rette de to detaljene i probing-løkka som sensor trekker for
3.4Søk i pseudokode — binærsøk, finn duplikat og finn par
  • kunne skrive binærsøk i pseudokode og si eksplisitt hva som må endres for at det skal returnere en indeks
  • kunne løse duplikat- og parsøk med hash-set og oppgi kjøretiden med det nødvendige forbeholdet om forventet tilfelle
  • kunne bruke to-peker-teknikken på et sortert array og begrunne hvorfor hver flytting utelukker en hel rad av mulige par
  • kunne sette opp poengtrappen for en søkeoppgave og begrunne hvorfor den valgte løsningen er lavest mulig
3.PPrøver til del 3: Hashing og søk
  • kunne håndkjøre en innsettingsrekke med lineær probing og levere hele tabellen i eksamensformatet
  • kunne svare sikkert på sant/usant om load-faktor, rehashing og hashkjøretider under antigjettings-skalering
  • kunne skrive innsettings- og søkeprosedyren i pseudokode fra hukommelsen, med begge kjøretidstilfellene oppgitt
  • kunne velge mellom hash-set, to pekere og sortering i en søkeoppgave, og begrunne valget med poengtrappen

4Trær: søketrær, balanserte trær og heap

4.1Binære søketrær (BST)
  • kunne håndkjøre innsetting i et binært søketre og oppgi in-order-utskriften og rotverdien som sluttilstand
  • kunne forklare hvorfor in-order-traversering av et søketre gir verdiene i stigende rekkefølge
  • kunne skrive innsetting, søk, minste og største verdi i pseudokode og oppgi kjøretiden som høyden på treet
  • kunne slette en verdi i alle tre tilfellene, inkludert å finne in-order-etterfølgeren når noden har to barn
4.2Tre-algoritmer i pseudokode — beskjæring og lineær rekursjon
  • kunne skrive et beskåret intervallsøk i et binært søketre og begrunne hvorfor det er raskere enn en full traversering
  • kunne regne ut den lengste stien i et tre med én gjennomgang, og forklare hvorfor varianten med en høydeberegning per node blir kvadratisk
  • kunne finne nærmeste felles forfar til to verdier i et søketre og oppgi kjøretiden som høyden på treet
  • kunne avgjøre om et tre er et gyldig søketre ved å sende et intervall nedover, og oppgi antagelser og kjøretid slik en Del 2-besvarelse krever
4.3Balanserte trær — AVL og rød-svart
  • kunne regne ut balansefaktoren til hver node i et binært søketre og avgjøre om treet er et gyldig AVL-tre
  • kunne håndkjøre en innsettingsrekke i et AVL-tre og oppgi antall enkle rotasjoner, rotverdien til slutt og om resultatet er gyldig
  • kunne kjenne igjen hvilket av de fire ubalansetilfellene som foreligger, og vite at en dobbelrotasjon består av to enkle rotasjoner
  • kunne begrunne hvorfor et høydebalansert søketre har logaritmisk høyde, og gjengi fargeinvariantene i et rød-svart-tre
4.4Heap og prioritetskø
  • kunne regne ut forelder- og barneindeksene i en heap som ligger som array med indeks fra 0, og avgjøre når et barn ikke finnes
  • kunne håndkjøre innsetting og uthenting av minste element i en min-heap og oppgi hele arrayet som sluttilstand
  • kunne skrive innsettings- og nedsynkingsprosedyrene i pseudokode, med sjekk på at barnet finnes og med riktig kjøretid
  • kunne begrunne hvorfor det å bygge en heap fra et vilkårlig array er lineært, og gjengi de faste heap-faktaene med begrunnelse
4.5DRILL — Håndkjøring av heap og AVL
  • kunne håndkjøre innsetting og fjerning av minsteelementet i en min-heap lagret som array med indeks fra 0, og oppgi arrayet som sluttsvar
  • kunne utføre down-heap korrekt: alltid mot det minste barnet, og alltid med en sjekk av at barnet finnes
  • kunne telle enkle rotasjoner i et AVL-tre, der en dobbelrotasjon teller som to, og oppgi rotverdien og gyldigheten til slutt
  • kunne avgjøre om en gitt struktur er en gyldig min-heap eller et gyldig AVL-tre, og peke ut det konkrete bruddet når den ikke er det
4.PPrøver til del 4: Trær: søketrær, balanserte trær og heap
  • kunne håndkjøre innsetting, søk og sletting i et binært søketre og levere in-order-utskriften og rotverdien som sluttsvar
  • kunne håndkjøre innsetting og fjerning av minsteelementet i en min-heap lagret som array med indeks fra 0
  • kunne skrive de faste tre-algoritmene i pseudokode med antagelser og kjøretid, og velge den løsningen som gir lavest kjøretid
  • kunne telle enkle rotasjoner i et AVL-tre og svare sikkert på fakta om balanserte trær og heap under antigjettings-skalering

5Grafer: representasjon, traversering og komponenter

5.1Grafrepresentasjon og grunnbegreper
  • kunne lese og skrive den samme grafen både som naboliste og som nabomatrise, og oppgi plassforbruket for begge
  • kunne avgjøre om en graf er enkel, om den er sammenhengende, om den inneholder en sykel og om den er et tre
  • kunne regne med grad, inngrad og utgrad, og bruke at gradsummen i en urettet graf er dobbelt så stor som antall kanter
  • kunne velge representasjon ut fra hvilke operasjoner algoritmen bruker mest, og alltid oppgi valget i en besvarelse
5.2BFS og DFS — traversering
  • kunne håndkjøre bredde-først med kø og dybde-først med kallstakk, og oppgi besøksrekkefølge, lag og ferdigrekkefølge
  • kunne skrive bredde-først, rekursivt dybde-først og dybde-først over hele grafen i pseudokode, med antagelser og kjøretid
  • kunne begrunne hvorfor dybde-først fra én node og dybde-først over hele grafen har forskjellig kjøretid, og oppgi riktig uttrykk for hver
  • kunne velge riktig traversering når en oppgave ber om korteste vei målt i antall kanter, og si hvorfor den andre ikke duger
5.3Komponenter, 2-fargelegging og sykeldeteksjon
  • kunne telle sammenhengende komponenter i en urettet graf med en dybde-først-traversering og begrunne kjøretiden ved løkketelling
  • kunne skrive 2-fargeleggingen i pseudokode og forklare hvorfor en konflikt beviser at grafen ikke er bipartitt
  • kunne oppdage en sykel i en urettet graf med en dybde-først-traversering, og håndtere kanten tilbake til forelderen riktig
  • kunne gjenkjenne komponentvis behandling fra en rot-mengde i en innpakket oppgavetekst og oppgi lavest mulig kjøretid
5.4SCC og komponentgraf (kondensasjon) — UiO-signatur
  • kunne forklare hva en sterkt sammenhengende komponent er, og hvordan komponentgrafen bygges ved å krympe hver komponent til én node
  • kunne beskrive de to dybde-først-gjennomløpene som finner komponentene, og begrunne kjøretiden ved løkketelling
  • kunne oversette et spørsmål om hvem som kan nås fra hvem til inngrad eller utgrad i komponentgrafen, og oppgi det minste antallet startnoder
  • kunne begrunne hvorfor den lineære løsningen slår den som traverserer fra hver enkelt node, og hva den forskjellen betyr for uttellingen
5.5DRILL — Grafalgoritmer i pseudokode: mønstergjenkjenning
  • kunne gjenkjenne hvilket klassisk grafproblem en innpakket oppgave egentlig er, og navngi det eksplisitt i besvarelsen
  • kunne skrive presis pseudokode for bredde-først-søk, avgrenset bredde-først-søk, dybde-først-søk over alle komponenter, tofarging og sterkt sammenhengende komponenter
  • kunne oppgi antagelser om representasjon og en kjøretid som matcher algoritmen du faktisk skrev, med antall noder og antall kanter definert
  • kunne velge løsningen med lavest kjøretid og begrunne i én setning hvorfor lavere ikke er mulig
5.PPrøver til del 5: Grafer: representasjon, traversering og komponenter
  • kunne krysse av for grafegenskaper og for kjøretidene til naboliste og nabomatrise uten oppslag
  • kunne skrive bredde-først- og dybde-først-traversering i pseudokode fra hukommelsen, med riktig kjøretid for hver variant
  • kunne skrive tofarging og komponenttelling i pseudokode og kjøre dem for hånd på en oppgitt graf
  • kunne løse en «hvem når hvem»-oppgave med én kjøring av komponentalgoritmen og begrunne at kjøretiden er lavest mulig

6Korteste vei, spenntrær og grådighet

6.1Topologisk sortering og DAG-egenskaper
  • kunne håndkjøre Kahns algoritme på en rettet graf og oppgi rekkefølgen, eller melde at grafen er syklisk
  • kunne skrive topologisk sortering i pseudokode med inngradstabell, kø og sykelsjekk
  • kunne begrunne kjøretiden ved løkketelling, og forklare hvorfor den er en sum og ikke et produkt
  • kunne gjenkjenne at et avhengighetsproblem skal løses med topologisk sortering, og oppgi lavest mulig kjøretid
6.2Korteste vei — BFS, Dijkstra, DAG og reversert graf
  • kunne velge riktig korteste-vei-algoritme ut fra graftypen, og oppgi kjøretiden for hver av de fire tilfellene
  • kunne håndkjøre Dijkstras algoritme og oppgi avstandstabellen ved terminering
  • kunne skrive Dijkstra og DAG-metoden i pseudokode med antagelser, invariant og kjøretid
  • kunne forklare hvorfor én negativ kant er nok til å ødelegge Dijkstra, selv i en graf uten sykler
6.3Minimale spenntrær — Prim, Kruskal, Borůvka
  • kunne håndkjøre Prim og Kruskal på en urettet vektet graf og oppgi kantene og totalvekten
  • kunne skrive Prim i pseudokode med antagelser, grunnidé og kjøretid, også for en komplett graf
  • kunne begrunne hvorfor bredde- og dybde-først-søk ikke finner minimale spenntrær
  • kunne gjenkjenne at «koble alt sammen billigst» er et spenntreproblem, og at korteste vei i det ferdige treet er en traversering
6.4Huffman-koding
  • kunne bygge et Huffman-tre fra en frekvenstabell for hånd og oppgi kodelengden per symbol
  • kunne regne ut totalt antall bits og sammenligne med en fast koding
  • kunne forklare hvorfor kodene danner en prefikskode, og hva det betyr for dekoding
  • kunne oppgi kjøretiden og si hva størrelsen i den står for
6.5DRILL — Korteste-vei-matrisen og MST-modellering
  • kunne fylle inn korteste-avstander-matrisen og kjøretidstabellen for grafalgoritmene uten oppslag
  • kunne gjenkjenne hvilket av Del 6-problemene en oppgavetekst beskriver, ut fra signalordene
  • kunne skrive svaret i de fire leddene sensor krever, med kjøretid som matcher algoritmen
  • kunne velge den raskeste korrekte algoritmen og begrunne hvorfor en tregere løsning gir færre poeng
6.PPrøver til del 6: Korteste vei, spenntrær og grådighet
  • kunne velge riktig grafalgoritme ut fra oppgavetekstens signalord og oppgi kjøretiden
  • kunne håndkjøre Dijkstra, Prim, Kruskal, Kahn og Huffman feilfritt og oppgi sluttilstanden
  • kunne skrive en Del 2-besvarelse i de fire leddene sensor krever
  • kunne regne ut hva en antigjettings-skalering krever av sikre svar

7Datastruktur-design, drøfting og NP-teori

7.1ADT-design — mediankø, bøttekø og trie
  • kunne designe en mediankø med to heaps, formulere invarianten og oppgi kjøretid per operasjon
  • kunne velge bøttekø framfor heap når antall prioritetsnivåer er fast og lite, og begrunne valget
  • kunne forklare hvorfor et trie gir prefikssøk som et hashmap ikke gir, og hva det koster i minne
  • kunne kombinere to strukturer når ingen enkeltstruktur gir alle operasjonene billig
7.2Drøft to strategier
  • kunne definere hva $n$ står for i en drøftingsoppgave, og navngi de andre størrelsene som kjøretiden avhenger av
  • kunne oppgi både verste og forventet kjøretid for to strategier, og sammenligne minnebruken deres
  • kunne kjenne igjen kanttilfellene som avgjør sammenligningen — stort verdiområde, kollisjoner og ferdig ordnet inndata
  • kunne konkludere med en betingelse i stedet for å stanse ved «det kommer an på»
7.3NP-kompletthet — og hva som IKKE er IN2010-pensum
  • kunne skille mellom å løse et problem og å kontrollere et foreslått svar, og bruke skillet til å plassere et problem i $P$ eller $NP$
  • kunne skrive en verifikator i pseudokode som kontrollerer et sertifikat i polynomisk tid, inkludert den siste kanten i en rundtur
  • kunne begrunne hvilken vei en polynomisk reduksjon må gå for å vise at et problem er vanskelig
  • kunne avgrense pensum og navngi de tunge algoritmetemaene som ikke testes i dette emnet
7.PPrøver til del 7: Datastruktur-design, drøfting og NP-teori
  • kunne håndkjøre en mediankø og en bøttekø og oppgi sluttilstanden i det formatet eksamen krever
  • kunne skrive en drøfting som treffer alle fire leddene sensor krever, og som ender i en betingelse
  • kunne skrive en verifikator med korrekt behandling av den siste kanten i en rundtur
  • kunne avgjøre hvilken vei en reduksjon må gå, og hvilke temaer som ikke er pensum i emnet

8Eksamenstrening

8.1DRILL — Del 2-strategi: velg lavest kjøretid (poengtrappen) og skriv presis pseudokode
  • kunne finne den raskeste korrekte løsningen på en Del 2-oppgave ved å gå gjennom de fem faste grepene
  • kunne skrive svaret i de fire leddene sensor krever, med kjøretid som matcher algoritmen og med n definert
  • kunne begrunne hvorfor en tregere korrekt løsning gir færre poeng, og hvor mye
  • kunne levere en besvarelse i klart naturlig språk som gir like mye uttelling som pseudokode
8.2Øvingseksamen 1 — bredt ordinært sett (epoke 3)
  • kunne gjennomføre et komplett firetimers sett uten hjelpemidler og fordele tiden mellom de tre delene
  • kunne svare sikkert på auto-rettede kjøretids-, sorterings-, heap- og graf-fakta under antigjettings-skalering
  • kunne håndkjøre min-heap og lineær probing og oppgi sluttilstanden i eksamensformatet
  • kunne skrive presise pseudokodesvar for tre-, hashing- og grafoppgaver med kjøretid som matcher algoritmen
8.3Øvingseksamen 2 — håndkjørings- og hashing-tungt sett
  • kunne håndkjøre min-heap, lineær probing, AVL-rotasjoner og Huffman-koding feilfritt og levere sluttilstanden i riktig format
  • kunne skrive hashing- og søkealgoritmer i pseudokode med korrekt forbehold om forventet og verste kjøretid
  • kunne bruke søketre-egenskapen til å beskjære et søk i stedet for å traversere hele treet
  • kunne drøfte to strategier med definerte størrelser, verste og forventet kjøretid, minne og en betinget konklusjon
8.4Øvingseksamen 3 — grafmodellerings-tungt topp-sett
  • kunne gjenkjenne hvilken pensumalgoritme en åpen modelleringsoppgave beskriver, ut fra signalordene i teksten
  • kunne velge den raskeste korrekte grafalgoritmen og begrunne hvorfor en tregere løsning gir færre poeng
  • kunne kombinere topologisk sortering og sterkt sammenhengende komponenter i samme oppgave
  • kunne designe en datastruktur av kjente byggeklosser og oppgi kjøretid per operasjon
Tilbake til IN2010 Algoritmer og datastrukturer