Algoritmer och datastrukturer TF3 Sy
samt
Algoritmer och datastrukturer med objektorienterad programmering




Obligatorisk inlämningsuppgift nummer 3,
Projekt


Uppgifter

Välj en av uppgifterna eller föreslå en egen uppgift.

  1. Egen uppgift

    Föreslå själv ett projekt! Din egen fantasi sätter gränserna. Diskutera din uppgift med Fredrik. Skriv därefter en kortfattat spec av uppgiften och lämna in den, innan du påbörjar ditt arbete.

  2. Texthanteringssystem

    Skriv ett antal objekt som filtrerar text och vid denna filtrering gör givna ändringar av texten. Filter att implementera kan vara konvertering lower->upper, upper->lower, search, delete, change. Skriv en basklass filter och låt filtren ärva denna.

  3. Ordbehandlare

    Skriv en enkel radorienterad ordbehandlare. På denna uppgift måste innan du påbörjar programmeringen, skriva en detaljerad beskrivning av ditt projekt, lämna in det till Fredrik och få planen godkänd, innan du påbörjar ditt arbete.

  4. Bignum

    Skriv en bignumklass, som kan hantera godtyckligt stora tal och utföra aritmetiska operationer på dessa.

  5. Spel

    Luffarschack, Othello, ...... Undvik spel med en flashig bildskärmshantering. Diskutera din uppgift med Fredrik. Skriv en kortfattat spec av uppgiften och lämna in den, innan du påbörjar ditt arbete.

  6. Kortspel

    Skriv ett kortspel, exempelvis Black Jack, poker, eller liknande.

  7. Simulering

    Simulera t ex en trafiksitutation, ett kösystem i en bank (prova vilket system, gemensam kö till alla kassor, eller olika köer, som blir effektivast under olika antaganden), djurpopulation. Du kan inte lämna in en "hottad kioskkö" och säga att det är ditt simlueringsprojekt. Naturligtvis kräver även denna uppgift en god självständighet. På denna uppgift måste innan du påbörjar programmeringen, skriva en detaljerad beskrivning av ditt projekt, lämna in det till Fredrik och få planen godkänd, innan du påbörjar ditt arbete.

    Exempel på bra simuleringsuppgifter kan vara

    Mindre bra projekt är en (rysk) kiosk, eller fyrvägskorsning (en uttjatad uppgift).

  8. Maze-Walking Robot

    A maze can be built as a 2-dimensional array of which some cells are occupied by obstructions. The obstructions can be used to build walls and rooms. You will want to be able to create a new maze, place and remove obstructions, and inquire as to the presence of an obstruction in a cell. All cells outside of the maze boundary are treated as obstructed. (You will want to be able to write a maze to a file and read it back in, since mazes are tedious to build.) One cell is marked as the goal. A robot occupies a cell of the maze and has as its purpose to seek the goal by moving to it without passing through any obstructions. The robot does this by moving to any adjacent cell (north, south, east, west) that is not blocked by an obstruction. The robot will need memory to keep track of the cells already visited, the path that has been followed, and points at which alternative paths could be tried if it needs to back up.

  9. Mapping/Seeking Robot

    A variation on the above is to create a robot whose first job is to traverse every reachable cell in the maze and create a map of the maze as it goes. In its seeker phase, the robot uses the map to find the goal as efficiently as possible from its original position.

  10. Huffman Encoding/Decoding

    Data compression is an important issue in both data communication and data storage. One common method of compression is Huffman encoding. Rather than using fixed number of bits per data unit, Huffman encoding uses fewer bits for data frequently occurring units and a larger number of bits for less frequent data units. The result should be a more compact representation of the data. If you find this to be an interesting project, talk to Fredrik for more information.

    Några goda råd

    När du arbetar med projektet, skissa ingående på klashierkier, väsentliga metoder etc. Diskutera gärna igenom din ambitionsnivå på uppgiften och din klasshierarki med handledaren innan du börjar koda.

    Frågor?
    Fråga!


    Redovisning

    Redovisningen består av
    1. Ifylld försättssida
    2. lämpligt kommenterad programlistning
    3. en beskrivning av och motiv för valda algoritmer, klasser klasshierkier och andra datastrukturer.
    4. ett körexempel
    5. uppgift om var den exekverbara filen finns tillgänglig för läsning. Se till att ge läsrättigheter åt gruppen övriga.
    Uppgiftslösningen ska i sin helhet spegla en god programmeringssed för C++ och tillämpa klassbegreppet på ett meningsfyllt sätt.

    Uppgiften får lösas individuellt eller i grupper om två. Om två personer arbetar tillsammans, ska båda aktivt delta i hela utvecklingsarbetet. En ren arbetsdelning, exempelvis programmering mot dokumentation är inte tillåtet.

    För handledning på denna uppgift hänvisas till Datortekniks jourhavande handledare eller Fredriks handledningstider


    Uppgifterna lämnas in enligt anvisningarna i kursplanen, senast den 25 Obs! mars kl 8.00.


    Fredrik Larsson <fredrikl@DoCS.UU.SE>
    Anders Berglund <Anders.Berglund@DoCS.UU.SE>
    Last modified: Fri Mar 6 23:25:53 MET 1998