Homework 0

Due: Tuesday, 1/23/2022, by 8:00am

Overview

Do your own work for this assignment; do not work with others. Consult the resources provided and your professor for help if you need it. This assignment will be submitted physically 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%.

Each question is worth 10 points. Total points: 50.

Assignment

  • 1. Define what is meant by the run-time stack, and the run-time heap. Explain how each of them are used.
  • 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.
  • 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.