Homework 1

Due Thursday, June 24th @ 8pm

1. Disprove by counterexample: the number of nodes in a tree is always one more than the number of non-leaf nodes.
2. Prove by example: the number of leaf nodes in a tree may be one more than the number of non-leaf nodes.
3. If proof by example is not generally a valid method of proof, why is the above question valid?
4. Prove by contradiction: The only prime number divisible by 2 is 2 itself
5. Prove by induction that 1 * 3 * ... * n is odd for all odd n > 1
6. Prove by induction that n² = (n-1)² + 2n - 1
7. Prove by induction that the number of edges in a non-empty binary tree is always one less than the number of nodes.
8. Prove by induction that 2n + 10 is O(n²)
9. Prove that for even values of n, 1 + 2 + 3 + ... + n = (n + 1) * n / 2
10. Prove that n! is O(nⁿ)

11. Rank the following functions in order of increasing running time (that is, fastest to slowest.) Indicate which (if any) are identical.
    • n²
    • n!
    • log n
    • log log n
    • 2 ^{log n}
    • 5n + 2
    • 2²ⁿ
    • nⁿ
    • n^3/2
    • log (n²)
    • 2¹⁰⁰
12. Give the Big-Oh running time for the following function:

    void f(unsigned int n)
    {
      int k = 0;
      for (int i = 0; i < n; i++)
      {
        for (int j = 0; j < n; j++)
        {
           k += 1;
        }
      }
    }
    

13. Give the Big-Oh running time for the following function:

    void f(unsigned int n)
    {
      int k = 0;
      for (int i = 0; i < n; i++)
      {
        for (int j = 1; j < n; j *= 2)
        {
           k += 1;
        }
      }
    }
    

14. Give the Big-Oh running time for the following function:

    void f(unsigned int n)
    {
      int k = 0;
      for (int i = 1; i < n; i *= 2)
      {
        for (int j = 1; j < i; j *= 2 )
        {
           k += 1;
        }
      }
    }
    

15. Give the Big-Oh running time for the following function:

    void f(unsigned int n)
    {
      if (n == 1) return;
      f(n / 2);
      f(n / 2);
    }