Pointer Exercises:
------------------

1. Given the following definitions:
            int ival = 1024;
            int *iptr;
            double *dptr;

which of the following assignments, if any, are illegal and why ?

a) ival = *iptr;
b) *iptr = ival;
c) *iptr = &ival;
d) dptr = iptr;
e) ival = iptr;
f) iptr = ival;
g) iptr = &ival;
h) dptr = *iptr;


2. Given the following set of variable definitions

    int *ip1, ip2;
    char ch, *cp;

Which of the following assignments are type violations ? Explain why.

a) ip1 = "All happy families are alike";
b) cp = 0;
c) ip1 = 0;
d) cp = &'a';
e) ip1 = ip2;
f) cp = '\0';
g) ip1 = '\0';
h) cp = &ch;
i) *ip1 = ip2;


Array and String Exercises:
---------------------------

1. Which of the following array definitions are illegal ? Explain why.

int get_size();
int buf_size = 1024;

a) int ia[buf_size];
b) int ia[get_size()];
c) int ia[10];
d) int ia[4*7 -14];
e) int ia[2*7 - 14];

2. Is there a problem with the following initialization ?

char st[11] = "fundamental";

3. Implement a function to determine if two strings are equal.


4. Implement a function to determine the number of
   occurences of a character within a string.

5. Implement a function to determine if a substring occurs within a string.

6. Implement a function to compare two arrays for equality.

7. Implement a function to search an array for a particular value.
If the value is found, return its array index. If not return -1.

List Exercises
--------------

1. Add an operation that returns the length() of a List to the List 
class we implemented in the tutorial - i.e., a count of the number of Items.
A sample implementation for a List class will be provided as well.

2. Implement an operation that reverses a list. 

3. Modify the List class implementation so that only one occurence of
each item is maintained.

4. Modify the List class implementation so that the list of Items is
maintained in sorted order.


Operator Overloading
--------------------

1. A binary tree class must provide the following general 
functionality: isEmpty(), isEqual(), print(), addNode(), build(),
copy(), and deleteNode().

Which of these member functions are candidates for operator overloading ? 

Class Exercises
---------------

Solutions for exercises 1, 4, 6, 7 and 8 are provided.

1) Implement a Resistor class that has the 
following class definition:

class Resistor {
  private:
    float resistance;
  
  public:

    Resistor();
    Resistor(float resistance);

    void printResistance();
    float calculateVoltage(float current);
    float calculateCurrent(float voltage);

    Resistor operator+(Resistor r);
    Resistor operator|(Resistor r);
};

Each resistor object has a private resistance.  
The value of this resistance can be printed using
the printResistance method.  Using Ohm's law V = I*R 
(where V is voltage, I is current and R is resistance), 
the resistor class can calculate the voltage across or 
current through the resistor.  Two resistors R1 and R2 
can be added together in series using the + operator 
to yield a new resistor with a resistance equal to 
R1.resistance + R2.resistance.  Two resistors can be 
combined together in parallel using the | operator, to 
yield a new resistor with 
resistance = (1 / (1/R1.resistance + 1/R2.resistance)). 
Implement and test your Resistor class.

2) Implement a BankAccount class.  Each BankAccount is 
described by the account number (an integer), the name 
of the owner (a string) and the current balance (a float).    
Implement methods to print out the current balance, make 
a deposit and to remove money from the account.  Make sure 
to check for error conditions (such as removing more money 
than is in the account).  

3) Design a Bank class that can hold zero or more BankAccount 
objects (defined in exercise 2).  Design the class such that 
it holds a predefined maximum number of BankAccounts (use an 
array of BankAccounts).  Include methods to find BankAccounts 
by account number or name.  Also include methods to deposit 
or withdraw money from an account identified by name or account 
number.  How might your Bank class be changed so that the 
maximum number of BankAccounts is not fixed?  
 
4) You are given the following class definition: 

class MyClass {
  private:
    int x;
    int y;
    void print();

  public:
    MyClass();
    int z;
    void changeX(MyClass m);
    void write();
};

which of the following implementations of changeX 
contain valid code (i.e. code that will compile and 
execute without error): 

a)  void MyClass::changeX(MyClass m) {
       x = m.z;
    }

b)  void MyClass::changeX(MyClass m) {
       (*this).x = m.z;
    }

c)  void MyClass::changeX(MyClass m) {
       this->x = m.x;
    }
      
d)  void MyClass::changeX(MyClass m) {
       print();
       m.print();
    }

5) Below is an implementation of a Square class.  
Create similar classes that describe and calculate
the area for (a) a Circle and (b) a RightTriangle.
Add methods to all of these class to calculate the
length of the perimeter.

/********* in Square.h ***************/

class Square {
  private:
    float lengthOfSide;

  public:
    Square();
    Square(float l);
    void setLengthOfSide(float l);
    float calculateArea();
};

/********* in Square.cc ***************/

#include "Square.h"

Square::Square() {
}

Square::Square(float l) {
  lengthOfSide = l;
}

void Square::setLengthOfSide(float l) {
  lengthOfSide = l;
}

float Square::calculateArea() {
  return lengthOfSide*lengthOfSide;
}

6) Create a HelloWorldFunc class so that the following
main function will print "Hello World!" to the output.

int main() {
  HelloWorldFunc HWF;
  HWF();
  return 0;
}

(HINT: define a void operator()(); method that overloads
 the () operator for the HelloWorldFunc class).

7) Implement and test a Fraction class that uses the following
   declaration:

class Fraction {
  private:
    int numerator;
    int denominator;

  public:
    Fraction();
    Fraction(int n, int d);

    // prints the fraction as "numerator / denominator"
    void show();

    // Calculates and returns the 
    // decimal value of a fraction
    double evaluate();

    // Overrides of operator "+" for fraction addition
    Fraction operator+ (Fraction f);
};

8) Implement an Array class that contains an array of integers.
The size of the array should be set by the constructor.  Overload
the [] operator to return a reference to an integer. 

HINT:  int &operator[] (int element);

Create a sample program that creates an Array of size 100 and
stores the numbers 1 to 100 in the corresponding elements.
Print out the array.  The only methods defined in Array should be 
the constructor and the overloaded [] operator.


SAMPLE SOLUTIONS
----------------


1) Below are an example Resistor.h and Resistor.cc  

/*************** Resistor.h ****************/

#ifndef __RESISTOR_H_
#define __RESISTOR_H_

class Resistor {
  private:
    float resistance;
  
  public:

    Resistor();
    Resistor(float resistance);

    void printResistance();
    float calculateVoltage(float current);
    float calculateCurrent(float current);

    Resistor operator+(Resistor r);
    Resistor operator|(Resistor r);
};

#endif

/*************** Resistor.cc ****************/

#include <iostream>
#include "Resistor.h"

using namespace std;

Resistor::Resistor() {
  // do nothing
}

Resistor::Resistor(float r) {
  resistance = r; 
}

void Resistor::printResistance() {
  cout << "R = " << resistance << endl;
}

float Resistor::calculateVoltage(float current) {
  return (current * resistance);
}

float Resistor::calculateCurrent(float voltage) {
  return (voltage / resistance);
}

Resistor Resistor::operator+(Resistor r) {
  Resistor temp;
  temp.resistance = resistance + r.resistance;
  return temp;
}

Resistor Resistor::operator|(Resistor r) {
  Resistor temp;
  float inverse = 1/resistance + 1/r.resistance; 
  temp.resistance = 1/inverse;
  return temp;
};


4) All of the implementations of changeX are valid.

6) The header and source files are: 

/******** HelloWorldFunc.h *********/

class HelloWorldFunc {
  public:
    HelloWorldFunc();
    void operator()();
};

/******** HelloWorldFunc.cc ********/

#include <iostream>
#include "HelloWorldFunc.h"

HelloWorldFunc::HelloWorldFunc() { }

void HelloWorldFunc::operator()() {
  cout << "Hello World" << endl;
}

/************ main.cc **************/

#include "HelloWorldFunc.h"

using namespace std;

int main() {
  HelloWorldFunc HWF;
  HWF();
  return 0;
}

7) The header and source files are below:

/**************** Fraction.h ***********/

class Fraction {
  private:
    int numerator;
    int denominator;

  public:
    Fraction();
    Fraction(int n, int d);

    // prints the fraction as "numerator / denominator"
    void show();

    // Calculates and returns the 
    // decimal value of a fraction
    double evaluate();

    // Overrides of operator "+" for fraction addition
    Fraction operator+ (Fraction f);
};

/*************** Fraction.cc ***********/

// The class definition for fractions.

#include <iostream>
#include "Fraction.h"

using namespace std;

Fraction::Fraction(int n, int d)
// A Fraction constructor which allows the numerator and denominator
// to be specified.
{
    numerator = n; 
    denominator = d;
}

Fraction::Fraction()
// Another constructor.  If no arguments specified, default to 0/1. 
{
    numerator = 0; 
    denominator = 1;
}

void Fraction::show()
// Display a fraction, in the form "numerator/denominator."
{
    cout << numerator << '/' << denominator;
}

double Fraction::evaluate()
// Calculates and returns the decimal value of a fraction
{
    double n = numerator;	// convert numerator to float
    double d = denominator;	// convert denominator to float
    return (n / d);		// compute and return float representation
}

Fraction Fraction::operator+ (Fraction f)
// Override of operator "+" for fraction addition
{
    Fraction r;				
    r.numerator = (numerator * f.denominator) + 
	(f.numerator * denominator);	
    r.denominator = denominator * f.denominator;    
    						// compute denominator
    return r;					// return the result
}

/**************** FracMain.cc ***************/

#include <iostream>
#include "Fraction.h"

using namespace std;

int main() {
  Fraction half(1,2);
  Fraction quarter(1,4);

  Fraction result = half + quarter;

  cout << "1/2 + 1/4 == ";
  result.show(); 
  cout << endl;

  return 0;
}

8) The source file (main.cc) is given below.  It includes the
   definition of Array as well as main (yes you might want to
   put Array in Array.h and Array.cc).  Do you understand what
   is happening in the following program?

#include <iostream>

using namespace std;

class Array {
  private:
    int *array;
  public:
    Array(int size);
    int &operator[] (int element);
};

Array::Array(int size) {
  array = new int[size];
}

int &Array::operator[] (int element) {
  return array[element];
}

int main() {
  Array a(100);

  for (int i = 0; i < 100; ++i) {
    a[i] = i;
  } 
 
  for (int i = 0; i < 100; ++i) {
     cout << "a[" << i << "] == " << a[i] << endl;
  } 

  return 0;
}

Recursion Exercises
-------------------

1. Write a Power(int x, int n) function that returns x * x * ... (n times).
   Count the number of times Power() is called when you invoke Power(2, 30).

2. Now rewrite the Power function so that you invoke Power(x, n/2) as part of
   the definition of Power(x, n). Again count the number of times Power() is
   called when you invoke Power(2, 30).

3. Write a recursive function Reverse() that accepts two string arguments S and
   R. Function Reverse() uses recursion to reverse the characters in string S
   and place the reversed string in string R. String S should not be modified.

4. Write a recursive function PrintNumber() that accepts an integer
   argument. Function PrintNumber() uses recursion to print out the value of
   its argument one digit at a time. For example, the PrintNumber(1023) should
   print the digits 1, 0, 2, 3.

5. Implement insertion sort as a recursive function.

6. We have talked about InOrder() and PreOrder() traversal in binary search
   trees in class. Implement these traversals on a binary search tree
   (as recursive functions).

7. Tough/Tricky: Now implement one of the InOrder() and PreOrder() functions
   without using recursion. Hint: You will need a stack of pointers to nodes!
   Which implementation, recursive or non-recursive is easier to write and
   debug? Why does the recursive implementation not require a stack of
   pointers.