Göm menyn

TDDC74 Programmering: Abstraktion och modellering

Project

VT 2013

På den här sidan finns information om projektarbetet som utförs under andra halvan av kursen. Följande behandlas:

Allmänna instruktioner

Under andra halvan av kursen ska studenter i grupper om två personer tillsammans genomföra ett projekt i Racket. Exempel på projekt kan vara en implementation av Othello eller Tetris. En mer utförlig lista av projekt finns längre ned på sidan (här).

I samband med lektionerna under vecka 12 (onsdag 21/3-2012 och torsdag 22/3-2012) kommer alla assistenter ge en kort presentation av samtliga projekt. Då finns det även möjlighet att ställa initiala frågor om projektet. Efter lektionen är det fritt fram att välja projekt, bilda projektgrupper (om två personer i varje grupp) och anmäla sig i webreg. Till skillnad från labbserien är det tillåtet att bilda labbgrupper med studenter i andra klasser.

Notera: sista anmälningsdag i webreg är 28/3-2012. Utebliven uppskrivning i webreg efter detta datum tolkas som att projekt ej kommer att genomföras. Skriv därför in er i webreg så fort som möjligt!

https://www.ida.liu.se/webreg/TDDC74-2013/PRA1

I första hand ska projektet genomföras i grupper om två personer (vi vet från erfarenhet att detta funkar bäst). Jalal tar beslut för grupper som önskar vara fler än två personer. Skicka därför ett mail till Jalal med en detaljerad projektbeskrivning och tänkt arbetsfördelning om ett undantag önskas.

Breddlektioner

På måndag 26/3-2012 mellan kl 10-12 hålls ett antal breddlektioner, där varje laborationsassistent ger en djupare bakgrund till något av de olika projektvalen. Vilken lektionssal som gäller beror således på vilket projekt ni valt. Gå alltså till den lektionssal i listan nedan, som behandlar det projekt ni vill genomföra:

  • Optimering och sökning i P18 (handledare: Anders Leffler, Anders Wirén)
  • Interpretatorer/expertsystem i S18 (handledare: Martin Arne, Jonas Wallgren)
  • Brädspel/Othello/animerade spel i U15 (handledare: Mikael Silvén, Peter Hafid)
  • Animerade spel/äventyrsspel i U4 (handledare: Peter, Pierre)
Tanken med dessa lektioner är att ge er mer information om exempelvis lämpliga algoritmer eller uppbyggnad av era projekt. Det är därför väldigt lämpligt att gå dessa lektioner.

Projektspecifikation

Efter lektionen ska det valda projektet konkretiseras genom att det skrivs ned i form av en projektspecifikation. Specifikationen ska beskriva det valda projektet, hur det ska genomföras, vad det ska innehålla, med mera. För att underlätta skrivandet av denna finns en OpenOffice-mall längre ned på sidan (här). Mallen är tämligen "pratig" och vad som efterfrågas bör te sig uppenbart. Projektspecifikationen kommer att delas ut i samband med lektioner och föreläsningar samt diskuteras ytterligare på dessa. Därför är det rekommenderat att delta på dessa tillfällen. Strax under mallen finns även ett dokument med generella riktlinjer för de olika betygsstegen. Titta gärna på dessa.

En första version av projektspecifikationen ska lämnas in i en låda utanför Jalals kontor (karta). Sista inlämningsdatum är 28/3-2012 och inlämningen sker på precis samma sätt som under labbserien, alltså i ett ifyllt IDA-omslag. Projektspecifikationer kommer sedan delas mellan alla assistenter för att göra arbetsbördan så jämn som möjligt (vi vet ju inte hur många som kommer välja respektive projekt och vi vill givetvis att alla ska få möjlighet att välja projekt fritt). Dagen efter kommer samtliga grupper få ett mail från sin tilldelade handledare med ytterligare instruktioner. Fredag 30/3-2012 återlämnas projektspecifikationen med kommentarer från er handledare. Vid eventuell komplettering så ska projektspecifikationen kompletteras och vara godkänd senast måndag 16/4-2012.

Mittavstämning

Efter att ungefär halva projekttiden har gått kommer en mittavstämning att hållas. I samband med denna kommer ni bli ombedda att maila in den kod som ni hittills producerat och även boka in en tid för själva mittavstämningen. Vid mötet kommer er handledare att ge kommenterar på koden samt svara på frågor. Använd tiden för att bolla idéer få lite extra hjälp på vägen. Exakt datum och tid för mittavstämning görs upp mer respektive handledare, men en generell riktlinje är runt 2/5-2012.

Demonstration/slutredovisning

Vid slutet av projektet ska slutprodukten visas upp för er handledare. Detta görs i en SU-sal, antingen på en av de tunna Solaris-klienterna eller på egen dator. Projektet ska vara vid redovisningen vara färdigt enligt de krav ni ställt upp och det ska vara fullt körbart (inga större buggar). Slutredovisningen kommer att äga rum onsdag 16/5-2012 (mer information skickas ut per mail när redovisningen närmar sig) medan den slutgiltiga inlämmningen 24/5-2012. Detta betyder alltså att ni har ytterligare ett par dagar på er att fixa småsaker (indentering, kommentarer, etc.) samt uppdatera och skriva klart projektspecifikationen. Till exempel ska ni skriva en liten manual till ert projekt samt utvärdera projektet. Inlämningens förfarande får ni av er handledare.

Viktiga datum

Nedan följer en sammanfattad lista med alla viktig datum samt vad som gäller för respektive datum. Allt som står i texten ovan sammanfattas här (och det kan vara bra att titta förbi här om ni är osäkra på något).

  • 21/3 & 22/2 - Lektioner med bland annat initial information om projekten
  • 23/3 - Föreläsning med diverse tips till projektet
  • 26/3 - Breddlektioner om de olika projekten
  • 28/3 - Sista dagen att anmäla sig i webreg och deadline för projektspecifikationen
  • 29/3 - Ni får mail från er tilldelade handledare
  • 30/3 - Respons lämnas på er projektspecifikation från er handledare
  • 16/4 - Projektspecifikationen godkänd (ev. kompletterad)
  • ~2/5 - Mittavstämning mer er handledare
  • 16/5 - Slutredovisning
  • 24/5 - Sista dagen att lämna in projektet!

Projektresurser

Betygskriterier

Projektet graderas med antingen en 3:a, 4: eller 5:a vid slutförande. Notera att det inte är storleken på projektet som ger ett visst betyg. Mycket fokus ligger på bra och välstrukturerad kod som är enkel att utöka, ändra och förstå. Lägg därför mycket fokus på att dela upp era projekt i olika moduler, som är lätta att förstå och implementera. Ett tips kan vara att försöka tänka inför framtiden: "om jag gör X så blir det lättare att göra Y senare". Till exempel kan det vara lämpligt att använda variabler för att bestämma en spelplans storlek, eftersom det då räcker med att ändra dessa om storleken önskas ändras i framtiden.

Mer generella riktlinjer hittar ni här.

Projektgrupper

Alla projektgrupper finns i Webreg: https://www.ida.liu.se/webreg/TDDC74-2013/PRA1.

Projektval

Nedan följer ett antal exempel på några olika projekt som är lämpliga att genomföra i kursen. Beskrivningen till (en del av) de olika exemplen är på engelska av historiska skäl och har ej blivit översatta till svenska ännu. Håll till godo...

Project selection

You can either select one of the projects that we propose below or create your own project completely. In any case, you need to consult the supervisor which is interested in the kinds of projects you like to work with. Sooner or later you need some supervision and it is important that there is an agreement on what kind of projects the teachers in the course can supervise.

Animated games

Supervisors:

Pierre Östlund
Mikael Silvén
Peter Larsson-Green

This project is meant for students with a passion for small simple games. The main focus is animated graphics and interaction. These games are supposed to interact with the user.

Examples of games that fits this description are:
  • Tetris
  • Breakout
  • Pac-Man
  • Frozen Bubble

Board games

Supervisors:

Mikael Silvén
Peter Hafid

The objective of this project is to develop a game that is turn-based, the primary focus is on implementing an existing board game. Another idea would be to take a real-time game and make it turn-based, for example you can make a turn-based racing game.

Depending on the extent of the game implemented, the group may choose to implement it with a text GUI (Graphical User Interface), a network interface and/or a graphical GUI. If your game is suitable, you may also choose to implement an AI (computer opponent) to play against.

Suggestions for board games include:

  • Settlers
  • Carcassonne
  • Roborally
  • Battlecars
  • Power Grid
  • Monopoly
  • Tsuro
  • Ticket to ride
  • Elfenland

For a list of more games you could choose to implement, please visit boardgamegeek.com or http://brettspielwelt.de/.

Two-player games: Othello, Chess

Supervisors:

Mikael Silvén
Peter Hafid

The purpous of this project is to implement a two-player game, i.e. an othello game with a computer player. Othello, chess and go belong to a family of games for two players where both players have perfect information (can see the entire state of the game) and there can be only one winner.

There exist a number of algorithms for playing in games like these. A good start is the Minimax algorithm and the alpha-beta cut-off.

When implementing Othello, you will have access to a dedicated Othello GUI library so little or no GUI programming will be required.

Adventure games

Supervisors:

Pierre Östlund
Peter Larsson-Green

In lab4 you began work on a small text based adventure game. Adventure games have been around for quite a long time and are still as popular as ever.

In this project you get a chance to improve or rewrite your game from lab4. The minimum requirement is that the project game is bigger than the lab4 game. You should also implement at least one additional feature. Examples of additional features are:

  • Dynamic worlds
    Make it possible to write the game world in some representation that your program can read so that the worlds can be changed without changing the program code. Prehaps even implement a way of extending the world during the play
  • Graphical interface
    Implement some simple graphics for your game that shows the world the user is playing in

The text editor Emacs actually has an implementation of a text based adventure you could look at for inspiration. To start it; start emacs, press M-x (hold the meta-button and press x), type "dunnet" and press return.

Computer languages

Supervisors:

Jonas Wallgren
Martin Arne

In this project the group is supposed to implement a subset of another programming language. This could be solved in two ways; either by an interpreter or by a compiler.

An interpretor is a program that reads the source-code and then carries out the instructions right away. Much like the REPL in DrScheme.

A compiler on the other hand is a program that translates the input program from one programming language to another, and then hands over execution of the translated code to another system. Commonly code is translated into machine code that the computer then executes, but in this case you could translate your code to scheme.

Another idea for this project could be to implement extensions to scheme. For example some of the new suggestions from R6RS.

Requirements

The language you implement should contain variables, assignments, procedures and control structures (such as if and loops). It would also be nice for the language to have procedures for input and output.

In your design specification for the project you should provide a description of the syntax of the language. Prefably in form of a Context free grammar.

To get you started chapter 4 in SICP discusses the implementation of a scheme interpretor in scheme, this could be a good idea to read.

Example description for Graphics Language

Mathematical problems/puzzles, Algoritmic problems

Supervisors:

Anders Märak Leffler
Anders Wirén

In this project you are expected to find some maths or CS problem, which is suitable for handling with Scheme. There may also be puzzles and coding problems.

Scheme is appropriate to do symbolic computation where we have a representation of the formula and do operations on it. Derivation is easy to do, but simplification may be harder. There is an algorithm for doing symbolic integration (Risch algorithm) and so on. You may want to solve equations or constraints in a symbolic way.

There may be puzzles, like Sudoku, where it is quite simple to set up all constraints which must hold, but harder to compute it in an efficient way to find solutions. Or, you may do a sudoku-generator which from constraints (number of given slots etc.) can generate a unique sudoku.

From a discrete mathematics course you may have seen algorithms from coding theory.

Sample projects:

  • Find the shortest road in a map, lika a GPS in a car. Road data for Sweden is available to work with. Applied graph theory, optimization and algorithms.
  • Zero-order-logical resolver. Converting between normal forms and checking the validity of a statement. Eg creating a program that can answer if "(p->q) and p implies q". (Applications of more refined versions include planning for intelligent agents (is the following implication valid? "{the door is locked; if I have a key, then I can open the door; if I can reach the key, then I have the key; I can reach the key} -> I can open the door").)
  • Programming language. Implement an interpreter for a simple imperative programming language in Scheme.

Medicinska beslutsstödssystem

Handledare:

Jonas Wallgren
Martin Arne

Beskrivning följer här.

Presentation/visualisering av hälsodata

Handledare:

Jonas Wallgren
Martin Arne

Beskrivning följer här.

Andra projekt med medicinsk inriktning

Handledare:

Jonas Wallgren
Martin Arne

Det är även möjligt att ni kan skapa egna projekt med en medicinsk teknik inriktning. Kanske kan ett spel eller äventyrsspel organsieras om med ett lärande moment. Tänk dig ett äventyrsspel där frågpr och uppgifter att utföra kräver eller kommer att ge dig medicin-kunskap. Ett pedagogiskt spel att kunna ha under sin utbildning.

Other projects

We may allow other projects as well, but we must decide if it is an appropriate project for this course and that we can supervise it.

If you want a project of your own you should write a mail to the examiner Jalal Maleki and desribe what you want to do and how you plan to implement it.

Övriga resurser

External links


Sidansvarig: Anders Märak Leffler
Senast uppdaterad: 2012-03-29