Errata

Dette er en oversikt over feil som har sneket seg inn i forelesningene og pensumheftet, høsten 2024.

Side 353: Her står det at vi normalt antar at heltall er maks $c\lg n$, for problemstørrelse $n$ og en eller annen $c\ge 1$. Det riktige er at vi antar at de representeres med maksimalt $c\lg n$ bits.

Side 180: Her skulle det ha stått «satellittdata».
Side 316–340: Tallene for innsetting er tatt fra en tidligere versjon, som tok hensyn til allokering. Heller enn $1, 2, 4, 8, 16$ skulle antallene ha vært $1, 1, 2, 4, 8$, så antallet innsettinger totalt blir $n$.

Side 103: Her skal det stå «Øk $p$ og krymp $i$», ikke «Øk $p$ og $i$».
Side 222–254: Prosedyrene Radix-Sort, Xidar-Non-Sort og Unstable-Non-Sort skal ta inn $n$ som sitt andre argument.
Side 230–254: Verdiene til $i$ (nederst til venstre) er gale. De teller oppover der pseudokoden og figuren teller nedover, og omvendt.
Side 269–311: Hvis bøttene er lenkede lister, bør nye elementer settes inn på starten heller enn slutten, for å få konstant kjøretid på innsettingen.

Side 45: Dette stemmer ikke lenger. Denne siden skulle ha vært slettet.
Side 314: «Gjennomsnittlig arbeid per node» er litt upresist her (selv om det er asymptotisk riktig), siden vi har delt på $2^h$ og ikke $n=2^{h+1}-1$.
Side 385–391: Navnene her er fra forrige utgave av pensum. Erstatt Heap-Max med Max-Heap-Maximum, Heap-Extract-Max med Max-Heap-Extract-Max og Heap-Increase-Key med Max-Heap-Increase-Key.

Side 323: Her har en tekstkommentar blitt delvis skjult. Teksten skal være:

Med andre ord: Navnet har vært brukt litt forskjellig, og handlet opprinnelig om en spesifikk type optimeringsproblemer. Vi behandler det bare som enda et navn på det samme vi har gjort hele veien – men i den mest generelle formen, der vi tillater at samme delinstanser brukes på flere måter i dekomponeringen, i motsetning til det vi (i motsetning til det Martin, Rardin & Campbell sier) kaller divide-and-conquer, der vi ikke har overlapp melom delinstanser.
Side 27: Dette burde være stier som får lov til å gå innom en gitt node (jf. hvordan Floyd–Warshall fungerer). Vi kan da fjerne ev. sykler som dukker opp for korteste vei, uten at det skader, men det fungerer ikke for lengste (enkle) vei.
Side 47: Her skulle det ha stått Cut-Rod og ikke Cut.
Side 371–372: Her står det «har er». Det skulle ha vært «er».
Side 619–626: Mangler sidetall.

Side 483: «DFS-skog» skal være «DF-skog» (som i «dybde-først-skog»).
Side 733: «fra $s$ til $s$» skal være «fra $s$ til $v$». (På side 734 er «fra $s$ til $s$» korrekt.)