Datastrukturar og Algoritmer

(Sist oppdatert: $Date$)

Utleveringsmateriale til kurset Objektorientert Programmering: Datastrukturar og Algoritmer ved Høgskolen i Ålesund.

Eg vil retta trykkfeil og mindre detaljar fortlaupande, og denne sida vil alltid ha siste versjon. Fronter tillet ikkje automatisert opplasting og kan difor ikkja haldast like oppdatert. Fronter vert brukt til innleveringane og materiale med avgrensa tilgang (i alle fall foilane som høyrer til læreboka).

Innleveringsfrist endeleg prosjektoppgåve sundag 6te mai i Fronter. Den endelege oppgåva skal innehalda alt som de har gjort til og med innlevering 3 med rettingar og oppdateringar. Det er den endelege innleveringa som dannar grunnlag for eksamen, og de står fritt til å gjera det beste som de kan uavhengig av kva de har gjort tidlegare. Dersom de har gjort ein god jobb til no og er heilt og fullt i rute, so kan de levera det same som til innlevering 3 og fokusera på andre fag resten av semesteret.

Nota Bene

Når eg bruker foilar, vert desse lagt ut nedanfor (under programmet veke for veke). Eg vil ofte ikkje bruka foilar, eller foilane er ufullstendige og vert supplerte med andre hjelpemiddel som ikkje alltid kan publiserast. Som hovudregel må de møta på førelesingane for å få med dykk stoffet.

Oppgåver

Som del av kurset skal ein gjera éin stor programmeringsoppgåve som skal leverast etter påske og som dannar grunnlag for munnleg eksamen. I tillegg skal ein gjera tre delinnleveringar, i veke 5-6, 9-10 og 13. Alle delinnleveringar inngår i hovudprosjektet. For å få levera inn hovudprosjektet skal alle delinnleveringane vera godkjende, og godkjenning skjer i øvingstimane.

  1. Delinnleveringane skal leverast i Fronter.
  2. Ein må møta i fyrste øvingstime etter fristen og personleg visa fram løysinga og ta imot tilbakemelding.
  3. Dersom ein unntaksvis er hindra frå å koma i øvingstimen for å få oppgåva godkjend, må ein ta kontakt so snart som råd, og normalt før timen, for å gjera ei alternativ avtale.
  4. Dersom ei øving vert levert i tide men ikkje godkjend, får ein ein ny sjanse til å retta manglane og levera på nytt.
  5. Dei som ikkje leverer og viser fram oppgåva i tide, får ikkje lov til å levera den endelege prosjektoppgåva og kan dermed heller ikkje ta eksamen.

Andre sider

Nytt

Eksamensform

Eksamen vil som i haust starta med ein kort presentasjon av prosjektoppgåva. Det er venta at de har god kjennskap til dei teknikkane som de har brukt og som de skulle ha brukt, inkl. teoriegrunnlaget for dei. Dvs.

Objektorientert design
med bruk av arv og polymorfi; fokus på low coupling high cohesion.
GUI
hendingsstyrt programmering, ActionListener, generell oppbygging og struktur.
Filhandsaming
bruk av straumar, parsing av tekstfiler, serialiseringsgrensesnittet
Feil og unntak
unntaksmekanismen i Java, alternativ til unntak

I samband med dette er heile Del 2 av boka Objects First pensum. Det aller meste i boka kan knyttast til ting som de har gjort, skulle ha gjort eller har gjort feil i prosjektet. Det å visa til feil som de har lært av er positivt, dersom lærdomen er god.

I tillegg har me ein del pensum frå Data structures and algorithms, som eg òg har gått gjennom på førelesing. Omgrep som de skal kunna relativt godt er abstrakt datatype, array, list, linked list, queue og stack. Rekursjon, både på datatypar og funksjonar, er pensum. De treng ikkje å kunna skriva rekursive funksjonar, men skal kjenna prinsippa med grunnfall og rekursivt fall og kva som skjer om det eine manglar. De bør òg vita om heap, tree, map og hashmap. Det er greitt å leggja vekt på føremonar og ulemper samt bruksområde for dei ulike datatypane.

Eksamensplan

Timeplan for eksamen er lagt ut.

Innlevering 3 ( Fri 30 Mar 2012 09:04:09 UTC )

På grunn av sjukdom kan eg ikkje handheva godkjenning av innlevering 3. Alle vert difor rekna som godkjent. Resten av gruppeøvingane vert brukte til å hjelpa deg som bed om det. Dvs. at om du kjenner at du treng tilbakemelding, so kom for all del og bed om det.

Åtvaring! Serialisering av fleire objekt ( Fri 30 Mar 2012 09:04:09 UTC )

Eg ser at mange serialiserer både spelarregisteret og spelrunderegisteret. Det er bra.

Der er tre måtar å gjera det på. Og to av dei er feil. Feila kan vera vanskelege å oppdaga ved testing.

  1. Lagra dei to objekta i kvar si fil.
  2. Lagra kvart object med eit eige kall til writeObject() men i den same fila.
  3. Laga eit tredje objekt som inneheld dei to som me er interessert i, og so serialisera dette tredje holding-objektet.

Utfordringa er objekt (t.d. Player) som vert brukte både i spelarregisteret og i spelrunderegisteret. Serialiseringa lagrar alle objekt som vert brukte. Løysing 1-2 vil difor lagra kvar spelar to gongar, ein gong for spelarregisteret og ein gong som del av kupongane. Når me lastar inn igjen får me kvar spelar to gongar, som to ulike objekt.

Dei aller fleste testar vil visa at dette fungerer. Men dersom du lastar inn igjen objekta og går via spelarregisteret for å endra adressa til ein spelar, so vil denne adresseendringa ikkje synest i det spelarobjektet som kupongane har.

Den einaste løysinga som fungerer når objekta er avhengige av kvarandre er nr. 3. Då vil serialiseringsmekanismen lagra kvar objekt éin gong, uavhengig av kor mange referansar objektet har.

GUI-verktyet i NetBeans ( Tue 14 Feb 2012 08:41:27 UTC)

Eit gjennomgangsspørsmål er om ein kan bruka det grafiske verktyet i NetBeans til å laga GUI. Svaret er både òg.

De er nødde til å kunna forklara hovuddraga i koden dykkar, spesielt dei konstruksjonane som er dekte i førelesingane og dei som er heilt sentrale i løysinga av oppgåva. Difor kan det vera lurt å starta med å koda GUI for hand.

Det er lurt å bruka det grafiske verktyet for å få ein god layout når de har mange komponentar i eit vindauga. Det er det vanskeleg å gjera for hand, og det grafiske verktyet er nyttig.

Ein student fortalde meg at det var mykje enklare å forstå det grafiske GUI-et når han hadde freista å skriva noko av GUI-en for hand.

Tips: når noko går galt ( Tue 14 Feb 2012 08:33:45 UTC )

Eg har talt med fleire der me har kome borti feilsituasjonar, og de ynskjer å avslutta programmet med ei feilmelding. Den beste måten å gjera dette på er fylgjande:

Me vil koma tilbake til dette, m.a. dei ulike underklassene til Exception, men formen over er fin ved prototyping og testing. Test han for å sjå kva som skjer.

De kan t.d. bruka når de overstyrer ein metode i ein underklasse, der argumentet skal vera ein subtype av typen brukt i superklassa. Til dømes slik:

   public void foobar( Row r ) {
     if ( ! r instanceof LottoRow )  {
        throw new Exception( "Programming error" ) ;
     } 
     LottoRow lr = (LottoRow) r ;
   }

Innlevering 1 ( Thu 9 Feb 2012 15:07:40 UTC )

Eg har no sett på circa 35 utav 55 innleverte oppåver. Om lag halvparten har gjort godt arbeid, som regel med litt småplukk. Den andre halvparten slit stadig med det grunnleggjande designet (med 1-2 unntak som har godt design men knapt starta på kodinga).

Dei som ikkje fekk godkjend har fått to veker på å verta ferdig. Eg har lagt ut nokre designtips som alle som ikkje har godkjend og mange som har godkjend, bør lesa.

Dei som ikkje har godkjend, og som veit at dei ikkje har kontroll på designet sitt, bør jobba vidare og bruka tipsa som eg har lagt ut. Eg har høve til å møta folk som treng hjelp på måndag etter 13.00 og tysdag etter 14.00.

Arbeidslivsdagen 1. februar ( Fri 27 Jan 2012 08:11:42 UTC )

Gruppeøvingane vil gå som planlagd 1. februar, til tross for arbeidslivsdagen. Det er derimot lov å gå inn og ut av øvinga, og få med seg evt. delar av arbeidslivsdagen innimellom. Øvingane går frå 12-16; dei fyrste to timane er eigentleg for automasjon og dei siste to for data, men det er ofte ledig plass slik at de kan bruka alle fire timane.

Grunnen til at øvinga går uansett er at alternativet vore å gi de knapp tid til innleveringane. Sjølv om ei frist kunne vore utsett ville det berre forskyva problemet til neste frist.

Oppmodinga om å sjekka ut arbeidslivsdagsprogrammet og få med seg interessante punkt står ved lag.

Nye sider ( Tue 24 Jan 2012 08:11:09 UTC )

Merk at eg har lagt ut eit kort oversyn over spelereglar, for dei som ikkje kjenner spela.

De skal ikkje vera redde for å forenkla reglane og ignorera detaljar i spela. Dersom de er flinke til å få til loose coupling og high cohesion so vil det vera lett å leggja til detaljar seinare. Difor skal de fokusera på god objektdesign for å få med hovudstrukturen i spela. Alle detaljar de tek med er positivt, men det kan ikkje erstatta god design.


Hans Georg / hasc@hials.no