Hashing
Oppgave 1
Implementer algoritmene fra forelesningen.
Oppgave 2–9 (fra læreboka)
- R-6.1
- R-6.2
- R-6.4
- R-6.5
- R-6.6
- R-6.7
- R-9.2
- C-6.7
Oppgave 10 (Hashtabell kompleksitet)
Hva er kompleksiteten i O-notasjon av å finne maksimum og mininimum av verdiene lagret i en hashtabell?
2-sammenhengende grafer, sterkt sammenhengende komponenter
Oppgave 1
Implementer algoritmene fra forelesningen.
Andre oppgaver (pdf fra 2021)
Kortest vei, minimale spenntrær
Oppgave
Implementer algoritmene fra forelesningen.
Graftraversering
Oppgave 1–5 (fra boka)
- R-13.5
- R-13.6
- R-13.7
- C-13.15
- C-13.16
Oppgave 6 (Eulerkrets)
En Eulerkrets i en graf G er en vei som starter og slutter i samme node og er innom alle kantene i G nøyaktig en gang. Lag en algoritme som finner ut om G inneholder en Eulerkrets. Output skal være true/false. Kjører algoritmen i polynomiell tid? Begrunn svaret. Hint: Det finnes en egenskap som har med graden til nodene i G å gjøre, som nøyaktig bestemmer om G har en Eulerkrets eller ikke.
Oppgave 2 (Hamiltonsykel)
En Hamiltonsykel i en en graf G er en sykel som inneholder hver node nøyaktig en gang. Lag en algoritme som løser Hamiltonsykel. Output skal være true/false. Hint: Enn så lenge har ingen klart å finne en algoritme som løser dette problemet i polynomiell tid, så ikke ta det så tungt om også din algoritme bruker eksponensiell tid.
Sortering; flette-, kvikk-, bøtte- og radixsortering.
Oppgave 1–4
Implementer de 4 sorteringsalgoritmene merge, quick, bucket og radix sort.
Oppgave 5–11
- R-8.3
- R-8.4
- C-8.3
- C-8.5
- A-8.2
- R-9.1
- R-9.2
Uke 38 (19. sep.–23. sep.) Sortering; boble-, utplukks-, innstikks- og heapsortering
Oppgave 1
Implementer Bubble sort (boblesortering)
Oppgave 2
Implementer Selection sort (utplukkssortering)
Oppgave 3
Implementer Insertion sort (innstikkssortering)
Oppgave 4
Implementer Heap sort (heapsortering)
Oppgave 5
Oppgaver fra læreboka (G&T):
- R-5.1
- R-5.2
- R-5.4
- R-5.5
- R-5.9
- R-5.11
- A-5.6
Oppgave 6 (Sammenligningsbaserte sorteringsalgoritmer)
- Skriv et program som sorterer fire elementer. Hvor mange sammenligninger kan du klare deg med?
- (Vanskelig?) Skriv et program som sorterer fem elementer ved hjelp av sju sammenligninger.
Uke 37 (12. sep.–16. sep.) prioritetskø, binære heaps, huffmankoding
Oppgave 1–3
Implementer algoritmene fra forelesningen (uke 36).
Oppgave 4–13 (fra boka)
- R-5.13 – R-5.15
- C-5.4
- C-5.9
- R-10.5 – R-10.9
Oppgave 14
A file contains only spaces and digits in the following frequency: space (9), a (5), b (1), d (3), e (7), f (3), h (1), i (1), k (1), n (4), o (1), r (5), s (1), t (2), u (1), v (1).
Construct the Huffman code.
Oppgave 15
A file contains only colons, spaces, newlines, commas, and digits in the following frequency: colon (100), space (605), newline (100), comma(705), 0 (431), 1 (242), 2 (176), 3 (59), 4 (185), 5 (250), 6 (174), 7 (199), 8 (205), 9 (217).
Construct the Huffman code.
Uke 36 (5. sep.–9. sep.) trær
Oppgave 1–14
Implementer algoritmene fra forelesningen (uke 35).
Oppgave 15 (Binære søketrær)
Gitt et binært søketre, skriv pseudokode for en prosedyre som
- (a) returnerer det minste elementet i treet
- (b) returnerer det største elementet i treet
- (c) returnerer lengden på den korteste stien fra roten til en nullpeker
- (d) returnerer lengden på den lengste stien fra roten til en nullpeker
Merk: vi definerer lengden til en sti til å være lik antall kanter i stien.
Oppgave 16 (Balanserte søketrær)
Bygg, steg etter steg, AVL-trær som er resultatet av å innsette følgende sekvenser av elementer:
(a) 41 38 31 12 19 8
(b) A L G O R I T H M
Ekstraoppgave: gjør tilsvarende for rød-svarte trær.
Oppgaver fra læreboka
- R-4.1
- R-4.4
- R-4.6
- R-4.7
- C-4.9
- C-4.14
- Ekstraoppgave: finn et rød-svart tre som ikke kvalifiseres som et AVL-tre
Uke 35 (29. aug.–2. sep.)
Vi anbefaler å implementere alle algoritmer i pensum (forelesninger).
Oppgave 1
Derfor blir første oppgave å implementere binærsøk (iterativ versjon fra forelesningen) i Java/Python (eller et annet språk).
Oppgave 2
Implementer binærsøk reksursivt.
Oppgaver om O-notasjon:
Fra boka (Goodrich&Tamassia):
R-1.9, R-1.11–1.15
C-1.8
C-1.19 (ignorer minnerestriksjonen)
C.1.24
Variant av C.1.24: La A være et array (lengde n) og ikke en matrise. Finn en algoritme som teller hvor mange 1ere A inneholder. Tips: dette kan gjøres raskere enn lineær tid.
Oppgaver fra Kattis
Løsningsforslag på gruppene (men man rekker neppe alle).