Kunsten å prioritere
Kjære IN2010,
Forrige uke lærte vi hvordan vi kan holde trær balanserte ved hjelp av rotasjoner. Ved å bruke en slik struktur, så får garantert logaritmisk tid på innsetting, sletting og oppslag. Et viktig poeng her er at vi velger å legge litt mer arbeid inn i hver operasjon, og ved å gjøre det, så unngår vi vesentlig mye mer arbeid i fremtiden!
Frist for den første obligatoriske oppgaven
Den første obligatoriske oppgaven skal leveres førstkommende fredag! I den skal du, blant annet, implementere binære søketrær med og uten selvbalansering. Den andre oppgaven er en liten nøtt, der en løsning fordrer god forståelse for binære søketrær, prioritetskøer og rekursjon; et lite hint er at løsningen er veldig enkel å skrive når man først har funnet den.
Alle grupper skal være opprettet nå, og de som skal levere individuelt skal ha fylt ut skjemaet. Dersom du hverken har opprettet gruppe eller levert skjemaet risikerer du at oppgaven din ikke blir rettet. Vi har åpnet skjemaet slik at du har en siste mulighet til å melde fra i løpet av tirsdag: https://nettskjema.no/a/539942.
Dersom du er syk eller av andre tungtveiende grunner ikke kan levere til den ordinære fristen så kan du levere et egenmeldingsskjema som du finner på innleveringssiden. Det er tilstrekkelig at én på samme gruppe leverer egenmeldingsskjemaet.
Kattis & Kaffe
Igjen vil vi ønske deg velkommen til Kattis & Kaffe i Escape! Det vil foregå hver tirsdag klokken 14:15–16:00 rett etter forelesning. Dette er et helt uformelt opplegg der du er velkommen til å sitte å løse oppgaver fra https://open.kattis.com/ og drikke kaffe med oss som underviser IN2010.
Det flotte med Kattis er at det er så utrolig mange oppgaver, slik at du er nærmest garantert å finne oppgaver som passer ditt nivå. Det er den beste måten vi vet om for å få mengdetrening i programmering, og det trenger du dersom du har ambisjoner om å bli flink til å programmere. En del av oppgavene er relevant for pensum i IN2010, men langt fra alle.
Her er noen oppgaver du kan bryne deg på!
Til uken
I morgen skal vi lære om binære heaps, som er binære trær som oppfyller litt andre egenskaper enn binære søketrær. Det er en enkel og vakker struktur, som lar deg implementere en prioritetskø på en svært effektiv måte. I tillegg skal vi se på Huffman-koding, som er grunnlaget for nesten all form for komprimering av data, og som også viser en veldig fin anvendelse av prioritetskøer!
___
Med vennlig hilsen oss som underviser IN2010