INF2200 (1-5 okt) 15-19 okt =========================== P? grunn av Oblig1 var det ingen ukeoppgaver sist uke, denne uken er det derfor litt ekstra. Disse vil bli presentert f?rst i uke 42 pga. undervisningsfri uke 41. Oppgave 1 Fra MAW: 6.1, 6.2, 6.3, 6.4, 6.10a Oppgave 2 a) Hva m? til for at en heap skal f? en FIFO-struktur p? objektene med lik prioritet? Foresl? datastruktur og endringer i koden for insert og deleteMin. b) Foresl? en datastruktur som underst?tter operasjonene decreaseKey, increaseKey og delete. Skisser kode for operasjonene. Oppgave 3 --------- a) Tegn den rettede grafen som tilsvarer denne nabomatrisen: 0 1 2 3 0 T F T F 1 T F F F 2 F F F T 3 T F T F b) Tegn nabo-liste representasjonen av denne grafen. Oppgave 4 --------- Vi skal se p? noen typer rettede grafer, der alle typene er slik at alle noder har maksimalt en etterf?lger, men gjerne flere forgjengere. Blant disse grafene finnes blant annet vanlige line?re lister, enkle sykliske strukturer (l?kker), samt rotrettede tr?r. Det finnes imidlertid ogs? mange andre grafer innenfor denne rammen. Tegn forskjellige forslag. Vi skal anta at vi har en slik graf representert ved noder av typen: class Node { Node etterf; // Er null om det ikke finnes etterf?lger int merke; // Eventuelle data.. } Det er n noder, og for ? f? tilgang til nodene har vi en array Node[] graf = new Node[n]; som peker ut alle nodene i TILFELDIG rekkef?lge. Vi skal lage tre boolske metoder: a) En som unders?ker om grafen er en enkel line?r liste, som ender med null. b) En som unders?ker om grafen best?r av en enkel rettet l?kke. c) En som unders?ker om grafen er ETT rotrettet tre. Det er alts? en int variabel "merke" i hver node, og denne vil v?re null n?r metodene starter, og metodene kan bruke den som de vil. Fors?k ? klare deg med ? bruke s? f? forskjellige verdier som mulig for denne variabelen, eller helst ? IKKE BRUKE DEN I DET HELE TATT. Oppgave 5 - Labyrint -------------------- Anta at en person st?r ved inngangen til en labyrint. Et eller annet sted inne i labyrinten finnes det en skatt. a) Hvordan vil du representere en slik labyrint som en graf? b) Skriv et program som s?ker gjennom labyrinten (grafen) og dirigerer en skattejeger frem til rommet med skatten og ut igjen. (S?kingen gjennom labyrinten burde v?re en relativt grei oppgave, mens utskriften/dirigeringen fort kan bli litt fiklete.) c) Gir instruksjonene som blir skrevet ut fra punkt b den raskeste veien til skatten? Hvis ikke, lag et nytt program som gj?r dette. Lag sm? labyrint-eksempler slik at du f?r sjekket at programmet ditt virker!