Øvinger og Nøtter
AlgKons
Innholdsfortegnelse |
Total Highscore
Til enhver tid oppdatert highscore for alle øvingene finnes her.
Øvinger
Målet er å gi ut en ny relevant øving 5 ganger i løpet av semesteret. Øvingene er ikke obligatoriske, men det anbefales at studenter jobber med øvingene. Alle øvinger unntatt en skal leveres på vår Programming Playground, som finnes her: http://feiten.idi.ntnu.no/playground/. Øvingene vil legges under eventen "AKVK 2007".
Øvingene har tidsfrist, men de vil være åpne etter tidsfristen. Ved semesterslutt blir det muligens en liten premie til de som har gjort beste innsats med øvingene i faget.
For å levere må dere registrere dere på Programming Playground. Vi legger ingen føringer for valg av nick, men ta med fullt navn.
Øving 1/Exercise 1
Øving 1 ligger her. An english version is available here.
Øving 3/Exercise 3
Øving 3 skal ikke leveres på Programming Playground, men er laget for at dere skal få leke litt med paralellitet, f.eks. i Java. Den finnes her.
Exercise 3 should not be handed in on Programming Playground, but we hope you will spend some ting playing with parallel programs. The exercise is available here.
Sample solution: here
Øving 4/Exercise 4
Øving 4 består av to oppgave, Blomster-Simon og Ikke mer WoW!, som begge ligger ute på playground under eventen AKVK2007. Lykke til!
Exercise 4 is out. You can find the two problems in these exercise at playground. They are called Blomster-Simon (Flower-Simon) and Ikke mer WoW! (No more WoW!). Good luck!
Øving 5/Exercise 5
Exercise 5 is out.
Nøtter
Innimellom vil vi legge ut noen nøtter her. Målet er at disse skal få dere til å tenke litt. Dersom du finner ut svaret på en nøtt kan du sende svaret til trulsamu@idi.ntnu.no. Vi vil gå gjennom svaret på forrige nøtt når en ny presenteres i øvingstimen.
Nøtt 1
English version I denne nøtten har du 12 kuler og en skålvekt.
Del 1
Du får vite at en av kulene er tyngre enn de andre. Hva er det minste antall veiinger du trenger for garantert å finne denne? Hva er strategien din?
Del 2
Du får vite at en av kulene er enten tyngre eller lettere enn de andre. Hva er det minste antall veiinger du trenger for garantert å finne denne? Hva er strategien din?
Del 2
Du får vite at en av kulene muligens er enten tyngre eller lettere enn de andre. Hva er det minste antall veiinger du trenger for garantert å finne denne hvis den eksisterer, eller slå fast at det ikke er tilfelle? Hva er strategien din?
Studenter med riktig løsning på nøtt 1(sortert etter innleveringstid)
1. Kjetil Johannesen
2. Karl Yngve Lervåg
3. Eirik Reksten
Riktig løsning på nøtt 1 (Kjetil Johannesen)
Del 1
- 3 veiinger.
- Første veiing er 4 mot 4, da får vi avgjort hvilken gruppe på 4 som inneholder den tunge kulen (den som går ned, eller de 4 uveide
hvis det blir likt).
- Andre veiing er 2 mot 2 og vi beholder de 2 kulene som gikk ned
- Siste veiing er en mot en for å avgjøre hvilken av de to kandidatene som er tyngst.
Del 2
- Fortsatt 3 veiinger
- Først 4 mot 4. Men her får vi derimot ikke garantert vite hvilken 4-gruppe som inneholder den abnormale kulen siden vi ikke vet om
den er tyngre eller lettere. Får dermed to muligheter
- Andre veiing del 1
- hvis likevekt er kulen blandt de 4 uveide og vi veier da tre av disse mot tre av 'kontrollkulene' vi vet ikke er noe spesielt
med. Vi finner da ut om kulen er lettere eller tyngre.
- hvis disse igjen var likevekt, er oppgaven løst, kulen er da den 12 uveide kulen, hvis ikke, så vil den tredje veiingen være en
av de tre abnormale kandidatene mot en annen av de andre kandidatene. Siden vi vet om den er tyngre eller lettere vil dette da gi oss svaret (likevekt=3.kulen, ene siden opp/ned så blir det den respektive kulen alt ettersom den er lettere/tyngre)
- Andre veiing del 2
- hvis derimot ene siden i 4 vs 4 veiingen går opp, så legger vi spesielt merke til hvilke kuler det var som gikk opp, og hvilke
som gikk ned. Vi kaller disse heretter henholdsvis opp- og nedkuler.
- Vi veier 2 opp-, og 1 nedkule på den ene skålen og 2 opp- og en nedkule på den andre skålen.
- Hvis likevekt, har vi kun to alternativer igjen, det er to nedkuler. Vi veier disse mot hverandre og finner ut hvilken som går
opp. Søkt kule er funnet.
- Hvis derimot veiing 2 fører til fortsatt uliket, står vi igjen med tre alternativer. Enten så var det den ene kulen som var
tung som fikk ting til å gå ned, eller en av de to opp-kulene som fikk den siden til å gå opp. Vi veier da en av de to opp-kulene og den ene nedkulen på samme skål mot 2 kontrollkuler. Hvis skålen går opp er det oppkulen,ned = nedkulen, og likevekt vil gi den andre oppkulen.
Del 3
Du får vite at en av kulene muligens er enten tyngre eller lettere enn de andre. Hva er det minste antall veiinger du trenger for garantert å finne denne hvis den eksisterer, eller slå fast at det ikke er tilfelle? Hva er strategien din?
- 3 veiinger
- Nøyaktig samme fremgangsmåte som den del 2 vil gi svaret. Straks du ser at en side går opp, vet du at kulen finnes og
oppgaven blir identisk lik forrige. Derimot hvis den ikke eksisterer, vil alle veiingene føre til likevekt, noe som ifølge algoritmen gitt i forrige delspørsmål ende opp med en veiing 1 mot 1 (etter å ha avslørt at det ikke er noen av de 11 første), og likevekt her vil da avkrefte at det er en abnormal kule...
Nøtt 2
English version Disse reglene gjelder for begge delene:
Du sitter foran et rundt bord, delt inn i 4 like kvadranter, med bind for øynene. I hver kvadrant står det en kopp. Kvadrantene er merket med bokstaver (A, B, C og D), og disse merkingene flytter seg ikke. Til å begynne med er hver kopp snudd tilfeldig med åpningen opp eller ned.
For hver runde roteres koppene på bordet av en hjelper.
Del 1
Du som spiller kan kjenne på nøyaktig to kopper. Etter å ha gjort dette kan du sette dem tilbake hvilken vei du vil. Dersom alle koppene nå er orientert samme vei, får du vite at du har vunnet. Hvis ikke spilles en ny runde.
Hva er det minste antall trekk du må gjøre for å være sikker på å ha vunnet? Hva er strategien din?
Del 2
Du som spiller kan be hjelperen din om å snu et vilkårlig antall kopper i kvadranter du velger fritt (du kan for eksempel si "snu koppene i A, B og D"). Hjelperen gjør som du ber om, og dersom alle koppene nå har åpningen opp, har du vunnet. Dersom dette ikke er tilfellet roteres koppene tilfeldig etter samme regler som i del 1, hvorpå det spilles en ny runde.
Hva er det minste antall trekk du må gjøre for å være sikker på å ha vunnet? Hva er strategien din?
For ytterligere klargjøring av hva det vil si at medhjelperen roterer koppene:
Dersom koppene har nummer og står som følger:
A:1 B:2 C:3 D:4
Vi vil da, etter at medhjelperen har rotert koppene, ha 4 muligheter for hvordan koppene står:
A:1 B:2 C:3 D:4
A:2 B:3 C:4 D:1
A:3 B:4 C:1 D:2
A:4 B:1 C:2 D:3
Studenter med riktig løsning på nøtt 2(sortert etter innleveringstid)
1. Karl Yngve Lervåg 2. Arne Bergende Fossa
Anbefalte teorioppgaver fra Cormen/Recommended exercises from the textbook
Approximation
- 35.1-3
- 35.1-4
- 35.2-2
- 35.2-5
- 35.3-1
- 35.1
Amortized analysis
- 17.1-3
- 17.2-1
- 17.3-2
Randomization
- 5.1-1
- 5.2-1
- 5.2-2
- 5.2-4
- 5.3-1
Sorting networks
- 27.1-2
- 27.1-5
- 27.2-5
- 27.3-2
- 27.5-1
- 27.5-2
- 27-1
- 27-3
Anbefalte eksamensoppgaver
- August 2006: 1, 5, (2)
- Juni 2006: 1, 5, (2)
- Juni 2005: 1, 3
- Juni 2004: 1, 4, (2)
- August 2003: 1, 3
- Mai 2003: 1, 3
- Mai 2002: 1, 4, 5
