Data Structures and Algorithms I

Assignments 

Due April 26, in class - Homework 4: Assuming the existence of template files Stack.h and Queue.h and that these templates define and implement assignment and copy constructors, complete these functions in the context shown:

#include <iostream>
#include "Stack.h"
#include "Queue.h"
template <class X>
operator std::ostream operator << (std::ostream & out, const Stack<X> & q){
//assuming type X has a well-defined << operator.
//output comma-delimited queue contents surrounded by < and > characters
//like this: <e1, e2, e3, ..., en> (top item is listed first)

}
operator std::istream operator>>(std::istream & in, Queue<char> & q){
//Place all characters of current line of file into the queue. 
//Stop when newline is encountered. Extract the newline, 
//but do not place it in the queue.

}

template <class X>
Queue<X> reverseQ(Queue<X> q){
//Return a queue with the same contents as q, but in the reverse order

}

template <class X>
bool bottom(Stack<X> s, X & item){
//If the stack is empty, just return false leaving item unchanged.
//Otherwise copy the bottom element of the stack into item and return true

}

Due April 16, midnight - Program 4: Linked List / Associative Array (Corrections finally :) )

Due March, 19, in class - Program 3: Templates

Due Feb 26, in class - Homework 3: Implement the following operators for a Fraction class (f represents a Fraction object)

• a) !f;  //member implementation, !f returns the constant value 1/f, does not change f (returns 0 if f was 0)
• b) ~f; //non-member, friend imp., ~f sets f to 1/f and returns a const reference to the new value (no change if f was 0)
• c) ++f; //member imp., increases f by 1, and returns const reference to new value
• d) Can the previous operator return a value rather than a reference? Explain.
• e) f++; //member imp., increases f by 1, returns old value of f as a const
• f) Can the previous operator return a reference rather than a value? Explain.
• g) x*f; //non-member, friend imp., x is an integer, returns a const Fraction value equal to x*f, neither x nor f are changed (if f was 5/2, then 2*f would be 5/1)
• h) Can the comma operator in g) be implemented as a member of the Fraction class? Explain.
• i) f | x; //non-member, non-friend, returns a const Fraction value. If f is a/b, then the Fraction value returned is (a-x)/(b-x). If b-x is 0, it returns 0. Assume the Fraction class includes public members getNum() and getDen().
• j) Can the | operator in i) be implemented as a member of the Fraction class? Explain.

Due Feb 29, 11:59 PM - Program 2: Polynomials  (corrected sample output 2/23 and error in sample data on 2/24)

Due Thursday, Feb 19, in class - Homework 2: 

1. D&D pg 544, Answer question 7.5
2. D&D pg 544, Answer question 7.6. 
3. Define a class representing polygons. The constructor requires the number of sides and an array of integers containing the lengths of the sides. Provide a destructor and a public method that computes and returns the perimeter of a Polygon object.
4. Define a class representing an elevator button. The constructor must take an integer representing the floor number where the button is located. Provide a method to 'push' the button, a method to return the floor number of the most recent button press, and a method to clear all previous button presses. None of the methods require any arguments. Provide within the class, storage locations for the floor number of the most recent button pressed and a boolean indicating that a button was pressed. These variables are shared by all buttons and accessed by the methods listed above. In a simple main function, show how to instantiate 10 elevator buttons on floors 1 through 10. Also illustrate how to push a button, how to clear all previous button presses, and how to determine if a button was pressed (since the last clear message) and if so, which button was most recently pressed.

(Extension!) Due Monday, Feb 9th, 11:59 PM - Program 1 (updated Feb 4): Credit Accounts Note: The transaction file had a typo (a comma rather than a decimal point) on line 16 - Feel free to correct it. I have updated it in the zip archive. (Turn in a printed copy of this program and email the project files)

Due Monday, Jan 26th, in class - Homework 1: Submit a printed copy of your solution to the following problem. Give a declaration and implementation (that is, show the method definitions) for a class named LetterSet that is to model a set of letters (you should treat uppercase and lowercase letters the same). LetterSet objects can contain up to 26 elements ('a'-'z').

• A conversion constructor must exist to create a one-element set from a character passed as an argument (the created set may be empty if the character is not a letter).
• Another conversion constructor should take a string (char *) and create a set containing all of the letters (letters only) found in the string. This constructor should also act as a default constructor that would create an empty set (use a default argument with no letters).
• Provide a print method that will display something like {a, f, w} or { }. Output should be capable of being sent to any ostream object (not just cout). List elements of the set in alphabetic order.
• Provide an isElement method to determine if a character is an element of the set (return true or false).
• Include methods to perform set union and intersection. These methods should return a new set representing the union or intersection of two existing sets. For example, c = a.union(b); would calculate the union of the sets a and b, and return the new set which would then be assigned to the set c.

Write a paragraph describing how your implementation stores and represents sets in memory (describe the structure of your objects). This should be typed at the top of your file as documentation. Don't forget your name and date.