Basic proof techniques

  1. Prove: (forall n in N) n+(n+1)+(n+2)+...+(n+6) is divisible by 7. Don't use induction. Prove a more general statement.
  2.  
  3.  
  4. Explain the following statement. Give a few examples.

    (forall S subset of N)(forall d in N, 1<=d<=|S|)(exists S'={s1,...,sk} a non-empty subset of S)(d divides s1+...+sk).

    (Hard: Prove it. Use the pigeonhole principle, you might have seen this in 102).
  5. (Hard:) Prove by contradiction that there is no way to arrange the digits 0 to 9 into numbers such that the sum of the numbers is 100. Example: 10+23+4+58+6+7+9=117 0+1+2+3+4+5+6+7+8+9=45

Simple Induction

  1. How do you determine whether to use Simple Induction or Complete Induction to prove (forall n in N)P(n)
  2. Prove: (forall n in N) n^2+n is divisible by 2
  3. Prove: (forall n in N) n+(n+1)+(n+2)+...+(n+6) is divisible by 7.
  4. Prove: (forall n in N) n is even <=> n^2 is even
  5. Prove: (forall n in N) 1^2+2^2+...+n^2=n(n+1)(2n+1)/6
  6. Derive and prove a formulae for the total number of squares on an n by n checkerboard.

Complete Induction

  1. Say you have an unlimited quantity of 3 and 4 cent stamps. Prove that you can make every amount above 5. Remember to use complete induction. Bonus: Prove this by simple induction as well.
  2.  
  3.  
  4.  
  5.  

Well Ordering

  1. Pick a few simple and complete induction questions and redo them using well ordering.

Definition by Induction (Functions)

  1. Let f(n)=0+1+...+n. Define f inductively.
  2. Let f(n)=n^2. Define f inductively.
  3.  
  4.  
  5.  

Definition by Induction (Sets) = Structural Induction

  1. Let T={n in N: n is a multiple of 3}
  2. Let S={a^nb^(2n):n in N}. So for example, epsilon, abb, aabbbb, aaabbbbbb in S. Define S inductively.
  3. Let poly(x) be the set of real polynomials over x. So for example, x^2, 3x+5x^2, 7, 75x^{32}+3x^2-5x^5+23x^2 in poly(x). Note: Both exponents and coefficients can be real numbers. Define poly(x), the polynomials over x by induction. Let poly(x) be the smallest set satisfying ... BASE CASE: ... INDUCTIVE STEP:...
  4.  
  5.  

O, Omega, Theta, Running times and Recurrences

  1. Let f(1)=1, f(2)=2, f(n)=3f(n-1)-2f(n-2), if n>2. Investigate f(n) and propose a simple expression for f(n) and prove your expression is correct. What kind of induction will you use?
  2. Write down and prove a big O expression for 1000n^3+2n^4
  3. What is the worst case running time for the following function? Write down and prove a good O() expression for this. #pre: n in N, n>=1 def f(n): if n<=1: return 0 else: return 1+f(n/2) # this is integer division #post: ?
  4.  
  5.  
  6. Is 2^n in O(n!) or is n! in O(2^n)? Prove your result. This may involve an induction proof.

The Master Theorem

  1. Use the Master Theorem to come up with a Theta for the following { 5 if n <= 3 T(n) = { { 2 T(ceil(n/2)) + T(floor(n/2)) + n if n > 3
  2.  
  3. Use the Master Theorem to confirm your answer in O, Omega, Theta, Running times and Recurrences question 3.
  4.  
  5.  
  6.  

Proving Recursive Programs Correct

Prove the following programs correct...
  1. #pre: n in N def w(n): if n==0: return 0 else: return 2n-1+w(n-1) #post: w(n)=n^2
  2. #pre: def r(n): if n==0: return "up" elif n==1: return r(n-1)+"down" else: return r(n-1)+r(n-1) #post:
  3. Prove this one by induction on s #pre: def st(s,n): if s==0: return n else: return st(s-1, n-1) #post:
  4. #pre: def d(n): if n<=0: return 0 else: return 1+d(n-7) #post:
  5.  
  6.  

Proving Iterative Programs Correct

Come up with pre, post and inv for the following and prove the programs correct.
  1. i=0 #preW: while(i<n): #invW: s=s-1 i=i+1 #postW: s=?
  2. i=0 #preW: while(i<n): #invW: i=i+7 #postW: i=?
  3. q=0 r=n #preW: n>=0, q=0, r=n, d>0 while(d<=r): #invW: q=q+1 r=r-d #postW: n=dq+r and 0<=r<d
  4. def aria(n): i=0 #preW1: while(i<=n): #invW1: j=n #preW2: while(j>=0): #invW2: print "("+str(i)+","+str(j)+")" j=j-1 #postW2: i=i+1 #postW1: #Bonus: change j=j-1 to j=j/3 (integer division) # prove correctness of the modified program. Is it still correct? # what is the running time of this, of the modified program (careful)?
  5. Remember the solution to the search sorted array problem from csc148 Consider the following program: 10 25 30 55 99 9 23 27 30 80 ^ 8 17 26 27 80 | 5 14 22 23 70 | 2 3 15 16 18 | increasing---> def search_sorted_array(t, v): """ return True if v appears in sorted array t return False otherwise """ dim = t.get_dimension() x = 0 y = dim - 1 is_found=False while x<dim and y>=0: value_at_xy = t.get(x, y) if v>value_at_xy: x += 1 elif v<value_at_xy: y -= 1 else: is_found=True return is_found Prove search sorted array correct. Use the measure of progress you define in the search_sorted_array while loop to determine the worst case running time for search_sorted_array.

Proving Programs Correct

Write down pre and post conditions and loop invariants for appropriate parts of the code. Define the notion of progress for the while loop which could be used to prove that the loop terminates. Finally outline the proof of correctness. # The nestingDepth of T is the number of # lists containing the most deeply nested member of T. def nestingDepth(T): max_depth=0 if type(T) is list: i=0 while(i<len(T)): depth=nestingDepth(T[i])+1 if depth>max_depth: max_depth=depth i=i+1 return max_depth L=[5,[2], [2, [3]], [2,[3, [1,2,[8]],[5]]] ] for T in L: print T, nestingDepth(T)

Regular Languages (formal, python/perl, DFSA )

Remember that to show that a language is regular, it is enough to give a DFSA or a Regular Expression. Show that the following are regular by giving a formal regular expression, a python/perl regular expression and a DFSA
  1. L={x in {0,1}*: x has an odd number of 1's}.
  2. L={x in {0,1,2,3}*: the symbols in x appear in order}.
  3. L={x in {0,1,2,3}*: Every 0 is next to a 1 and vice versa. Every 2 is next to a 3 and vice versa.}. For example: 011001231320132 is not in L since the 1 in ...23132... does not appear next to a 0.
  4.  
  5.  

Proving DFSA correct

  1. Prove your DFSA above correct

The Pumping Lemma

Show that the following languages are not regular by using the pumping lemma.
  1. L={0^n1^n: n in N}
  2. L={x in {a,b,c}*: a appears most frequently in x}
  3.  
  4.  
  5.  
  6. L={x in {0,1}*: |x| is a perfect square}