SUNY Geneseo Department of Computer Science

Introduction to Recurrence Relations

Previous Lecture

Misc

First hour exam next Thursday (Oct. 7)

• 3 - 5 short-answer questions
• Covers all material to that point (e.g., object oriented algorithms, experimentation, recursion, induction, recurrences)
• Whole class period
• Open book, notes, computers
• Closed person

I'm out of town (most of) Wednesday through Sunday after Fall break (i.e., gone Oct. 13 through 17).

• Class Thursday, Oct. 14 will be Career Services presentation re what they do, geared to CS people.

Hand out Lab 5

Questions?

Lab exercise to check if a string is a palindrome?

• String that's a palindrome looks like...
  • x y z a ... a z y x
• Palindrome if
  • First char and length-1-th char are equal
  • and rest of the string is a palindrome
  • e.g., "radar"
• Base case: 1-letter string
  • or 0-letter string
• Code

    if length = 0
        return ...
    else if length = 1
        return ...
    else
        compare first and last characters,
        use recursion

• Return boolean expression, e.g.,

    return s.charAt(0) == s.charAt( s.length()-1 )
        && palindrome( s.substring(1,s.length()-1) )

Draw a Check Mark

    // In some subclass of Robot
    drawCheck( int n )
        if n = 1
            this.paint( Yellow )
            turn around
        else
            this.paint( Yellow )
            this.move()
            this.drawCheck( n-1 )
            this.move()
            this.turnRight()
            this.move()
            this.paint( Yellow )
            this.turnleft()

Prove the above correct (i.e., draws check, leaves robot facing "out" of check mark on last tile of diagonal stroke)

• Induction on n
• Base case, n = 1
  • "if n = 1" passes
  • Paint tile robot is on, turns around
  • This leaves a 1-tile checkmark
• Induction hypothesis: assume when n = k-1 >= 1 the algorithm draws a size k-1 checkmark
• Show when n = k, algorithm draws a size k checkmark
  • k >= 2, so "n=1" test fails
  • Robot paints tile it's on
  • Moves forward 1 tile
  • Sends checkmark(k-1)
    • Which draws checkmark of size k-1
  • Then robot moves forward, turns right, moves forward, turns left
    • (which produces a diagonal movement)
  • Robot paints tile it's now on
  • Which competes size k checkmark

Reading Summary

Section 7.2 through "A First Example" in 7.2.2

Recurence relation is a recursive counting technique, can be used to count steps in recursive algorithm

Mathematical functions as examples

Necessities:

• 1 part involves recursion
• Some other part is non-recursive
• Arguments are natural numbers

Closed forms: produce same values as recurrence relations

Prove closed forms using induction

Practice with Recurrences

Example

• f(n) = 7 if n = 0
• f(n) = 3 + f(n-1) if n > 0

Find closed form

When n = 1, f(n) = 3 + f(0) = 3 + 7 = 10

• When n = 2, f(n) = 3 + f(1) = 3 + ( 3 + 7 )

Guess: f(n) = 3n + 7

Prove this:

• Induction on n
• Base case, n = 0
  • f(n) = 7 (from recurrence)
  • = 3 * 0 + 7
• Assume f(k-1) = 3(k-1) + 7
• Show f(k) = 3k + 7
  • f(k) = 3 + f(k-1) (2nd line of recurrence)
  • = 3 + 3(k-1) + 7 (induction hypothesis)
  • = 3k + 7 (algebra)

Next

Recurrence relations and algorithms

Read rest of Section 7.2 (i.e., middle of page 230 through middle of page 238)

Next Lecture