Transcript Document

Chapter Five
Recursion and Trees





Recursion
Divide and conquer
Dynamic programming
Trees and tree traversals
Graphs and graph traversals
Please read chapter 5.
Recursive algorithms

What’s the runtime of this algorithm?
int puzzle(int N)
{
if (N == 1) return 1;
if (N % 2 == 0) return puzzle(N/2);
else return puzzle(3 * n + 1);
}
Why is it hard to determine the runtime?
Recursive algorithms need base case and
recursive call(s) (preferably smaller!)
Euclid’s algorithm



Suppose you write a first-class Fraction class
Need to reduce fractions, such as 546/3185
Note that gcd(m,n) = gcd(n,m%n)
gcd(3185,546)
 return 91
gcd(546,455)  return 91
gcd(455,91)  return 91
gcd(91,0) return 91
code?
int gcd(int m, int n) {
if (n == 0) return m;
return gcd(n, m%n);
}
Fractals

What is a fractal?
Koch Snowflake:
how to draw?
2D Fractal Star…
Fractal flowers…
self-similarity at a different level
/kochR {
2 copy ge {dup 0
rlineto }
{
3 dif
2 copy kockR
60 rotate
2 copy kochR
-120 rotate
2 copy kochR
60 rotate
2 copy kochR
} ifelse
pop pop
} def
0 0 moveto
27 81 kochR
0 27 moveto
9 81 kochR
0 54 moveto
3 81 kochR
0 81 moveto
1 81 kochR
stroke
Divide and Conquer



Split a problem into smaller subproblems
Solve the subproblems recursively
Merge the subproblem solutions into a solution to
the whole problem
The great point is to learn to solve a problem in
terms of subproblem solutions.
Divide and Conquer Examples








Merge sort
Binary Search
Towers of Hanoi
Parsing HTML, XML
pow(x,n)
log(n,base)
log*(n)
Point-in-convex-polygon
Min & Max



Given a set of n items, find the min and max. How many
comparisons needed?
Simple alg: n-1 comparisons to find min, n-1 for max
Recursive algorithm:
void minmax(int i, int j, int& min0, int& max0)
if (j<=i+1) [handle base case; return]
m=(i+j+1)/2;
minmax(i,m-1,min1,max1);
minmax(m,j,min2,max2);
min0 = min(min1,min2);
max0 = max(max1,max2);
Recurrence: T(n)=2T(n/2) + 2; T(2)=1
Solution?
1.5 n - 2
Multiplying

How long does it take to multiply two n-bit numbers?
Grade school algorithm:
Runtime?
O(n2)

Recursive algorithm:

How to solve in terms of subproblem solutions?
(a 2n/2 + b)(c 2n/2 + d)
ac 2n + (ad + bc)2n/2 + bd
Recurrence?
T(n) = 4T(n/2) + c n
Improvement:
(a+b)(c+d) = ac + ad + bc + bd
T(n)=3T(n/2) + c n
O(nlg 3)
O(n2)
Fibonacci Numbers






What is the Golden ratio?
Can approximate with Fibonacci numbers.
Mi to km conversion
Pineapple raster, pine cone pattern…
Recursive Fibonacci algorithm?
Runtime Recurrence?
T(1)=1; T(2)=1; T(n) = T(n-1) + T(n-2) + 1

Runtime?
not sure…but at least W(2n/2)

How to improve runtime?


compute bottom-up
or just remember values you’ve already computed
Dynamic Programming



Solve by combining solutions to overlapping
subproblems
Runtime of recursive solution is typically exponential
Make the algorithm efficient:


built a table bottom-up
or memoize
DP Example: Making Change

Making change






Available coin values: v1, v2, v3, …, vk
How to make change totalling C with fewest coins?
Base cases: mincoins(0)=0; mincoins(v1)=1, etc.
Recursive step:
mincoins(n)=min[ 1+mincoins(n-v1),
1+mincoins(n-v2), …, 1+mincoins(n-vk) ]
Runtime recurrence?
How to make this algorithm efficient?


table-based approach
memoization
Algorithm design by
Dynamic Programming
1.
Identify subproblem solutions of interest.
Name them.
coin values v1, v2, …, vn
mincoins(k)=smallest number of coins to totaling k in value
2.
Express solution to whole problem recursively,
in terms of subproblem solutions
mincoins(k) = 1 if k = vi, infinity if k < 1
mincoins(k) = min[mincoins(k-v1), …, mincoins(k-vn) ] + 1
3.
Memoize (or compute bottom-up)
jot down subproblem solutions as you compute them
DP Example: Weird Dice

Given several weird dice. Roll probabilities?

Dice have s1, s2, s3, …, sn sides
Count the number of ways you can roll each roll;
divide by Psk
Base case: rolling die number 1.
What about 2 dice, 3, …?
Subproblem solutions of interest?
Rolls(n,i) = number of ways of rolling n with first i dice
=Rolls(n-1, i-1) + Rolls(n-2,i-1) + … + Rolls(n-sk,i-1)
Rolls(i,1) = 1, i=1..si

Runtime?






O(S sk)
= O(n) if sk <= const.
Knapsack




You are robbing a bank vault. How to maximize take?
Items 1, 2, …, n have values v1, v2, …, vn and integer weights
w1, w2, …, wn
How to maximize take, if you can only carry B lbs?
Subproblems of interest:
maxval(w,k) = best value with weight w, objects a subset of 1..k

Recursive solution?
maxval(w,k) =
max[maxval(w-1,k),maxval(w,k-1), maxval(w-wk,k-1)+vk]
maxval(w,0) = 0
want maxval(B,n)

memoize or compute bottom up
Other Dynamic Programming applications

Not-one strategies
Shortest path
Paragraph wrapping
Matrix chain multiplication
Polygon triangulation

lots of optimization problems…




Graphs and Trees

Graph:
a set V of vertices (or nodes) and a set E of edges, a subset of
VxV

Digraph:
a graph with directed edges

Tree:
a connected, acyclic graph with one node designated as root


Sibling, parent, ancestor, descendent
External node:
“dummy” node or null pointer

Leaf:
a node with only external nodes as children
Graphs
Binary Trees

Path:
a list of connected vertices

Height of a rooted tree:
the length of the longest path from the root to a leaf

Binary tree:
a tree where each node has up to 2 children, called “left” and “right”

Complete binary tree:
a tree where all the leaves are at the same level

Binary search tree (BST):
a binary tree where the key of any node is greater than the
keys of the nodes in its left subtree and less than those of
its right subtree.
Tree Properties and Traversals

How many edges in a tree of n nodes?
n-1

How many external nodes in a tree of n nodes?
n+1

Height of a binary tree with n nodes?
between lg n and n-1


How can I visit every node of a tree?
Traversals:



preorder
inorder
postorder
Parse Trees


How would one parse an arithmetic expression?
Parse tree:



a node for each operator
leaves for operands
Parse tree traversals:



What does inorder traversal give?
infix expression: (3+4)*(5-6)
Postorder?
postfix expression: 3 4 + 5 6 – *
Preorder?
prefix expression: * + 3 4 – 5 6
Non-recursive Traversals


How to implement a traversal non-recursively?
What kind of traversal is this:
void traverse(link n, void visit(link))
{
STACK<link> s(max);
s.push(n);
while (!s.empty())
{
visit(n = s.pop());
if (n->right != 0) s.push(n->right);
if (n->left != 0) s.push(n->left);
}
}
Graph Traversals


How do you find your way out
of a maze, given a large supply
of pennies?
Graph traversals



Depth-first search
Breadth-first search
Other applications: Boggle™,
tic-tac-toe, path finding,
theorem proving, motion
planning, AI, …
Representing a Graph
Two different drawings of the same graph are shown.

What data structure to represent this graph?
Adjacency Matrix
A B C D
A
1 1 0
B
0 0
C
0
D
E
F
G
H
I
J
K
L
M
E
0
0
0
1
F
1
0
0
1
1
G
1
0
0
0
1
0
H
0
0
0
0
0
0
0
I
0
0
0
0
0
0
0
1
J
0
0
0
0
0
0
0
0
0
K
0
0
0
0
0
0
0
0
0
1
L
0
0
0
0
0
0
0
0
0
1
0
M
0
0
0
0
0
0
0
0
0
1
0
1
Space required for a graph
with v vertices, e edges?
Q(e2)
Time to tell if there is an
edge from v1 to v2?
Q(1)
Adjacency List
A:
B:
C:
D:
E:
F:
G:
H:
I:
J:
K:
L:
M:
F
A
A
E
D
D
A
I
H
K
J
M
J
-> B -> C -> G
->
->
->
->
F
F -> G
E
E
-> L -> M
-> J
-> L
Space required for a graph
with v vertices, e edges?
Q(v+e)
Time to tell if there is an
edge from v1 to v2?
Q(v)
Depth-first Search
Main idea: keep traveling to a new,
unvisited node until you you get stuck.
Then backtrack as far as necessary and try a new path.
DFS: Recursive

How to implement recursively?
void dfs(link n, void visit(link))
{
visit(n);
visited[n]=1;
for (link t=adj[k]; t!=0; t = t->next)
if (!visited[t->v]) dfs(t->v, visit);
visited[n]=2;
}
Runtime?
O(e+v) for e edges, v vertices
Space?
O(v) – a path may be really long
DFS: Non-recursive


How can you implement DFS non-recursively?
Use a stack
void dfs(link h, void visit(link))
{
STACK<link> s(max);
s.push(h);
while (!stack.empty())
if (!visited[n = s.pop()])
{
visit(n); visited[n]=1;
for (link t=adj[n]; t!=0; t=t->next)
if (visited[t->v] == 0) s.push(t->v);
visited[n]=2;
}
}
Breadth-first Search

Breadth-first search:
Visit all neighbors of the start node
(but don’t visit a node you’ve already seen).
Then all neighbors of theirs,
and of theirs,
etc.
Time?
O(v+e)
Space?
O(v)
Breadth-first search


How can you implement BFS?
Use a queue with the DFS algorithm!
void bfs(link h, void visit(link))
{
QUEUE<link> q(max);
q.put(h);
while (!q.empty()])
if (!visited[n = s.pop()])
{
visit(n); visited[n]=1;
for (link t=adj[n]; t!=0; t=t->next)
if (visited[t->v] == 0) s.push(t->v);
visited[n]=2;
}
}
Aside on AI



Will computers ever be intelligent?
Really intelligent?
Tasks that previously were thought to require intelligence:










adding and subtracting
playing chess
driving a car
recognizing speech or handwriting
translating to a foreign language
proving mathematical theorems
What does it mean to say that a computer is intelligent?
Is that the same as being a person? What is a person?
Is a computer program a person?
Is a person a computer program?
Achieving “Intelligence”


How do AI program achieve “intelligent” behavior?
Currently, three main paradigms:



Symbolic knowledge representation and search
Neural Nets
Genetic Algorithms
Search in Artificial Intelligence

Represent your problem as a graph where nodes are
states and edges are operators that go between states





Define problem states (nodes)
Identify start and goal states
Define operators (edges)
Use DFS or BFS to find goal
Example: Missionaries and cannibals problem

states: (3,3,1)  3 missionaries, 3 cannibals, and 1 boat on
left side of river.
Operators: one or two people cross the river in the boat, so
that there isn’t a cannibal majority on either side.
Goal: get to the other side?
Moves?

(331)–(220)–(321)–(210)–(221)–(020)–(031)–(010)–(021)–(000)



DFS/BFS Resource Requirements

DFS:

Runtime?



O(n), n=number of nodes expanded
Space required?
O(d), d = depth of search

Can I cut off a search after 5 seconds?
BFS:

Runtime? O(n)

Space required?
O(breadth of tree) = O(bd), b=branching factor

Can I cut off a search after 5 seconds?
Staged DFS: do a DFS of depth 1, 2, 3, … until out of time

Runtime?
O(n)

Space required? O(d)
Game Playing

We could use DFS but…can’t search whole tree!


limit depth of search and use an evaluation function
We could use DFS but…how do we know which
move the opponent will choose?


minimax algorithm: assume the opponent does what
looks best.
i.e. at nodes where it is the human’s turn, pick the move
that looks best for human. Where computer’s turn, pick the
move that looks best for the computer
Mankalah



An ancient gamed called Kalah or Mankalah uses stones and pits: 6 to
a side and one on each end.
4 stones are initially placed in each side pit. None are in the end pits
(called Kalahs – a player’s kalah is on her right).
A move consists of picking up the stones in a pit and distributing
them, one at a time, in successive pits.


If the last stone is placed in your Kalah, you go again
If the last stone is placed in an empty pit on your side, you capture the
stones in that pit and the opposite one, on the opponent’s side of the
board. These are put into your Kalah.

The game ends when one player has no stones left; the other player
puts all the remaining stones on her side into her Kalah.
Whoever ends with more stones in her Kalah wins.

See the demo program on holmes at /home/hplantin/kalah.c

 Write a smart kalah playing program!
Mankalah minimax
int kalahboard::minimax(depth d):
//semi-pseudocode
if [human won] return –infinity;
if [machine won] return +infinity;
if (d==0) return evaluate();
if (whosemove==HUMAN)
best=+infinity;
for (move=first; move<=last; move++)
kalahboard b=*this;
//duplicate board
if (b.board[move]>0)
//is move legal?
b.makemove(move);
//make the move
v=b.minimax(d-1);
//find its value
if (v<best) best=v; //remember if best
else // similarly for MACHINE’s move
return best;