Midterm Answers

CSC 172

February 23, 2001

All answers in blue books

Meliora

  1. Prove  by induction.

Induction on n.

 

Basis: n=1,

Induction: Assuming  we show

Substituting the induction hypothesis

 

  1. Prove that is  divisible by 7 for every positive integer n.

 

Basis: P(1) : == 8-1 == 7 and 7|7

Induction: Assume: P(n): 7| so or  for some m

                        Show:

                                   

                                   

                                    ==

                                    ==

           

  1. Prove by induction that any amount of postage greater than or equal to 8 cents can be built using only 3-cent and 5-cent stamps. You need to set up the problem mathematically in a form appropriate for an induction proof.

 

 

S(n): "n³8,$ integers x,y Ž n == 5x+3y

 

Basis: Must prove 3 basis cases

S(8): 8 = 5(1)+3(1),

S(9): 9 = 5(0)+3(3),

S(10): 10 = 5(2)+3(0)

 

Induction: S(n+1), assume(via basis) (n+1)³11, So, ((n+1)-3)==(n-2) ³ 8 .

                        Assume(BTIH); S(n-2): (n-2) = 5a+3b

                                    Therefore (n-2)+3= 5a+3b+3

                                                Or (n+1) = 5a+2(b+1)

Big O

 

  1. If n0 = 1, what is the smallest value of c such that n0 and c are witnesses to the fact that (n+2)2 is O(n2)?

c=9

9n2 > n2+4n+4, 9>1+4/n+4/n2

  1. If c=5, what is the smallest non-negative integer n0 such that n0 and c are witnesses to the fact that (n+2)2 is O(n2)?

n0=2

5n2>(n+2)2

5n2>(n2+4n+4)

5>1+4/n+4/n2

 

For Q6-Q8, tell whether the stated big-oh relationship holds. If it does not, you can just say “false”. If the relationship does hold, then you must give witnesses n0 and c.

 

  1. 7n + 50 is O(n2)

Ans: n0=1;c=57. There are many other choices. However, most people who tried something else lost points because they forgot that there is no requirement that c be an integer. Since we were looking for the least c for a given n0, if you, say picked n0=12, you had to say c = 134/144, not c =1

  1. 10n is O(nn)

Ans: n0=10, c=1

  1. 2n3 is O(n2 + n4)

Ans: n0=0,c=1

n2+n4 > 2n3

1+1/n2 > 2/n

 

 

Recursion

 

  1. Anderson numbers are similar to Fibonacci number, but are generated with a slightly different function, as shown below. Write a recursive method which takes in an integer parameter n and returns an integer equal to the nth Anderson number An.
    1. A0 = 0
    2. A1 = A2 = 1
    3. An = An-1 + An-3 for all n >= 3

 

public int A(int n){

      If (n >=3) return (A(n-1) + A(n-3));

      else If (n<0) return –A(-n);

                  else if (n ==0) return 0;

                              else if (n <= 2) return 1;                                   

}

 

 

RUNTIME

Give the run time O(n) for the following code samples

 

  1. int inc = 1;

for (int i=0;i<n;i++) {

            inc *= 2 ;

            if (inc >= n) return;

            for (int j=0;j<n;j += inc)

                        x++;

}

 

Ans: N/2+N/4+… , so O(n)

 

  1. int inc = 0;

for(int i=0;i<n;i++) {

   inc++;

   for (int j=0;j<n;j+=inc)

               x++;

}

 

                        Ans: N+N/2+N/3+…, so O(NlogN)

 

  1. for (int i =0;i< n*n*n;i++)

for(int j =0; j<n*n*n;j++)

x++;

                        Ans: O(N6)

 

 

 

 

 

 

 

 

 

LINKED LISTS

For Q13-Q14, assume the following node class

 

class Node {

      public int i;

      public Node next;

}

 

  1. Write a recursive method to insert a value into an (increasingly) sorted linked list public static Node insert(Node list,int val) multiple entries of the same value are allowed.

 

public static Node insert(list, int val) {

            Node temp;

            if (list == null) {

                        temp = new Node();

                        temp.i = val;

                        temp.next = null;

                        Return temp;

} else

if (list.i < val) {

            list.next = insert(list.next,val);

            return list;

} else {

                        temp = new Node();

                        temp.i = val;

                        temp.next = list.next;

                        list.next = temp;

                        return list;

}

}

 

           

           

                       

           

 

  1. Write a method to reverse a linked list.

 

      public static Node revList(Node n) {

                  if (n.next == null) return n;

                  Node temp = delLast(n);

                  temp.next = revList(n);

                  return temp;

      }

     

      public static Node delLast(Node           n) {

                  Node temp =    n ;       

Node temp2 = null;

                  if (temp ==       null) return null;

                  else if    (temp.next == null)  { return n; }

                  else if    ((temp.next).next == null) {

                              temp2 = temp.next;

                              temp.next = null;

                              return temp2;

                  } else return delLast(temp.next);

      }

 

 

 

 

RECURRENCE RELATIONS

 

            For Q-Q, consider the recurrenc:

                       

                        Basis: T(1) = 0

 

                        Induction:  for integers > 1

 

  1. What are the 5 initial values of T(n)?

 

T(1)=0,T(2)=1,T(3)=1.5,T(4)=1.75,T(5)=1.875

 

  1. Expand the inductive rule so that T(n) is expressed in terms of T(n-2)

 

T(n)=(T(n-2)/4)+3/2

 

  1. Express T(n) in terms of T(n-3)

 

T(n)=(T(n-3)/8)+7/4

 

  1. What is the general pattern? That is, express T(n) in terms of T(n-i).

 

 

  1. For what value of I can we eliminate T(n-i) from the expression?

 

I==(n-1) because T(n-(n-1))==T(1) = 0

 

  1. Use your answer to the previous question to express T(n) as a function of n alone (without any terms involving the function T).