Homework Questions

Due - Tuesday, Dec 13, 2005

Write, compile, debug, and test a BinarySearchTree class. Your class should support the insert, size, isEmpty, preOrderPrint, postOrderPrint, and inOrderPrint functions. Your TreeNode should store a single string. Electronically submit BST.h, BST.cpp, TreeNode.h, TreeNode.cpp, and Test.cpp

Chapter 6 - R-6.1(a-h), R-6.6(a), R-6.12
Write, compile, debug, and test a LinkedQueue class. As with the LinkedList and LinkedStack classes, each element of your stack should be stored in a Node object that contains a single character. All data members must be declared private or protected. Your LinkedQueue must support the enqueue, dequeue, isEmpty, size, and printQueue functions. Electronically submit LinkedQueue.h, LinkedQueue.cpp, Node.h, Node.cpp, and Test.cpp.

Write, compile, debug, and test a Stack class. You may draw on your LinkedList and Node classes or you may use an array implementation. Alternatively, for those who want to get a head start on Project 2, you may use a doubly-linked list implementation. For any implemetation, your Stack class must provide the push, pop, top, isEmpty, size, and printStack functions. Electronically submit all files required to compile and run your program along with a README file that describes each file submitted and provides instructions for running your program.
Write AND IMPLEMENT an algorithm for a new stack function which will return the second element from the top of the stack without changing the stack. Your algorithm should call push, pop, and top to access stack elements. (you may not directly refer to the second-to-top element.)
Write AND IMPLEMENT an algorithm for a new stack function removeAll. This function takes as input an element, removes all occurrences of that element from the stack, and leaves the remaining elements in their orignal order. For example, assume the original stack was: 10, 45, 6, 77, 6, 6. After the call removeAll(6), the stack will be as follows: 10, 45, 77. You must use push, pop, and top to move elements. You may NOT access elements directly.

Chapter 4 - R-4.8, C-4.10, C-4.12 (don't repeat for a doubly linked list), C-4.15
Write, compile, debug, and test a LinkedList class. Your class should support the insertAtHead, removeHead, printList, size, and isEmpty functions. You must implement a Node class that will be used to store a single character and will represent a single element of your LinkedList. All data members of all classes must be declared private or protected. Electronically submit LinkedList.h, LinkedList.cpp, Node.h, Node.cpp, and Test.cpp

Design (don't implement) a program to play a card game of your choice (such as Poker, BlackJack, or Go Fish). Your design should list a series of classes, the member variables of each class, and the methods of each class. At least one of your classes should be a derived class and you should clearly indicate any methods which are overriden.
Chapter 2 - R-2.10, R-2.11
Submit a complete design and algorithm for Project 1. This should include a short description of each class you plan to implement, the members (variables and functions) of each class, and complete algorithims for each member function (including main)

Write, compile, debug, and test a ChangeMaker class. Your ChangeMaker class should act as a cash register. It should store various bills and coins and be able to make change for a given charge and amount paid. For example, if the charge is $3.50 and the amount paid is a $5.00 bill, the change would be $1.50 and the ChangeMaker would increase the number of $5.00 bills stored by 1, decrease the number of $1.00 bills stored by 1, and decrese the number of quarters stored by 2. Be careful to test for error conditions such as when there are no more quarters remaining. Electronically submit ChangeMaker.h, ChangeMaker.cpp, and Test.cpp. If your design lends itself to having additional classes, make sure to submit those classes as well.

Chapter 1 - R-1.5, R-1.8
Write, compile, debug, and test a Beverage class. The data members of your Beverage class should describe the properties of a beverage, for example the type of beverage and the size of the beverage (you should include more properties than just these two). The functions should, at the very least, provide accessor and modifier functions for the data members of the class. To test your class, write a driver that contains a main function that will create an instance of the Beverage class and invoke all of its member functions at least once. Electronically submit Beverage.h, Beverage.cpp, and Test.cpp.