Inlämningsuppgifter
Detta är en sammanställning av inlämningsuppgifter som delats ut
till enskilda studenter eller till samtliga studenter på kursen.
Dessa uppgifter kan ses som ett lämpligt urval för den som önskar
ytterliggare övningsuppgifter.
(Andra lämpliga uppgifter hittas naturligtvis bland de som har
lösningsförslag i boken, dvs de med uppgiftsnumret understruket.)
Gruppövning 2
Kapitel 2: 2, 3, 7, 10, 11, 12, 14, 16, 19
Kapitel 3: 1, 2, 3, (5,) 7, 11, 12, 13, 15, 16
Gruppövning 3
Kapitel 5: 2, 3, 5, 6, 7, 9, 13, 16
Kapitel 6: 10, 15, 21
-
Kan en huffmankodning ge en "komprimerad" fil som
är större en ursprungsfilen? Visa att det kan hända genom att ge ett exempel för
ett alfabet med 8 tecken (dvs normalrepresenation med 3 bitar per tecken) eller
ge ett motbevis.
-
Gör en enkel implemenation av algoritmen för att konstruera
huffmankoder. Beräkna med hjälp av din implementation den optimala kodningen för
följande uppsättning tecken (med antal förekomster inom parentes):
a(10), b(4), c(74), d(26), e(54), f(34), g(45), h(8), i(65), j(64), k(34), l(43),
m(12), n(7). (Gör enklast möjliga implementation, exempelvis med indata i en
vanlig array). När ditt program har beräknat trädet kan du för hand härleda själva
huffmankoden.
Gruppövning 4
Kapitel 6: 16
Kapitel 7: 7.1, 7.2a, 7.2b, 7.5, 7.21, 7.22, 7.25
-
Gör en enkel implemenation av algoritmen för
att matcha strängar. Om du vill göra det enkelt för dig räcker det om
algoritmen klarar av att jämföra tal i två vektorer (dvs, du kan med fördel
göra implementationen i Matlab.) Illustrera algoritmens exekvering genom att
testa det problem som ges i bokens exempel och skriv ut vilka delsträngar
som har jämförts mellan varje skift som görs i "B"-strängen. (För att göra
detta på tal kan du exempelvis byta exemplets x och y mot 1 och 2.)
Gruppövning 5
Kapitel 7: 7, 9, 10, 11, 12a, 12b
Kapitel 8: 1, 2, 3, 5, 8, 9, 12, 15, 18a
Senast ändrad 95-10-03 av
Erik Elmroth
(Email: elmroth@cs.umu.se)