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).