Warning! This is the 2012 course's website! You probably want the current course website.

Laboration 1

Introduktionen består av ett antal mindre uppgifter som behandlar olika moment från kurser i Java-programmering. Laborationsuppgifterna skall implementeras och lämnas in via Fire-systemet.

Förutom labuppgifterna så bör ni göra så många övningar som möjligt! Bäst är att göra några övningar innan ni börjar med laborationsuppgifterna. En del är lätta, andra är svårare och tar mer tid att göra. Upptäcker ni att det finns luckor i era kunskaper, se till att fylla dessa så snart som möjligt. Läs själva och fråga om det som är svårt! Erfarenheten visar att luckor tenderar att vidga sig snarare än att automatiskt fyllas igen.

Laborationsuppgifter

1. Fibonacci-serien är 0, 1, 1, 2, 3, 5, 8, 13, 21, …, och kan beräknas med följande rekursiva definition:

       fib(0) = 0
       fib(1) = 1
       fib(n) = fib(n-1) + fib(n-2)
   

   Om man definierar Fibonacci-funktionen på enklaste sätt så blir funktionen dubbelrekursiv. Detta ger upphov till många "onödiga" beräkningar och därmed en onödigt ineffektiv implementering. Implementerar man funktionen i ett imperativt språk, gör man i allmänhet en iterativ lösning, som blir effektivare.

   Implementera Fibonacci-funktionen dubbelrekursivt och iterativt och mät tidsåtgången för att beräkna funktionen på ett antal allt större argument. Skriv en enkel tabell som visar exekveringstiden relativt argumentets storlek för de två fallen. (För att få tillförlitligare värden, kan man exekvera varje argument 10 ggr och ta det lägsta värdet.)

   Tidsmätningen är inte speciellt noga, det som är intressant är skillnaden i tid för olika argument. Det räcker att använda metoden: System.currentTimeMillis som ger den aktuella tiden i millisekunder. Början på tabellen bör se ut:

       n   fib n   tid iterativ   tid rekursiv
   
       0     0         0.00 s         0.00 s
       1     1         0.00 s         0.00 s
       ...
   

   Gör tabellen tillräckligt lång, så att värdena börjar växa ordentligt (för den rekursiva varianten). Går det att säga något om komplexiteten?

2. Skriv ett program som kan läsa en text från en fil och göra frekvensanalys på de bokstäver (inklusive 'å', 'ä' och 'ö') som förekommer. För att lagra information, får ni inte använda någon datastruktur i util-paketet (förutom Scanner), utan endast använda variabler och fält, dvs array. Utdata skall ges i form av en tabell:

       bokstav  antal   frekvens
   
       a         112       9.33%
       b          15       1.25%
       ...
   

   Frekvensen anges i % och endast bokstäver som förekommer minst 1 gång tas med.

   Texter på olika språk har en karaktäristisk frekvensfördelning. Se om ni kan se någon skillnad på engelsk respektive svensk text genom att testa med någon lite större lämplig text på vardera språket.

3. Implementera en klass som kan lagra en sekvens av strängar. För att representera sekvensen ska ni använda ett fält som utökas automatiskt vid behov, ungefär som i implementationen av ArrayList i kursboken, avsnitt 2.3. Klassen skall innehålla följande metoder:

   • addFirst(s): lägg till en sträng först i sekvensen
   • nonEmpty(): avgör om det finns några element
   • getFirst(): returnera det första elementet
   • removeFirst(): ta bort det första elementet
   • contains(s): avgör om en sträng finns i sekvensen
   • toString(): förvandla hela listan till en sträng, med utseende ungefär som: "['ada', 'bcpl', 'c']"

   Utöka klassen, dvs gör en subklass, så att den också innehåller en "markerad" position i sekvensen tillsammans med följande metoder:

   • markFirst(): sätt positionen på första elementet (om det finns)
   • isMarked(): avgöra om positionen är satt (dvs, om något element är markerat)
   • addAfterMarked(s): lägg till ett element efter det markerade elementet
   • getMarked(): returnera det markerade elementet
   • moveMarker(p): flytta den markerade positionen ett antal steg framåt eller bakåt
   • search(s): sök efter en sträng och sätt P till strängens position om den finns i sekvensen
   • Dessutom skall metoden toString() märka ut positionen genom att sätta en stjärna vid det aktuella elementet. Ungefär såhär: "['ada', 'bcpl'*, 'c']"
   • Fundera på hur ni ska representera att inget element är markerat. Och fundera noggrannt på randvillkor, dvs. vad som bör hända om något går fel: t.ex., vad bör moveMarker() göra om man flyttar positionen för långt?

   Tänk på att ge klasserna vettiga namn! Och glöm inte att dokumentera varje metod!