Project 1

Dominoes

Assigned 09 Sep 2002
Design Due 15 Sep 2002
Program Due 22 Sep 2002
Updates None

Objectives

Project Description

There are many applications in which a large space needs to be covered with "tiles". For example, the space above the stove in a kitchen, or the walls inside a shower in the bathroom, or an educational child's puzzle. If the tiles are square, then there is only one pattern that can be used to cover the space. But if the tiles are not square, then many different patterns might be possible.

Dominoes are rectangular shapes which are 2 inches by 1 inch (2" x 1") in size. In this project, you will write a program to determine and display all the different patterns that can be used to cover a rectangular area with dominoes. The area to be covered will be 2-inches wide and N inches long, where N is a command line argument. Obviously, the larger value N has, the more ways there will be to cover the area.

After some thought, you'll find that this is a problem which is best solved recursively and will require multiple recursive functions.

To help you visualize the problem, these pictures show the different ways that 2" x 1" dominoes can be arranged to cover areas which are 2" x 1", 2" x 2" and 2" x 3".

Other Program Requirements

  1. To achieve the highest possible grade, your program should not contain any loops (for, while, do-while) anywhere in the code. It is certainly possible to write this program without them. However, if you find it necessary to use loops, two loops are permitted. However, a 10-point penalty per loop will be assessed.
    If your code contains more than two loops, you will recieve a score of zero
  2. You must use C++ (not C) output (i.e. use cin and not printf)
  3. DO NOT prompt the user for any input. Graders will be using scripts to test your code and no user input will be provided.
  4. Display dominoes placed vertically using two vertical bars, one on top of the other. A vertical domino looks like this | |
  5. Display dominoes placed horizontally using an equal sign followed by a tilda A horizontal domino looks like this =~

Assumptions

Your program can make the following assumptions, but no others.

A Sample Output

These outputs correspond to the pictures above. If more than one pattern is displayed, they may be displayed in any order. linux1[3] Proj1 1 | | For 2 x 1 area, totals ways is 1. linux1[4] Proj1 2 || || =~ =~ For 2 x 2 area, total ways is 2. linux1[5] Proj1 3 ||| ||| =~| =~| |=~ |=~ For 2 x 3 area, total ways is 3.

Error Handling

Your program, and ALL programs in this class, must handle the following errors:

For this project, if any of the above errors occur, send a message to the user (via cerr) and exit the program. We will learn other error handling techniques later in the semester.

Project Design Assignment

This project requires that you submit a project design text file by midnight, Sunday Sept 15th. The file may be named whatever you like, but it must be a plain text file.

At a minimum, your design submittal must inlcude the following

  1. An explanation of the basic algorithm you will use.
  2. A description of each major function. This description must include the function's name, the function's return type, a description of each parameter, and description of what the function does.
  3. A description of any major data item (arrays, structs, etc), including its purpose, limitations and scope.
Submit your file using the submit command. submit cs202 Proj1 design.txt

Project Make File

The "make" utility is used to help control projects with large numbers of files. It consists of targets, rules, and dependencies. You will be learning about make files in discussion. For this project, the file will be provided for you. You will be responsible for providing make files for all future projects. Copy the file

/afs/umbc.edu/users/d/e/dennis/pub/CMSC202/p1/Makefile to your directory.

When you finish creating all of the required project files (proj1.C, domino.C and domino.H, you will find that by typing the command make or make Proj1 at the Linux prompt, your project will compile and link (if there are no compiler or linker errors) and produce an executable called Proj1.

If you name your files anything other than proj1.C, domino.C and domino.H, or if you create additional files, it is your responsibility to provide your own makefile. Any project that does not compile and link without errors simply by typing the command make Proj1 will be considered to have a compiler/linker error.

In addition to creating your project executable, make can be used for maintaining your directory. Typing make clean will remove any extraneous files in your directory, such as .o files and core files. Typing make cleanest will remove all .o files, core, Proj1, and backup files created by the editor.

See the 202 Syllabus for links to more information on make files.

Grading

The grade for this project will be broken down as follows. A more detailed breakdown will be provided in the grade form you recieve from the grader.

Project Submission

You must use separate compilation for this project. You must have a file called proj1.C that contains the function main(). You should also have a domino.C and a domino.H that contain the functions used by proj1.C and the prototypes for those functions, respectively. (Note the uppercase "C" and uppercase "H".) Submit as follows: submit cs202 Proj1 proj1.C domino.C domino.H Makefile The order in which the files are listed doesn't matter. However, you must make sure that all files necessary to compile your project (using the make file) are listed.

You can check to see what files you have submitted by typing

submitls cs202 Proj1

More complete documentation for submit and related commands can be found here.

Remember -- if you make any change to your program, no matter how insignificant it may seem, you should recompile and retest your program before submitting it. Even the smallest typo can cause compiler errors and a reduction in your grade.