Foreløpig pensumoversikt for høsten 2011

Denne høsten innfører vi en ny ordning, med to alternative lærebøker. Pensum dekkes jevngodt av bøkene, og det er fritt valg mellom dem.

Alternativ 1: Introduction to Algorithms, tredje utgave (Cormen et al., 2009)

Dette er den boka som har blitt brukt i faget i flere tiår. Den regnes som en klassiker, og er svært grundig på det formelle.

Alternativ 2: Algorithm Design (Kleinberg & Tardos, 2006)

Denne boka er noe mindre grundig på det formelle, men kan til gjengjeld være mer lettlest og pedagogisk.

Merk: Du trenger kun én av disse. Det er ikke nødvendig å lese begge to. Hvilken du velger kan for eksempel være basert på anlegg og interesse for mer matematisk orienterte fag.

Stoffet som dekkes av de to bøkene er ikke identisk, men eksamen vil utformes slik at begge gir like godt grunnlag for å besvare oppgavene. Dette betyr ikke at det kun er de overlappende delene av pensum som er relevant. (Det kan f.eks. stilles oppgaver med valgfrie deloppgaver som er tatt fra hver sin bok.)

Det er også mulig å bruke 2. utgave av Cormen, sammen med det av ekstramaterialet angitt for Kleinberg (nedenfor) som ikke er dekket av boka.

Pensumavsnittene er oppgitt i det følgende. (Antall sider er omtrent det samme for begge varianter.) Det tas forbehold om mindre endringer.

Pensum, alle

Forelesningsfoilene til hovedforelesningene (altså ikke øvingsforelesningene) er pensum. (Link til disse finnes i it's:learning.)

Pensum, Cormen

Kapittel 1, 2, 3, 4.3–4.5, 6, 7.1–7.3, 8, 9, 10.1, 10.2, 10.4, 11.1–11.4, 12.1–12.3, 15, 16.1–16.3, 22.1–22.4, 23, 24.1–24.3, 25.2, 26.1–26.3, 27.1, 34.5 (uten bevis).

Innledningsdelen er også pensum i alle kapitler som inneholder pensumavsnitt.

Pensum, Kleinberg

Kapittel 1, 2, 3, 4.1–4.8, 5.1–5.4, 6.1–6.8, 6.10, 7.1, 7.2, 7.5, 7.6, 7.8–7.12, 8.1–8.8, 8.10, 13.5–6.

Ekstramateriale:

• Artikler om lineær sortering, bucket sort, binære søketrær, og Floyd-Warshall.
• A Minicourse on Multithreaded Programming av Leiserson og Prokup (dekker samme stoff som Cormens kapittel 27.1).

Anbefalt støttelitteratur

Om du synes forklaringene i begge lærebøkene er tung å forstå, eller vil ha en mer kort og konsis oversikt (i litt samme stil som forelesningene), med tilhørende Python-implementasjoner av alle algoritmene, så er Python Algorithms (Hetland, 2010) anbefalt som et supplement. Merk at denne boka ikke er pensum.