# Homework 0

Due: August 29th, 2012 at the beginning of class
Homework turned in after class will not be accepted.
Homework turned in during class but after I have collected it will lose 20%.
120 total points

Do your own work for this assignment; do not work with others. Consult the book and your professor for help if you need it. Please write neatly, or preferably type your answers. Use good grammar, spelling, and complete sentences.

Each question is worth 10 points.

1. Define what is meant by the run-time stack, and the run-time heap. Explain how each of them are used.
2. When the following function runs, what variables and memory live on the run-time stack? What variables and memory live on the on the run-time heap? The things you should consider are underlined.
```class Node {
public:
Node(int v, Node *n = NULL) { value = v; next = n; }

private:
Node *next;
int value;
};

Node *createList(int numberElements) {
for (int i = 0; i < numberElements; i++) {
int v;
cin >> v;
}
}
```
3. Computers have an interesting way of computing modulus. To illustrate, write a (very short) C++ program to compute the values of the following expressions. What do you notice that is different, interesting, or surprising about the results?
``` 30 % 8
-30 % 8
30 % -8
-30 % -8
30 % 0
```
4. Using proof by induction, prove that the sum of integers 1, 2, ..., n is equal to n(n+1)/2.
5. What are the four fundamental rules of recursion? After listing them, design a recursive function that follows the four rules and explain how it follows each of them.
6. Will the following C++ function terminate for all inputs? Prove your answer. You should assume that the int type does not wrap around. That is, it will not overflow; it can represent any integer, positive or negative.
```void printToN(int n) {
for (int i = 0; i != n + 1; i++) {
cout << i << endl;
}
}
```
7. What are the two things that define an Abstract Data Type (ADT)? Give the answer we discussed in class.
8. Explain why it is good design practice to hide data members and certain functions in C++ classes behind the "private" access specifier.
9. Your book identifies a set of guidelines for passing parameters that are (a) small and need not be modified, (b) large and must not be modified, and (c) anything that may be modified. However, these differ from the conventions we will use in this class. How are they different?
10. What are the "big three" functions that any C++ class must have if it allocates its own memory (on the heap)? Explain why are they needed.
11. Explain how a function template is different from a non-templated C++ function.
12. Explain the concept of inheritance in object oriented programming. Then explain how a derived class may override a function of a parent class in C++, and what it means when this happens. You may give a small example if you wish.