Jan 6, 2000

A Maze

Random’s Solution path

Claim: always have a path from startNode to currNode

à currNode=exitNode, we have a solution

Proof by Induction

Restatement: after i moves

Base case:

0 moves (currNode=startNode)

Induction step:

have path for i moves

prove for i+1 moves.

Depth First Search is “Backtracking”

Memory usage and Locality


Claim: always have a path from startNode to currNode
	à currNode=exitNode, we have a solution
Proof by Induction
	Restatement: after i moves
	Base case:
		0 moves (currNode=startNode)
	Induction step:
		have path for i moves
		prove for i+1 moves.