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