Information about the individual homework assignment

In order to get the signature and a grade, it is necessary to choose, solve and deliver a homework assignment problem.

You can choose whatever problem you wish for the homework but the solution must meet the following requirements. There is a list of sample problems below, you can choose one of them as well.

Requirements

Your homework assignment must meet all of the following criteria:

Must be an individual work, you should not cooperate with your student fellows.
Approx. 2⁸..2⁹ lines of C code.
All elements of the program must be standard and portable. (ISO/IEC 9899:1990)
Extensive use of the advanced features of C is required: the program must be structurally built, must use functions.
Use appropriate data structures with dynamic memory handling (2D dynamic array, linked list or binary tree).
File handling must be used.
Your code must be indented for readability.
Use comments to document the code (min. 10%).
The program should compile without warnings (except for certain safe function alternative warnings in Visual Studio).
Two separate documents should be delivered for the program: developer doc (including testing doc) and users manual. Only pdf files are acceptable.
The documentation and the source code (.c, .h files) of the program are to be zipped into a single file that should be uploaded at the CProg portal.

The developer documentation consists of

explanation of your solution, modules, data structures, algorithms,
a list of your functions and their interface (input parameters, returned result) with explanation.

The user guide documentation consists of

Goal of the program
Instructions how to use the program
Where the files saved and loaded

Deliverables

You must submit your homework solutions in four steps. Watch the portal for deadlines. Meeting the deadlines implies extra points during the evaluation. Missing portal deadlines result is not accepted stages or HW!

HW 1. – choice: In this first step you must select a homework assignment. There is a list of sample problems below, you can choose any of them, you can also modify them, but you can specify any suitable problem for yourself, too. Make sure that the problem is complex enough and all the above listed mandatory elements will added (file handling, for instance).
HW 2. – specification: A detailed specification of your chosen problem must be uploaded. A detailed description of the goal of the program, specify the expected behaviour and output of the program for any possible user input. In the specification the internal structure of the program is not an important point. The main goal of the detailed specification is to meet the exact needs of the customer of the program. In other words it means that if two programmers receive this document and develop the requested program independently, the behaviour and capabilities of the two programs should be almost identical. If there are ambiguous points in the short specification of the chosen assignment, consult your tutor and feel free to specify it the way you like. The specification is at least 2 A4 pages, and contains all the possible input/output of your program, as well as the states of the menu etc.
HW 3. – current state of development: In this task you must submit your project with some of the planned functionalities working. The goal of the final program must be clear both from a user's and from a developer's point of view. A "hello world" application, or an empty menu will not do! It does not need to be error free, some functionalities may be missing but some of them must be realized. In this stage, proper documentation is not required yet.
For example in case of a snake game an acceptable stage can be when the head of the snake moves, it can eat apples, counts the scores but the tail of the snake is not implemented yet. In case of a phonebook application this stage can be when the input of data and their internal storage in a fix sized array is implemented, probably the file operations work, too but no dynamic data structures are used and the search option is still missing.
HW 4. – final submission: This is for delivering the final version of your program, the source files and the documentations together.
HW 5. – late submission: If you missed the deadline to deliver your homework assignment or it was not accepted, you must submit your solution here by the last day of lectures.

Presentation of the homework

The program must be presented to the lab conductor. You should be able to make slight modifications upon request. The lab conductor is going to ask questions about the code (algorithms, design decisions, syntax) and general questions from the lectures, too. Presentation must be taken face-to-face, on-line presentation is not acceptable.

Your homework will be rejected in the following cases

Not an individual work. (Supposed if the student cannot modify the program on request during presentation)
No source code uploaded, or not in the requested form.
Any of the two required documentation is missing.
The program is not working at all, or not according to the specification.
No file handling implemented.
There is no dynamic memory handling.
Some important data variable is global.
The total score is less than 10.

Scoring

When your solution submitted to HW 4. was accepted:

Each accepted milestone HW 1. - HW 4. scores 1 point (a total of 4).

The quality of your program code scores 8 points:

Correct use of elements of the C language.
No re-implementation of standard library functions.
Quality of functional decomposition.
Appropriate use of types and data structures.
Descriptive identifiers (names).
Consistently indented code.
2 problem specific points.

The quality of your documentation scores 5 points:

Your documents are not bloated (extra wide margins, large font, needless screenshots etc.)
Description of the requirements to build the program.
Data structures, design considerations.
Description of the functions (role, input parameters, output data).
Users' manual (goal of the program, inputs, outputs; controls of a game.)

The homework presentation scores 3 points:

Correct answer when asked about different details of the source code.
Correct solution for the minor modification request of the lab conductor - 2 points.

A total of 20 points can be achieved, 10 points are necessary to pass.

When your solution submitted to HW 5. was accepted.

You lose any points for the milestones HW 1. - HW 4., the rest of the points are the same.

A total of 16 points can be achieved, 10 points are necessary to pass.

Visualization

Graphics is not a requirement for the homework assignment, and not needed for most of the problems below. The standard 25x80 console screen can be used to visualize the results for most problems. In a few cases it might be advantageous to use advanced low level console handling functions (colours, positioning etc.). The econio package can be used under windows for this purpose.

Using graphics

If you still insist on problems using graphics, use a multi-platform graphics library. SDL 1.2 is highly recommended for game developers. (Do not use version 2.x for your project.)

See a brief tutorial and setup instructions here.

Sample problems

The most difficult problems

have their title in red, they are not recommended for beginners.

Fox-hare

Create a menu-driven C program, which simulates the classical predator-prey (fox-hare) problem. The base constants should be stored in a file and can be changed from within the program. The program should be able to

track changes of the rabbit and fox populations,
for any duration given by the user,
for any initial population values given by the user,
draw the population vs. time diagram,
draw the fox population vs. rabbit population diagram.

Ballistics

Create a menu-driven C program, which calculates the firing angle of a cannon for the required distance (in 2D). Be careful, the ball travels in air and there is friction. The program should be able to

find both possible firing angles,
visualise the trajectory of the ball,
take into consideration the effect of constant wind (1D).

Life

Create a menu-driven C program, which implements Conway's LIFE model. See http://en.wikipedia.org/wiki/Conway%27s_Game_of_Life for details. The program should be able to

handle a board of any user defined size (80×24 fits most console screens),
let the user determine initial state,
take initial state from file,
save current board to file,
visualise LIFE continuously, or step-by-step.

Integration

Create a menu-driven C program, which can (numerically) integrate functions given by the user. Design your data structures carefully. Implement an appropriate input deck (reverse-Polish notation can be used). The program should be able to

Handle polynomials,
a wide range of the usual mathematical functions (sin, log, exp etc.)
and arbitrary combination of them.

Statistics

Create a menu-driven C program, which analyses text, builds a database of the words and counts their occurrences. You can only read the file once! Use binary tree (or linked list) to store the words. The program should be able to

calculate statistics of words,
take input from keyboard or file,
process multiple files in the same analysis,
write the result into file.

Pascal converter

Create a command-line tool C program, which converts simple standard Pascal programs to C language. The program should be able to handle the following features of Pascal:

global/local variables, constants, assignment,
built-in data types, arrays (indexed from 1), records,
functions, procedures,
all the operators,
if-then-else, for, while,
read and write (for stdin/stdout only), pred, succ, ord, chr, odd, sqr, sqrt,
comments.

Huffman compression

Create a command-line tool C program, which compresses files using the Huffman encoding algorithm. The program should be able to:

encode files,
restore original from encoded file,
the encode/decode is controlled via command line parameters.

Lempel-Ziv compression

The algorithm of Lempel and Ziv compresses files in the following way. Suppose there is a file with the following content:

Blah blah blah

The marked sequences are the same, the second occurance can can be replaced by a reference to the first:

Blah b[D=5,L=5]lah

This means that backwards by D=5 bytes there was the same sequence of length L=5. (It seems longer but in the binary storage will be shorter than the original.)

Write a program that can compress and restore files using this method. Test your program on text files and images (like BMP. No use to test on .png or .jpg since these are compressed.) There are numerous web documents available on this method.

Morse

Create a command-line tool C program, which can handle Morse text. For Morse alphabet visit e.g. http://www.scphillips.com/morse/morse2.html. The program should be able to:

code text into Morse,
decode Morse into text (binary tree must be used),
give statistics of Latin and Morse characters (dashes, dots).
The coding/decoding should be controlled by command line switch.

Calculator

Create a command-line tool C program, which implements a non-limited range integer calculator. The program should be able to:

handle arbitrary long integers (arbitrary means infinitely many digits, without any restrictions),
their input in multiple lines (choose a continuation symbol, like: \),
carry out the five integer base operations as they work in C.

Go-moku

Create a menu-driven C program, which plays "five-in-a-row". Design your data structures carefully. The program should be able to

administer the game on a board of any user defined size (80×24 fits most console screens; 13×13 is the official board size),
follow at least three defensive and
at least three offensive rules.
save to and load from file

Reversi

Create a menu-driven C program, which plays reversi. (See https://en.wikipedia.org/wiki/Reversi for details.) Design your data structures carefully. The program should be able to

administer the game on a board of 8×8,
check players move
make offensive moves.
save to and load from file

Sokoban

There are walls, empty squares, boxes and their target position defined in a room. Your character can move around and push the boxes but can not pull them. The goal is to push all boxes onto the target squares.

Read the room definition from file! Implement a persistend hall of fame. (How many steps did it take for each player to solve a given room?) A console screen is fine for this problem. Using econio might make the control of the character easier.

Snake (needs econio or SDL)

Create a C program, which implements the well known snake game. The snake goes on its own, the user can only change directions. Apples are placed randomly on the field, eating them scores points. Also the snake grows (in length) when eating an apple. Hitting a wall or its tail (or the other snake) will make the game end. The program should be able to

handle single player and two player games,
keep track of and save best scores (hall of fames).

Charge game (needs graphics)

The program shoots a particle of positive charge in a given direction. There are a few other charged particles for the player to place them on the field. The goal is to place the particles in a way to make the moving particle hit a predefined target. Each scenario can have walls, fixed charges, etc.

The program should also score the player (e.g. the number of trials to hit the target), and administer a persistent hall of fame.

Hexxagon

A board game similar to reversi. Two players attempt to control the majority of spaces on a customizable board. The field is built of hexagons. Two players start the game each having one piece on the board. Spreading involves adding a new piece adjacent to an existing one. Jumping means moving a piece two spaces away. Whenever a piece is placed adjacent to opposing pieces these are infected, meaning replaced with friendly ones. See a YouTube video. May it be not too beautiful but it can be solved on console screen.

  _
 /*\_
 \_/o\
 / \_/
 \_/

Write a hexxagon program where the computer plays versus the user!

Minesweeper game

The field is rectangular, built of square cells. At the beginning mines are placed randomly in a number of the cells, all cell contents are hidden. Stepping on (selecting) a cell will reveal its content: if there is a mine we would explode, the game terminates. If the revealed cell is empty it will show a number: the number of mines in the surrounding 8 cells. The goal is to reveal all cells. Write a minesweeper program with the following features:

user defined size of the field,
user defined number of mines,
measuring the time elapsed,
marking cells by the player where a mine is suspected,
automatic revealing of mine-free regions.

Four colour theorem (needs graphics)

In mathematics, the four colour theorem states that, given any separation of a plane into contiguous regions, producing a figure called a map, no more than four colours are required to colour the regions of the map so that no two adjacent regions have the same colour.

Write a four color theorem "game" that generates maps randomly and lets the user colour them using four colours only. Whenever the user violates the theorem the program should emphasise the violating regions by making their colour a brighter shade. Measure the time required for a complete colouring, lead hall of fame. Let the user change difficulty: the number of regions on the map, within rational limits.

Hangman

Find a suitable list of words. There is a list here, too.

The word to guess, selected randomly by the program, is represented by a row of dashes, representing each letter of the word. If the guessing player suggests a letter which occurs in the word, then the program should reveal all in their correct positions. If the suggested letter does not occur in the word, it counts as a miss. On the tenth miss the player loses. For example, if the word is cat, the guesses are e and a, then the player should see: _a_ misses: e. The program should:

Select a random word (of length given by the user) from the list.
Notify the user if the guessed letter has already been guessed.
Let the user change difficulty: change the allowed number of misses.

The list of words file can only be read once, and hence an array is not suitable for storing the words!

Running log

Create a program that implements a running log: the data of jogs are stored in a database. For each run (training) the program should store the following data: date (year, month and day) and start time of the run (hour and minute), length of the route (in kilometers), time needed for the run (hour and minute). The program should be able to:

load existing database into memory (create a new if there is no database yet),
add new training statistics entry (data of one running) into the database,
delete training entries,
save the training statistics database (from the memory) into a file,
display the training statistics of a given day (the user may enter a date and the program should display the statistics of that day if there was a training),
for a user selected time period (the user may enter the start and end date of the period) display entry of the training of the fastest and slowest run (when, length of route, what time, what speed), and the total length the runner has run, and his/her average speed.

Facebook

Create a program that realizes the data management system of a simple, Facebook-like, invitation based community. The program should store the user name of the member, the real name of the member (family name and given name), the date of birth (year, month, day), birthplace (name of town) and the name (user name) of the person who invited this member to the community. The program should be able to:

load existing database into memory (create a new if there is no database yet),
save the database (from the memory) into a file,
insert the data of a new member into the database (the user may enter all information of the new member: nickname, family name, given name, date of birth and, birthplace of the member, and the nickname of the inviter),
search the data of a member (or members) given by his/her family name or nickname,
delete a member from the community (the user enters the nickname of the member to be deleted),
list all the members who were invited by the same person,
list all the members of the community (name, year and place of birth).

Songs

Create a program to store data of songs in a database. For each entry the program should store the following data: title of the song, name of the performer (singer or group), title of the album it was released on, year of release, genre of the music (rock, pop, hip-hop, jazz, classical, etc.), length of song (in minutes and seconds). The program should be able to:

load existing database into memory (create a new if there is no database yet),
add new song entry to the database,
delete song entry from the database,
edit song entry,
save the database (from the memory) into a file,
display all songs of a user selected artist (the user may enter the artist, for example “Lady Gaga”),
display all details of the songs of a user selected album (the user may enter the name of the artist and the title of the album),
list all songs that were released in a user selected year,
list all songs (title, performer, album, release year) of a user selected genre (for example: list all hip-hop songs).

Task manager

Create a program to store tasks in a database. For each entry the program should store the following data: name of the task (short name), description of the task (text less than 200 characters), category (like work, university, family, household, etc.), start and end date of the task (year, month, day), priority of the task (for example 1 for highest, 10 for lowest priority), dependency (if there is another task that should be finished before this task can be started – the name of this other task should be given here, or if there is no dependency, this field should be left empty). The program should be able to:

load existing database into memory (create a new if there is no database yet),
add new task entry into the database,
delete task entry from the database,
edit task entry,
save the database (from the memory) into a file,
create new categories on user’s request,
display all details of the tasks that belong to a user selected category (the user may enter the category),
display all details of the tasks that are not yet finished (the user enters the date of today, and the program should list all tasks where the end date is not yet reached), list them in chronological order (according start or end date)
display all details of the tasks that are depending on other tasks, and list also the details of these other tasks too (for example if “Painting of walls” is depending on the “Construction of walls”, then you should list all data of both “Painting...” and “Construction...” tasks).

Car fleet manager

Create a program that implements a car fleet manager: the program should store re-fuelling data in a database and determine when a general service of the cars is needed. For each re-fuelling the program should store the following data: license plate ID of the car (for example the Hungarian type: three letters of alphabet and 3 numbers), manufacturer and make of the car (like Toyota Land Cruiser), date of the re-fueling (year, month and day), amount of fuel filled (in liters), mileage of the car (in kilometers). The program should be able to:

load existing database into memory (create a new if there is no database yet),
add new re-fueling entry into the database,
delete re-fueling entry from the database,
edit re-fueling entry,
save the re-fuelling database (from the memory) into a file,
display the average consumption of the user selected car (the user may select the car by entering its license plate),
list all cars that need to go to service in the near future: these are cars that have already exceeded 20.000 kilometers, or according on the overall mileage of the car and the frequency of re-fuelling, it is expected that its mileage will exceed 20.000 kilometers within 3 months (1/4 year).

Birthdays and Anniversaries

Create a program to store birthdays and other anniversaries of your relatives and friends in a database. You should be able to add a new event to the database, for each entry the program should store the following data: date of the anniversary (year, month and day), type (birthday, nameday or other anniversary), category (like family, relative, friend, colleague, etc.), name (or description of the anniversary, like “John Smith” – for a birthday, or “Anna and Juan” for a marriage, etc). The program should be able to:

load existing database into memory (create a new if there is no database yet),
add new birthday/anniversary entry into the database,
delete birthday/anniversary entry from the database,
edit birthday/anniversary entry,
save the database (from the memory) into a file,
display all birthdays/anniversaries that belong to a user selected category (the user may enter the category),
display all birthdays/anniversaries that are on a user selected day (the user enters the day),
display all birthdays/anniversaries that did occur in the last month and those that will occur in the next month – list them in chronological order (in the order they will happen).

Wallet (incomes and expenses)

Create a program to store your incomes and expenses in a database. You should be able to add incomes and expenses to the database. For each entry the program should store the following data: date (year, month and day), type (income or expense), category (like household, food, party, travel, scholarship, salary, money from poker games, etc.), the amount (given in HUF, EUR or whatever you want). The program should be able to:

load existing database into memory (create a new if there is no database yet),
add new income/expense entry into the database,
delete income/expense entry from the database,
edit income/expense entry,
save the database (from the memory) into a file,
create new categories on user’s request,
display your total expenses and incomes, the name of the most expensive category and the money you spent for that category, and your overall balance (the money you have) – this means evaluating all entries of the database,
for a user selected time period (the user may enter the start and end date of the period) display statistics for each category (total spent, total income, largest expense).