1. Define what is meant by the run-time stack, and the run-time heap. Explain how each of them are used. o 2. Using proof by induction, prove that the sum of integers 1, 2, n is equal to n(n+1)/2. 3. 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. O O O 4. Will the following Java 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; the int type can represent any integer, positive or negative. void printToN(int n) { for (int i = 0; i != n + 1; i++) { System.out.println(i); } 5. What are the two things that define an Abstract Data Type (ADT)? Give the answer we discussed in class.