Beskjeder
Eksamensoppgaven for 2005 ligger her
Hjelpemidler til eksamen. Bare så det ikke skal være noe tvil: De lovlige hjepemidler til eksamen er: "Alle trykte og skrevne".
Den detaljerte pensum-listen er nå ferdig oppdatert.
Prøveeksamen med svarforslag (litt rettet etter gjennomgåelsen) er lagt ut her
Prøveeksamen er lagt ut her . Det har vært vanskelig å vurdere arbeidsmengden, men vi ønsket å få med oppgaver fra forskjellige deler av pensum. Oppgavene blir altså gjennomgått i vanlig undervisnigstid torsdag 1/12.
Avslutning av konkurransen: Juryen (Karianne, Patricia og Stein) har kjørt de innkomne forslag, men vi røper her intet om selve resultatet. Vi kan imidlertid opplyse at det hendte at noen gikk ut på plassmangel, og at svarene noen ganger av vårt system ble oppfattet som gale. Selve avslutningen forgår i Lille Aud. torsdag 1 des., kl. 15.15 (etter gjennomgåelse av prøve-eks.). Vi synes det da var fint om hvert lag først forteller kort om sitt program (2-3 minutter), ved speiselt å beskrive: (1) Generell metode, (2) impl. av prioriteskø, (3) heuristikk og (4) representasjon av brettene. Deretter skal vi kanskje vise noen typiske kjøringer, og til slutt utropes vinneren av hver klasse, og det blir utdelig av diplom med noe attåt.
Noen har spurt om hva "antall forbedringsskritt" er i oppgave 3 i Oblig 2. Det er det antall ganger man leter etter og finner forbedringveier som så brukes til å øke flyten. I eksempelet på side 440/441 er altså antall forbedringsskritt lik 6.
Levering til konkurransen: Deltakere i konkurransen skal legge løsnings-metoden inn i en klasse som må implementere en interface vi har laget. Denne ligger på filen "~inf3130/Konkurranse/Puzzle.java", og den har kommentarer som nærmere angir hvordan ting skal gjøres. Les disse nøye. Fristen er altså torsdag 24/11, og programmet skal sendes til gruppelæreren. Angi hvilken klasse du/dere stiller i. Premieutdelingen vil foregå under gjennomgangen av prøve-eksamen, torsdag 1/12 kl 14.15."
Om løsning av oppgave 3 i Oblig 2. Merk for det første at det å lagre ting i arrayer som foreslått i oppgaven bare én måte å gjøre det på. Mange andre er også helt OK. For det andre står det i oppgaveteksten: "Ellers er det jo bare å gjennomføre et bredde-først søk med en FIFO-kø, ...". Det kunne gi inntrykk av at det bare skal gjøres ett slikt søk, men det er feil. Man må gjøre et slikt søk i grafen Nf hver gang man vil finne en ny forbedringsvei (og mellom hvert søk forandrer Nf seg). Se figur 14.9, men pass på alle trykkfeilene.
Svarforslag for testdata for Oblig2 er lagt ut, se "~inf3130/Oblig2/Test-svar.txt" Si fra (til "steinkr@ifi.uio.no") om det er noen uoverenstemmelser.
KONKURRANSEN: Nytt nå er at det blir satt opp to klasser: én for spesialistene og én for oss dødlige (og det er vel kanskje urimelig at samme lag får være med i begge klasser?). Som det ser ut nå vil vi begrense lagerstørrelsen til 64MB (som er standard på javac på Linux). I spesielist-klassen vil konkurransen etter alt å dømme bli å løse så mange som mulig av en sekvens av vanskeligere og vanskeligere 4x4-brett (om vi da ikke må opp i 5x5-brett!?). Hver oppgave må løses før man går videre. I den litt snillere klassen brukes bare 3x3-brett, og her gjelder det å komme gjennom flest mulig fra en tilfeldig generert sekvens av oppgaver. Også her må alle løses. Nærmere info kommer om hvordan tidsmåling skal foregå etc.
Testdata til Oblig2: Svar ønskes! På filene "~inf3130/Oblig2/Opg1-test1.txt" og tilsvarende ligger noen testdata (tre filer for 0ppgave 1 (vanskeligere og vanskeligere!), og én for oppgave 3). Jeg (SK) har dessverre ikke løsningene, så om noen har kommet så langt, mottar jeg gjerne løsninger, som jeg da vil legge ut.
For de som ikke har Weiss-boka er kap 6 og 11.4 kopiert opp (like mange som sist: 4), og kan hentes i luka på instituttkontoret, informatikk.
Det er nå lagt ut en detaljert (men ikke endelig) pensumliste under "pensum og litteratur".
NB: Etter anmodning fra studentene er fristen på Oblig 2 utsatt til 21. nov., men merk at man må ha obligen helt godkjent 30. nov. for å få gå opp til eksamen. (Om du tok ut oppgaven før 1/11, kl 15.30, ta den ut på nytt!). Fristen for å levere inn konkurranse-program er 24/11.
Takk til alle som deltok i Underveis-evalueringen! Vi arbeider nå med å komplettere svarforslagene (første uke er lagt ut), med å lage en detaljert pensumliste, og med å få ferdig oblig 2.
Det vil bli tillatt med skriftlige hjelpemidler til eksamen.
Underveis-evaluering av kurset: På forelesningen 20. okt. blir det satt av litt tid så dere kan besvare et enkelt skjema om hva dere synes om kurset (såkalte 5-minutterslapper). Tenk litt på om dere har forslag til forbedringer av kurset. Hva fungerer og hva fungerer ikke?
Delta i konkurransen 15-spillets mysterier! Se under "Oppgaver og øvelser".
Leveringsfristen for obligatorisk oppgave 1 er utsatt til torsdag 20. oktober. Leveringsanvisning er lagt ut (under "Oppgaver og øvelser").
Notat om matching-algoritme for ikke-bipartite grafer er lagt ut under pensum og litteratur.
Foilene fra 6. oktober er lagt ut i forbedret stand.
Det blir verken gruppeøvelser eller forelesning i uka fra 10. til 14. oktober.
Ny og presisert utgave av den obligatoriske oppgaven er lagt ut. Det dreier seg i stor grad om hvordan input/output skal gjøres for testdata. Noen steder er det også gitt større frihet.
OBLIG 1: Det er kommet inn en del kommentarer og spørsmål om obligen, så en ny versjon med presiseringer og bedre forklaringer kommer senest mandag morgen (kanskje også gjort slik at alle programmene greit skal kunne kjøres). Angående LØU så kunne sikkert det vært bedre forklart, men om T = 9, 1, 6, 2, 4, 7, 5, så er en løsning på LØU: 1, 2, 4, 5 (med lengde 4, og med indeksmengde i T: 2, 4, 5, 7).