Homework 2

Due: September 26th, 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%.
115 total points.

Do your own work for this assignment; do not work with others. Consult the book and your professor for help. Please write neatly, or preferably type your answers. Use good grammar, spelling, and complete sentences. Any code you write should "just work" if I typed it in and compiled and ran it.

  1. (5 points) A const method is one which does not change the data member(s) of an object when the method runs. It is signified by a "const" after the argument list of the method, e.g. void doSomething() const;. Which of the following methods on a Stack class should be marked as const methods based on what they apparently do?
    • void pop()
    • void clear()
    • void push(const Base & val)
    • const Base &top()
    • int getSize()
  2. (10 points each, 30 points total) Analyze these functions. For each function, give the complete T(n) (or T(m,n), or whatever is appropriate), then find the tightest time complexity you can, in big-Oh notation. You need not show every step in getting from T(n) to big-Oh. You should assume all inputs are > 0.
    1. int f1(int n) {
          int i = 1;                      // c1
          for (int j = 1;                 // c2
                          j <= n;         // c3
                                  j++) {  // c4
              i = i * j;                  // c5
          }
          return i;                       // c6
      }
                  
    2. int f2(int m, unsigned int n) {
          for (int i = 0;                    // c1
                          i < 2 * m;         // c2
                                     i++) {  // c3
              for (int j = n;                // c4
                              j > 0;         // c5
                                     j--) {  // c6
                  return j;                  // c7
              }
          }
          return 0;                          // c8
      }
                  
    3. void f3(int n) {
          for (int i = 0;                        // c1
                          i < n;                 // c2
                                 i++) {          // c3
              for (int j = 10;                   // c4
                               j >= 0;           // c5
                                       j--) {    // c6
                  cout << "i = " << i;           // c7
                  cout << ", j = " << j << endl; // c8
              }
          }
      }
                  
  3. (10 points) Will the following C++ function always terminate, for any input? Prove your answer. You should assume for this problem that the int type does NOT wrap around (it can count to any integer, positive or negative).
    int g(int n) {
        int x = g(n - 1);
        if (x > 0) {
            return x + 1;
        } else {
            return 1;
        }
    }
  4. (10 points) Consider a standard binary tree with n nodes, where every node has a pointer to two children, either of which may be NULL. In this tree, are there more NULL child pointers, or non-NULL child pointers? Prove your answer. Remember that n could be any integer greater than zero, so we're not just talking about one particular tree for some fixed n, but ANY tree.
  5. (10 points) Exercise 2.11 in your textbook. For this problem and the next one, consider setting up an equation T(n1)/t1 = T(n2)/t2. Think about what this equation means.
  6. (10 points) Exercise 2.12 in your textbook. For part (b), you will need to use some guess-and-check to find the answer.
  7. (10 points) Exercise 2.29 in your textbook (Hint: the answer has to do with how we perform algorithm analysis).
  8. (10 points) Exercise 3.9 in your textbook. (This problem is near and dear to your professor's heart, because he learned it the hard way when he was in college. He was writing a program that was misbehaving, but it wasn't clear why.)
  9. (10 points) Exercise 3.27 in your textbook (here "stack space" means the "space on the runtime stack" — the stack that stores function calls and local variables).
  10. (10 points) Exercise 3.36 in your textbook. Think outside the box on this one. The answer is simple.

Copyright © 2012 Adam Sealey, based largely on a syllabus by Greg Hamerly .
Computer Science Department
Baylor University

valid html and css