HW4 Assignment

CS 311
Assignment 4
Assignment 4 is due at 5:00 p.m. Monday, October 17. It is worth 25 points.
Procedures
This assignment is to be done individually.
Submit your answers on Blackboard.
●	Your answers should consist of two files: countrt.h and countrt.cpp, from Exercise A. The two files (or a single archive file containing them) should be submitted on Blackboard.
●	Be sure to include your name in each file.
Exercises (25 pts total)
Exercise A — Counting Rectangle Tilings
Purpose
In this exercise, you will implement recursive search with backtracking.
This exercise does not emphasize implementation details and language features nearly as much as earlier programming exercises did. You still need to write high-quality code and follow the coding standards; however, this should be relatively easy, for those that did a decent job on the previous assignments.
The key part of this exercise is the logic that the code must follow. When you do this exercise, it is probably worthwhile to spend more time planning, and less time coding, than you have before.
Background
Consider a rectangle divided into squares, like a checkerboard or chessboard. You are given a set of tiles with numbered edges, and must place them on the board so that the numbers match. The tiles must not only match each other where they touch, they must also have a 1 on the outer edges of the board.
For more information on boards and tilings, along with illustrations, see slides 9–12 from the October 10 lecture slides.
Instructions
Write a C++ package that counts the number of tilings on a given board. Be sure to follow the coding standards. Standard 3A (“Requirements on template parameter types must be documented.”) and standard 3B (“ If a function is not a template and not a member of a class template, then the exceptions it throws must be documented.”) now apply. You do not need to follow standards 3C or 3D.
●	Your package should be contained in files countrt.h and countrt.cpp.
●	You will need to #include "Tile.h" (but don't turn it in.)
●	The public interface of this package consists of a single function: countRT, which returns the number of tilings on a given board (details below).
●	Function countRT should do the bulk of its work via a call to a function countRT_recurse, which is a recursive function (global or member) that counts the number of tilings based on a given partial solution.
○	Note: Function countRT_recurse is not part of the public interface of the package. Prototype and implement it however you want; I will not test it. However, it must exist, be recursive, be used by countRTto do most of the required computational work, and perform the correct computations for the partial solution it is given.
Here are the details for function countRT.
●	It should be prototyped as
●	 int countRT(const TileSet& tiles, int xSize, int ySize);
●	For legal parameter values, function countRT returns the number of tilings on a xSize × ySize board using tiles from the given tile set.
●	The function should work properly for all meaningful parameter values (ignoring stack overflows due to excessive recursion depth).
○	Function countRT will only be called with parameter values that make sense. In particular, xSize and ySize will always be positive.
○	Your documentation should include information about what parameter values the function will accept (preconditions).
●	The function should run in a “reasonable” time (say, less than two minutes on a recent machine) whenever there are fewer than 20 million solutions.
Notes:
●	Your function is only required to be fast for boards with fewer than 20 million solutions. However, it is still required to work for large boards with many types of tiles. Do not arbitrarily limit the size of a board or the tile set!
●	The October 10 lecture slides contain suggestions for how to do this assignment.
Test Program
I have written a test program: countrttest.cpp. If you compile and run your package with this program (unmodified!), then it will test whether your package works properly.
Do not turn in countrttest.cpp.
Notes:
●	When your homework is graded, function countRT may be called with different parameters from those in the test program.
●	The test program does not check whether function countRT_recurse meets the requirements of the assignment; nor does it check whether your code is fast enough.
What about Speed?
This exercise emphasizes logic, not efficiency. For grading purposes, running in a reasonable time is all I ask; you will not be given extra credit for super-fast code.
However, for those who like a challenge, once you get your code working, see how fast you can get it to run. I will do timing tests on all working implementations; the names of top performers will be announced in class some time after the homework is graded.