Lecture Notes: Recurrence Relations and Algorithms
Added on 2023-01-13
20 Pages6833 Words97 Views
|
|
|
Lecture Notes
Computational Problem Solving
Week 7:
Recurrence Relations and Algorithms
Contents
Recursive Algorithms............................................................................................................................................. 1
Towers of Hanoi .................................................................................................................................................... 1
Recurrence Relations ............................................................................................................................................ 5
Second Order Linear Homogeneous Recurrence Relations .................................................................................. 8
Application: Fibonacci and Lucas Recurrence Relations ....................................................................................... 9
Extension Topic: General Homogeneous Recurrence Relations ......................................................................... 11
Extension Topic: Non-homogeneous Recurrence Relations ........................................................................... 12
Recursion in Python ............................................................................................................................................ 13
Recursive Algorithms
Recursive algorithms are those that call themselves. For example, to find the factorial of an integer is:
5! = 5 × 4 × 3 × 2 × 1
And more generally as:
𝑛! = 𝑛 × (𝑛 − 1) × (𝑛 − 2) × ... × 3 × 2 × 1
As (𝑛 − 1)! = (𝑛 − 1) × (𝑛 − 2) × ... × 3 × 2 × 1 we can rewrite the above as:
𝑛! = 𝑛 × (𝑛 − 1)!
Where 1! = 1 as a base condition. As we can see recursive algorithms have similar ideas to what we used to
prove statements by mathematical induction.
Towers of Hanoi
This involves n discs of various sizes on three posts
Computational Problem Solving
Week 7:
Recurrence Relations and Algorithms
Contents
Recursive Algorithms............................................................................................................................................. 1
Towers of Hanoi .................................................................................................................................................... 1
Recurrence Relations ............................................................................................................................................ 5
Second Order Linear Homogeneous Recurrence Relations .................................................................................. 8
Application: Fibonacci and Lucas Recurrence Relations ....................................................................................... 9
Extension Topic: General Homogeneous Recurrence Relations ......................................................................... 11
Extension Topic: Non-homogeneous Recurrence Relations ........................................................................... 12
Recursion in Python ............................................................................................................................................ 13
Recursive Algorithms
Recursive algorithms are those that call themselves. For example, to find the factorial of an integer is:
5! = 5 × 4 × 3 × 2 × 1
And more generally as:
𝑛! = 𝑛 × (𝑛 − 1) × (𝑛 − 2) × ... × 3 × 2 × 1
As (𝑛 − 1)! = (𝑛 − 1) × (𝑛 − 2) × ... × 3 × 2 × 1 we can rewrite the above as:
𝑛! = 𝑛 × (𝑛 − 1)!
Where 1! = 1 as a base condition. As we can see recursive algorithms have similar ideas to what we used to
prove statements by mathematical induction.
Towers of Hanoi
This involves n discs of various sizes on three posts
The disc starts on one of the posts with the largest disc on the bottom of the stack, with the smaller discs
resting on top of a larger disc, so ordered with respect to size.
The exercise is to move all the discs to another post, with the largest on the bottom and the smallest on top
without a larger disc resting on a small disc.
The question is: what is the minimum number of moves needed?
Understanding the Problem:
Objective:
Place the pile of discs on a different peg
Constraints:
- no disc can sit on a smaller disc
- only top disc may be moved
- you can only move one disc at a time
We are being asked to work out the minimum number of moves to move the discs from one peg to another.
We could build a model of the problem (as it was originally in Vietnam). Or we can use diagrams to help us
model the moves. We cannot really restate the problem.
The unknown is the minimum number of moves as well as the number of discs. Also, we are not sure how we
can make those moves to obtain the minimal number of moves. We have not made any assumptions apart
from the constraints of the problem and that there are a fixed number of pegs which is 3 (i.e. we are not
generalising the number of pegs).
Devising a Plan
We haven’t solved this problem before. However, we have looked at noughts and crosses. In that problem we
broke it down by seeing what happens if we add an extra column or row.
We can do a similar approach here too. We can look at the number of moves for 1 disc, 2 discs, etc to see if
we can build up a pattern.
We can then look to see how we make those moves for 2 discs, 3 discs to see what happens if we add a disc
to the source peg. We already said in part (1) that we can use diagrams to help us.
We haven’t left anything out from the problem statement. To move three discs, we may find via trial and
error:
resting on top of a larger disc, so ordered with respect to size.
The exercise is to move all the discs to another post, with the largest on the bottom and the smallest on top
without a larger disc resting on a small disc.
The question is: what is the minimum number of moves needed?
Understanding the Problem:
Objective:
Place the pile of discs on a different peg
Constraints:
- no disc can sit on a smaller disc
- only top disc may be moved
- you can only move one disc at a time
We are being asked to work out the minimum number of moves to move the discs from one peg to another.
We could build a model of the problem (as it was originally in Vietnam). Or we can use diagrams to help us
model the moves. We cannot really restate the problem.
The unknown is the minimum number of moves as well as the number of discs. Also, we are not sure how we
can make those moves to obtain the minimal number of moves. We have not made any assumptions apart
from the constraints of the problem and that there are a fixed number of pegs which is 3 (i.e. we are not
generalising the number of pegs).
Devising a Plan
We haven’t solved this problem before. However, we have looked at noughts and crosses. In that problem we
broke it down by seeing what happens if we add an extra column or row.
We can do a similar approach here too. We can look at the number of moves for 1 disc, 2 discs, etc to see if
we can build up a pattern.
We can then look to see how we make those moves for 2 discs, 3 discs to see what happens if we add a disc
to the source peg. We already said in part (1) that we can use diagrams to help us.
We haven’t left anything out from the problem statement. To move three discs, we may find via trial and
error:
Following a similar strategy, we may find the number of ways to move the discs when we have 2, 3, 4, etc
discs.
Number of discs Number of moves breakdown
1 1 1
2 3 1 + 1 + 1
3 7 3 + 1 + 3
4 15 7 + 1 + 7
5 31 15 + 1 + 15
Generalising this, we may find the number of moves is:
(number of moves for 𝑛 − 1 discs) + 1 + (number of moves for 𝑛 − 1 discs)
Alternatively, we may note that the number of moves is one less than a power of 2. Therefore, the number of
moves is 2𝑛 − 1. Hence given 𝑛 discs on a peg it will take 2𝑛 − 1 moves (minimum) to move the discs from
one peg to another peg given the constraints. But, how do we make those moves? This is where the first
strategy proves helpful. To write an algorithm for Tower of Hanoi, first we need to learn how to solve this
problem with lesser amount of discs, say → 1 or 2. We mark three towers with
name, source, destination and aux (only to help moving the discs). If we have only one disc, then it can easily
be moved from source to destination peg.
If we have 2 discs −
• First, we move the smaller (top) disc to aux peg.
• Then, we move the larger (bottom) disc to destination peg.
• And finally, we move the smaller disc from aux to destination peg.
If we then say that the larger (bottom) disc is the rest of the discs and using the relationship between the
number of moves: number of moves for 𝑛 − 1 discs) + 1 + (number of moves for 𝑛 − 1 discs), we can form a
generalised strategy.
discs.
Number of discs Number of moves breakdown
1 1 1
2 3 1 + 1 + 1
3 7 3 + 1 + 3
4 15 7 + 1 + 7
5 31 15 + 1 + 15
Generalising this, we may find the number of moves is:
(number of moves for 𝑛 − 1 discs) + 1 + (number of moves for 𝑛 − 1 discs)
Alternatively, we may note that the number of moves is one less than a power of 2. Therefore, the number of
moves is 2𝑛 − 1. Hence given 𝑛 discs on a peg it will take 2𝑛 − 1 moves (minimum) to move the discs from
one peg to another peg given the constraints. But, how do we make those moves? This is where the first
strategy proves helpful. To write an algorithm for Tower of Hanoi, first we need to learn how to solve this
problem with lesser amount of discs, say → 1 or 2. We mark three towers with
name, source, destination and aux (only to help moving the discs). If we have only one disc, then it can easily
be moved from source to destination peg.
If we have 2 discs −
• First, we move the smaller (top) disc to aux peg.
• Then, we move the larger (bottom) disc to destination peg.
• And finally, we move the smaller disc from aux to destination peg.
If we then say that the larger (bottom) disc is the rest of the discs and using the relationship between the
number of moves: number of moves for 𝑛 − 1 discs) + 1 + (number of moves for 𝑛 − 1 discs), we can form a
generalised strategy.
Approach:
• Recursively Move N-1 disc from source to Auxiliary peg.
• Move the last disc from source to destination.
• Recursively Move N-1 disc from Auxiliary to destination peg
The steps to follow are:
Step 1 − Move n-1 discs from source to aux
Step 2 − Move nth disc from source to dest
Step 3 − Move n-1 discs from aux to dest
From which we can produce pseudo-code to solve the Towers of Hanoi
problem.
START Procedure Hanoi(disc, source, dest, aux)
IF disc == 1, THEN
move disc from source to dest
ELSE
Hanoi(disc - 1, source, aux, dest) // Step 1
move disc from source to dest // Step 2
Hanoi(disc - 1, aux, dest, source) // Step 3
END IF
END Procedure STOP
Which, in Python, is:
def TowerOfHanoi(n , source, destination, auxiliary):
if n==1:
print ("Move disc 1 from source",source,"to destination",destination)
return
TowerOfHanoi(n-1, source, auxiliary, destination)
print ("Move disc",n,"from source",source,"to destination",destination)
TowerOfHanoi(n-1, auxiliary, destination, source)
# test code
n = 4
TowerOfHanoi(n,'A','B','C')
# A, C, B are the name of rods
To test this, we may look at the solutions or prove it via induction.
For the Tower of Hanoi, we have the number of moves, 𝑆𝑛 is 𝑆𝑛 = 2𝑛 − 1 for 𝑛 discs, this is our 𝑃(𝑛).
• Recursively Move N-1 disc from source to Auxiliary peg.
• Move the last disc from source to destination.
• Recursively Move N-1 disc from Auxiliary to destination peg
The steps to follow are:
Step 1 − Move n-1 discs from source to aux
Step 2 − Move nth disc from source to dest
Step 3 − Move n-1 discs from aux to dest
From which we can produce pseudo-code to solve the Towers of Hanoi
problem.
START Procedure Hanoi(disc, source, dest, aux)
IF disc == 1, THEN
move disc from source to dest
ELSE
Hanoi(disc - 1, source, aux, dest) // Step 1
move disc from source to dest // Step 2
Hanoi(disc - 1, aux, dest, source) // Step 3
END IF
END Procedure STOP
Which, in Python, is:
def TowerOfHanoi(n , source, destination, auxiliary):
if n==1:
print ("Move disc 1 from source",source,"to destination",destination)
return
TowerOfHanoi(n-1, source, auxiliary, destination)
print ("Move disc",n,"from source",source,"to destination",destination)
TowerOfHanoi(n-1, auxiliary, destination, source)
# test code
n = 4
TowerOfHanoi(n,'A','B','C')
# A, C, B are the name of rods
To test this, we may look at the solutions or prove it via induction.
For the Tower of Hanoi, we have the number of moves, 𝑆𝑛 is 𝑆𝑛 = 2𝑛 − 1 for 𝑛 discs, this is our 𝑃(𝑛).
End of preview
Want to access all the pages? Upload your documents or become a member.
Related Documents