SUNY Geneseo Department of Computer Science

Another Induction Example

{Date}

CSci 141, Fall 2003
Prof. Doug Baldwin

Return to List of Lectures

Previous Lecture

Misc

I'm out of town Friday (Oct. 3)

Class will be a guest presentation by Career Services re where you might go with a CS major/minor/etc

Lab 6 handout will be available in lab tomorrow

Will be an experiment w/ recurrences

Exam 1 is next Friday (Oct. 10)

Basics of design, theory, experimentation, and recursion, induction, recurrences
Open book, open notes, open computer
3 - 5 short-answer questions (algorithms, proofs, paragraphs, etc.)
Whole class period
Sample test will be on Web

Questions?

Homework and test files:

http://cs.geneseo.edu/~baldwin/csci141/fall2003/exercises.html then follow links to files

Induction and non-math algorithms

    forwardAndBack( n )
        if n > 0
            this.move()
            this.forwardAndBack( n-1 )
            this.move()
        else
            this.turnLeft()
            this.turnLeft()

Prove that this moves robot n tiles forward, then back to start, leaves robot facing in opposite of original direction

[Number Tiles w/ Positive Numbers in Front of Robot, Negative Behind]

Induction on n
Base case: n = 0
- Algorithm does 2 turns,
- Therefore robot faces opposite of original direction and hasn't moved, so still on tile 0
Induction step
- Assume forwardAndBack( k-1 )...
  - [ k-1 >= 0 ]
  - Moves robot to tile original+(k-1)
  - Then back to original tile
  - And leaves robot facing in opposite of original direction
- Show forwardAndBack(k)...
  - Moves to tile k,
  - Back to tile 0,
  - Robot faces opposite of original direction
- k > 0, so algorithm does recursive arm
- Moves robot, leaves robot on tile 1
- Sends recursive forwardAndBack(k-1)
  - So robot moves to tile 1+(k-1) = k
  - Comes back to tile 1
  - Faces opposite of original direction
- Finally algorithm moves robot
  - Puts robot on tile 0 because robot was on tile 1 and facing tile 0,
  - And robot facing opposite of original direction
- Therefore robot has moved to tile k,
  - Back to tile 0,
  - And faces opposite of original direction

Proof about halfWayBack

Find a number that describes problem or amount of recursion
# of tiles between robot and wall, i.e., n

[Induction Variable is Distance to Wall]

How does n (induction variable) change?
- Start at k tiles from wall,
- Recursion has k-2 tiles from wall

Next Lecture