> Home

> Lectures

> Projects

Here is a list of proposed projects. Some of them may seem trivial; however, there are aspects that require quite a bit of effort in all of them.

The names written in gray will show tentative assignments. As soon as an assignment is final, the name of the student will be written normally.

The list is currently dynamic, but by 1st of April I will freeze it.

If you can come up with similar proposals, please do not hesitate to contact me.

You can consult any bibliographical sources, you can use (some) public domain code, you can discuss, but the written work must be your own.

You will be required to deliver some artefacts (documents, code, etc.) at dates that will be specified. Please try to respect the deadlines: There will be penalties for delays.

1. Algorithms

1.1. Visualization of sorting algorithms for real values. (Clemens Hofstadler) The software shall offer a graphical representation of in-place sorting algorithms. The array of real numbers to be sorted shall be read from a file. The user shall be able to choose one of some available algorithms. The array to be sorted shall be displayed as a stack of line segments with lengths proportional to the values in the array. The number of displayed algorithms shall be chosen by the user. These algorithms shall run in parallel.

2. Data structures

2.1. Visualization of binary search trees. (Mario Gobrial) Creation and traversal. The program shall read a list of values (from a file, or given by user) and create a binary search tree with these values. The tree shall be visualized on a graphical surface. The user shall have the possibility to give a value, and the value shall be searched in the tree. The path connecting the root with the element that corresponds to the searched value shall be marked (colored). The nodes traversed in order to display the sorted values will be emphasized (blinking or colored).

3. Graph Theory

3.1. Graphical representation of directed graphs. The graphs shall be read from files which shall also contain the position in the plane of each node (as a pair of coordinates). Sources (nodes with no incoming arcs) and sinks (nodes with no outgoing arcs) shall be marked. The arcs shall be drawn as straight-line arrows.

3.2. Finding connections. The program reads an undirected labelled graph. The user is expected to choose two labels, and the program detects if there is a route in the graph between the nodes with those labels. The Dijkstra algorithm shall be used, and its evolution shall be displayed.

3.3. Finding routes. The program reads a simple planar map given as straight-line segments with topographic coordinates: Each segment is defined as four real numbers given on the same line of text, separated with spaces. The program draws the map on a graphic surface. If the users clicks on a segment, that segment shall be marked (e.g. displayed with a different colour). The next click on a segment shall leads to the program computing the shortest route in the map, between the previously clicked segment and the currently clicked segment; the program shall mark all segments on the computed route, and shall unmarked all other segments. If the user clicks far from any segment, the currently marked segment(s) shall be unmarked.

4. Applied maths

4.1. Arithmetic of arbitrarily big integer numbers. Main operations (addition, multiplication, division, greatest common divisor, factorization) shall be implemented. The user shall give two (long - up to 200 digits) integers, and the software shall allow her to request any of these operations.

4.2. Visualization of Newton method for approximate computation of roots of general equations. (Michael Winkler) A predefined set of equations shall be used. The user shall select the equation and the initial approximation. The program shall iteratively compute approximations of a solution, and the progress shall be displayed in graphical form.

5. Graphics, Visualization

5.1. Drawing the Mandelbrot set. The program shall show a window in which the Mandelbrot set (or a part of it) shall be drawn. The user shall have the possibility to select a rectangle from the already drawn set: The program shall perform a zoom-in, by re-computing the set in that rectangle.

5.2. Visualization of a surface. A parallel (perspective) projection of a surface shall be drawn. The user shall chose the formula of the surface from a set of predefined formulas. Examples: sin(x+y), x/(y*y+1). The x– and y–intervals shall also be given by the user.

5.3. Simple graphical editor.

5.4. Renderer. The program shall read a graphical scene from an XML file whose tags represent graphical objects and shall offer a visualization of the scene. The tags should agree with the SVG schema.

5.5. Image filters. The program shall read an image and apply a filter, selected from a predefined list. Recommended filters: blur, sharpen, edge detection.

5.6. Wireframe rendering of geometries. The program shall read a set of simple 3D geometrical objects (line segments, triangles, polygons) given by sets of points and shall visualize them in wireframe mode (perspective view). The user shall give the viewpoint and the line of sight. It shall be possible for the user to change these parameters, and the view shall change accordingly.

5.7. Bézier curve for a set of points set by the user clicking on a canvas. The Bézier curve shall be computed and displayed dynamically on the same surface on which the user clicks. The number of points that can be set is limited to a reasonable number. For computing the curves, one can use e.g. the de Casteljau algorithm.

5.8. Visualization of sample data. (Michael Rußmann) A set of integer, positive numbers is read from a file and its values drawn on a graphical surface. The user shall have the possibility to visualize, on the same surface, any (or all) of the following mathematical objects: the interpolating polynomial; an approximating polynomial, whose degree is given by the user, computed with the least squares method; the Bézier curve defined by these numbers (as abscissae, the index of each read value shall be used). For computing the Bézier curve, one can use e.g. the de Casteljau algorithm.

5.9. Mystify. The program shall show a window with a canvas where an animated drawing similar to what you get by choosing "Mystify" (with polygonal lines, not Bezier curves) as screen saver can be seen. The user can choose the number of lines, and the number of points on any line. There shall be only one set of lines.

6. Computational geometry

6.1. Convex hull for a set of points set by user clicking on a canvas. (Stefan Tyoler) The convex hull shall be computed and displayed dynamically on the same surface on which the user clicks.

6.2. Rectangular hull. Each pair of mouse-clicks defines oposite corners of a rectangle. The user defines thus a set of rectangles. The program computes the external rectangular contour of this set. Each new rectangle is displayed with another (random) color. After a new rectangle is inserted, the contour is recomputed and displayed. It shall be possible to remove the last inserted rectangle; the rectangular hull shall be recomputed.

6.3. Connecting points in a scene with rectangles. (Lukas Weissinger) The program shall read from a file the coordinates of a set of rectangles with horizontal / vertical edges, and the coordinates of two points. The program shall compute a (short) path, made with horizontal or vertical line segments, between the two points, a path that avoids the rectangles.

6.4. Computation of intersections in a set of line segments in plane. The user shall click on the program’s graphical surface; pairs of clicks shall define line segments. The intersections of these segments shall be marked.

7. Simulation

7.1. Simulation of a coffee machine.

7.2. Packaging. The program simulates the work of a packaging installation. It generates weights of objects randomly, following a normal distribution whose parameters can be set via the user interface. After a certain number of objects’ weights has been generated, it creates packets by picking a subset so that the sum of chosen weights exceeds a certain value, but with a minimum amount. The whole process is repeated a (big) number of times. The final distribution of the packets shall be drawn as a histogram.

7.3. Simulation of a population: Conway's Game of Life. (Simon Breneis) See, e.g., http://en.wikipedia.org/wiki/Conway%27s_Game_of_Life. It shall be possible that the user changes the evolution rules.

8. Utils

8.1. Simple database system for personal library. The information shall be stored in a text file. The user shall be able to browse this file and insert new information.

8.2. Calendar. (Patryk Grabski) The program shall visualize a calendar of the current month (the use of Calendar controls provided by various packages is not accepted). It shall be possible to change the displayed month. By double-click on a respective day it shall be possible to add appointments at certain times. If one day contains appointments, this shall be indicated in the calendar.

8.3. Simple art database. The program shall read from a file a list of painters and shall expose their names to the user. A click on a painter name shall show a set of thumbnails of his paintings, with titles. A click on a painting’s thumbnail shall display that painting in normal size.

8.4. Folder synchronisation. The program shall work with two directories, the source and the target. All files in these directories will be visualized, in two lists. Every file in the source directory that is new or has been more recently modified than its counterpart in the target directory can be copied into the latter. These files shall be emphasized. The user shall be able to select or deselect any file, or all files, from the source directory. The selected files will be copied to the target directory at a button click.

8.5. Multiple choice tests. (Stephan Moser) A set of questions will be read from a file, together with a set of possible answert to each question, and the indication of the correct answer. The program shall offer the possiblity of a training test: A randomly generated subset (whose size can be configured) of questions shall be presented to the user, and their possible answers. The user shall be able to selected an answer. After the user has chosen, the next question shall be displayed. Upon termination of all questions in the subset, the score shall be shown, as the number of correct answers.

8.6. Encrypting a text. The program shall offer an editing area where the user can enter text. This text shall be saved in a file, encrypted, using some encryption algorithm of your choice. The encryption shall need some key, which the user must give in order to be able to decrypt the content of the file.

8.7. Recipe book. (Andrea Huber) The programm shall maintain a collection of recipes classified first after the meal type (breakfast, lunch, etc.) and then after main ingredient (beef, fish, kale, etc.). The user shall select a meal type and shall be offered the list of all main ingredients. Selecting a main ingredient shall bring up the list of stored recipes (title and an image). After clicking an element in this list, the selected recipe shall be displayed (ingredients with quantities, preparation, possibly images).

9. Games

9.1. Hangman. (Sophia Schwendtner) See http://www.manythings.org/c/hm-geography.cgi for an example. The list of words shall be read from a file.

9.2. Sudoku. (Thomas Losbichler) The initial configuration of digits on the 9x9 table shall be given (read from a file or introduced by the user). The program shall compute a solution: shall fill the remaining cells with the correct digits.

9.3. Mastermind. (Mathias Lasselsberger) The user plays against the computer for finding out the color configuration of a group of four colored items. (For the computer, a brute force algorithm shall suffice.) See http://en.wikipedia.org/wiki/Mastermind_%28board_game%29.

9.4. Wordzap. The user plays against the program to find words using a set of eight randomly generated letters. The words should not exceed 5 letters. For a list of words, see Corncob web page. For Wordzap, see http://wordzap.com/features.html.

9.5. Memory blocks. (Michael Kritzinger) An even number of tiles have one face painted with some drawings or images. Pairs of them have the same image. At the beginning al tiles have the drawing hidden. The user clicks on two of them, and by doing that the two tiles turn, showing their drawing. If they have the same drawing, they remain turned, else the next click (on another tile) turns them back, with drawing hidden. The goal is to have them all with the drawing visible.

9.6. Word game. The user is given a set of letters (not necessarily distinct) at the beginning of the game. She can place these letters on a board to create words, horizontally and vertically. Some slots in this board have points associated to them. If a letter of a word is placed in such a slot, the number of points is added to the total score. The goal of the game is to accumulate as many points as possible with the given letters.

9.7. Words finding. A rectangular board is filled with letters. Inside the board words can be detected - sequences of adjacent letters, horizontally or vertically, that have a meaning in the english language. The goal is to detect as many words as possible. Variant: The goal is to detect words so that as many letters as possible are used.

9.8. Minesweeper. (Sophie Hofmanninger) The user should be able to give the size of the table.

9.9. Snake game. (Stephanie Schwaiger) See, e.g., http://www.thepcmanwebsite.com/media/snake/. The game ends when the snake hits the margin of the field or crosses itself.

9.10. Jigsaw. (Edith Karda) The user shall choose an image from a predefined set, and the difficulty of the game. According to the difficulty, the image shall be split into smaller rectangles which shall be scrambled on a canvas. By clicking pairs of rectangles, the user can change their position. The game ends when all rectangles are in their right positions, conform to the initial image.

9.11. Space Invaders. (Sebastian Moharitsch) The game is based on the arcade classic "Space Invaders" on atari. The player can move a small icon showing a canon to the left and the right side of the game's board. Rows and rows of "aliens" are moving from one side to the other, slowly advancing down from the top to the bottom of the screen. If any of the aliens successfully reach the player's canon (bottom), it crashes and the player loses. The player's cannon has an unlimited supply of ammunition, it could fire at the aliens to destroy them. If the player is able to eliminate the aliens, she wins.

9.12. Pong. (Stefan Immler) A simple, single-player variant of the Pong game (see http://en.wikipedia.org/wiki/Pong) shall be implemented. The ball shall be reflected by the left, top, right walls; the player shall defend the bottom wall. The number of lost points shall be displayed, as well as the played time. The game ends after the player loses 11 points. A hall of fame shall be available; the best player is the one with the longest played time.

9.13. Battleship game. (Nico Stimmeder) See, e.g., http://en.wikipedia.org/wiki/Battleship_%28game%29.

9.14. 2048 game. (Lucas Payr) See game's Wikipedia site for a description.

9.15. Connect four. (Manuel Schlenkrich) The popular board game, see game's Wikipedia site for a description..

9.16. Fifteen puzzle. (Thomas Augl) There are 15 square plaques, numbered from 1 to 15, in a 4x4 table; one position is empty. The (at most four) plaques on positions adjacent to the empty one can move to the empty position. The program offers the game to the user, so that by moving the plaques the user can bring them to an ordered configuration. The program should also be able to solve the game by itself. The initial position of the plaques is generated randomly. See http://en.wikipedia.org/wiki/Fifteen_puzzle.

9.17. Collapse game. (Jakob Moosbauer) See http://zone.msn.com/en/collapse/default.htm?intgid=hp_puzzle_16. A simpler version shall be developed: At the start, the table is completely filled. No new blocks shall be generated after the game has started.

9.18. Pick up sticks. The program generates randomly colored sticks (long rectangles with same size, horizontally or vertically). The user eliminates the sticks by clicking on them. A stick can be eliminated only when there are no other sticks on top of it.