For the programming aspect of the course, the assignments will be based on completing a number of challenges by the end of the course.
Each challenge is given a point rating and you must complete challenges equal to at least
For each challenge you should hand in (typed please):
Partnering: You may do up to 50 points with a partner. However the number of points a challenge is worth will drecrease to half value. (E.g. if you do challenges worth 100 points with a partner, that's 50 for you and 50 for them, so you still have to do 50 more on your own.)
Below is a list of challenges. Throughout the term, this list may grow. Feel freee to send your own suggestions for challenges.
You must not simply copy or slightly modify a solution you find in a book, an article, on the net, etc. You may use a published algorithm, if it is properly cited.
Read in a file of floating point numbers. Calculate and print the mean, minimum, maximum, and standard deviation.
Create a program to output Pascal's triangle up to the 10th row (remember to make your code easily modifiable).
Pascal's Triangle is formed by starting with 1 and forming the next row by adding the number above to the number to the left (if any). Thus
1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1
etc.
Create a program that reads in a year and a month (it might obtain these from the command line) and prints a calendar for the month, using the Gregorian system.
Read in a text file containing:
7 12 A# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #a #
The robot can only move in four directions (up, down, east, west) and may only occupy "floor" locations. It can not leave the maze. Each move takes 1 time unit.
Your program must find and report a path from the initial position to the final position (if there is such a path), or report that there is no such path (otherwise). It should demonstrate the path by printing the maze showing the path with characters ^ V < >.
As above, but the path reported must be optimal (minimum time).
Now there are up to 10 robots (a,b,c,..,j), each with an initial and a final position. Each robot is capable of the four moves above and one additional move "stay". For each robot find a path that gets it to its final position subject to the constraints that: (1) no two robots may occupy the same location at the same time, (2) no robot can move to a location that was occupied in the previous time unit. The set of paths found should be optimal in the sense that the length of the longest path, should be as short as possible. Demonstrate the path by printing out the maze over time showing the location of the robots at each unit of time.
Create an interactive program to act as a calculator. Your program should read lines like
12.5*2+123.4/2
and print the answer in response. Your calculator should understand the precedence of * and / over + and -. It should print an error message in response to any ill-formed input line. As a minimum it should understand + - * / ( and ).
You might consider adding features such as pi, sin, tan, memory and programmability.
Hint: You can find some useful algorithms at http://www.engr.mun.ca/~theo/Misc/exp_parsing.htm.
Design and implement a class that sends messages to either the screen (i.e. cout), to a file named log.txt, or to both (or neither).
A possible interface for this class would be
class Logger {
public: Logger() ; // By default message go to both screen and file.
public: void setScreenOutput( bool ) ;
public: void setFileOutput( bool ) ;
public: void sendMessage( char * ) ;
public: ~Logger() ; // Closes the file.
private: Logger( const Logger & ) ; // Not implemented
private: Logger & operator=(const Logger & ) ; // Not implemented
} ;
(Note I declared the copy constructor and the assignment operator, in order to prevent the compiler from creating its own versions. There is no need to implement these methods.)
You should also design a test program that tests your class.
Design and implement a class for representing 3 dimensional arrays.
Your class should represent arrays in such a fashion that the space required is O(N) where N is the number of array entries that are not 0.0. The dimensions of the array should be set on construction.
Many interactive applications feature the ability to undo edits made by the user. The assignment looks at one way to implement these.
Consider the following interface class
class Undoable {
public: virtual void checkpoint() = 0 ;
public: virtual void undo() = 0 ;
public: virtual void redo() = 0 ;
} ;
We can create a derived class with interface:
class UndoableInt : public Undoable {
public: UndoableInt() ; // Initializes to 0.
public: void setValue( int i ) ;
public: int getValue() ;
public: virtual void checkpoint() ;
public: virtual void undo() ;
public: virtual void redo() ;
} ;
The idea is that when undo is called the value of the object reverts to the value it had at the previous checkpoint. If undo is called again, then the value is the value at the checkpoint before that, etc. Calls to redo, restore the value to the value it had before the last undo.
Let's look at an example:
Call Value that getValue would return
---- --------------------------------
UndoableInt 0
setValue( 1 ) 1
setValue( 2 ) 2
checkpoint() 2
setValue( 3 ) 3
setValue( 4 ) 4
checkpoint() 4
undo() 2
undo() 0
undo() 0 // no effect
redo() 2
redo() 4
undo() 2
checkpoint() 2 // clears the redo list.
redo() 2 // no effect
We can create another derived class representing arrays of ints
class UndoableIntArray : public Undoable {
public: UndoableIntArray(int size) ; // Array has N elements, all 0.
public: void setValue( int index, int value ) ;
public: int getValue(int index) ;
public: virtual void checkpoint() ;
public: virtual void undo() ;
public: virtual void redo() ;
} ;
We can also create a collection of objects that are undone and redone together
class UndoableCollection : public Undoable {
public: UndoableCollection(int size) ;
public: void addObject( Undoable &object ) ;
public: virtual void checkpoint() ;
public: virtual void undo() ;
public: virtual void redo() ;
} ;
To use this class, you add a number of undoable objects to it (up to size) and then calls to undo, redo and checkpoint are passed on to the various members of the collection.
Design and implement these classes.
Design a class to represent the chess board. Your class should be capable of reporting the position of pieces, moving the pieces, and printing the board. Design another class to produce a list of all legal moves.
Output can be an ascii representation of the board, e.g.
8 r n b q k b n r
7 p p p p p p p p
6 * - * - * - * -
5 - * - * - * - *
4 * - * - * - * -
3 - * - * - * - *
2 P P P P P P P P
1 R N B Q K B N R
a b c d e f g h
Builing on the above, create a program to allow two human players to play a game, checking that each move is legal, and declaring mate when the game is over.
Design an interactive program to play chess against a human player.
Look up the Min-max algorithm (see almost any book on artificial intellegence) and apply it to the problem. You will also need an evaluation function to estimate the strength of a given position.
Last modified: Thu 2002.01.17 at 16:08 NST by Dennis Peters