### pptx

```Tutorial 11 of CSCI2110
Number of Sequence & Recursion
Tutor: Zhou Hong (周宏)
[email protected]/* <![CDATA[ */!function(t,e,r,n,c,a,p){try{t=document.currentScript||function(){for(t=document.getElementsByTagName('script'),e=t.length;e--;)if(t[e].getAttribute('data-cfhash'))return t[e]}();if(t&&(c=t.previousSibling)){p=t.parentNode;if(a=c.getAttribute('data-cfemail')){for(e='',r='0x'+a.substr(0,2)|0,n=2;a.length-n;n+=2)e+='%'+('0'+('0x'+a.substr(n,2)^r).toString(16)).slice(-2);p.replaceChild(document.createTextNode(decodeURIComponent(e)),c)}p.removeChild(t)}}catch(u){}}()/* ]]> */
Announcement
• HW2 & HW3 has been marked, please pick them up.
• HW4 will be returned in next Monday.
Announcement
• In your homework, you should declare your
cooperators or cite references, this will not affect
– Note: write your OWN solutions, do NOT just copy!
• Fail to do so may be considered as plagiarism.
– The same notation or the same term (e.g. “imaginary women”)
are clues.
Outline
• Number of Sequence
• Setup Recurrence Relations
NUMBER OF SEQUENCE
Warm Up Exercise
What’s the next number?
• a1 = -3, a2 = -1, a3 = 1, a4 = 3, …
• a1 = 3, a2 = 6, a3 = 12, a4 = 24, …
• a1=1, a2=11, a3=21, a4=1211, a5=111221, a6=312211, a7=13112221, …
• This is just for fun = )
Warm Up Exercise (Cont.)
Write down the general formula of ai
• a1 = -3, a2 = -1, a3 = 1, a4 = 3, …
Answer: ai = a1 + (i-1)d = -3 + 2(i-1) = 2i - 5
• a1 = 3, a2 = 6, a3 = 12, a4 = 24, …
Answer: ai = a1 q(i-1) = 3 x 2(i-1)
Write down the closed form of the following partial sum (

=  )
• a1 = -3, a2 = -1, a3 = 1, a4 = 3, …, ai = 2i – 5, …
Arithmetic Sequence:

=
=
+

=
+ −

• a1 = 3, a2 = 6, a3 = 12, a4 = 24, …, ai = 3 x 2(i-1), …
Geometric Sequence:

=
=
(− )
−
=  ×  −
=  −
Warm Up Exercise (Cont.)
Evaluate the following summation (Hint: Telescoping Sum)
•

1
2 +8+3
4
=0
=
1
=
2
1
=
2

1
=0 (2 + 1)(2 + 3)

1
1
−
2 + 3
=0 2 + 1
1
+1
1−
=
2 + 3
2 + 3
Future Value
Given bank rate b unchanged, if we deposit \$X now, how much will
we have after n years?
Now
After 1 Year
After 2 Years
…
After n Years
\$X
\$X * b
\$X * b2
…
\$X * bn
Future Value:
1 dollar today will be worth bn dollars after n years.
Current Value
Given bank rate b unchanged, if we want to have \$X after n
years, how much should we deposit now?
Now
…
After n-2 Years
After n-1 Years
After n Years
\$X / bn
…
\$X / b2
\$X / b
\$X
Current Value:
1 dollar after n years is only worth 1 / bn dollars today.
Mortgage Loan
Suppose the bank rate is b and keeps unchanged. Now, we rise a
mortgage loan of \$X dollars to buy a house. We have to repay the
loan in n years. What is the annual repayment \$p. (assume
repayment is made at the end of each year)
Solution 1: Consider Future Value
Year
Amount to Be Repaid
Now
\$X
1 year
\$X * b - \$p
2 years
(\$X * b – \$p) * b – \$p = \$X * b2 – \$p * b – \$p
…
…
n years
\$X * bn – \$p* bn-1 – … – \$p * b – \$p
In order to repay the loan in n years, we must have
\$ ⋅   − \$
−1
=0
= 0
⇔

1
−

\$ ⋅   − \$
=0
1−
Therefore, in each year, we have to repay
(1 − )
\$ = \$
1 −
Solution 2: Consider Current Value
Year
Current Value of Each Year’s Payment
1 year
\$p / b
2 years
\$p / b2
…
…
n years
\$p / bn
The key observation is that the total current value should equal to \$X.
Let  =
1
,

\$ =

(1
−

)

\$ ⋅  = \$
1−
=1

Therefore, in each year, we have to repay
1−
(1 − )
\$ = \$
= \$

(1 −  )
1 −
RECURSION
Disclaimer: Some of the slides in this section are taken from the slides by Chow Chi Wang,
last year’s Tutor of CSCI2110.
Recursion
• Recursion is an important technique in computer
science. The key idea is to reduce a problem into the
similar problems in simpler cases.
• In this tutorial, we will focus on how to setup the
recurrence relations. We will discuss solving
recurrence relations in next week’s tutorial.
• Tip: After setting up a recurrence relation,
remember to test it’s correctness by trying some
base cases.
Fibonacci Variant
We have a single pair of rabbits (male and female)
initially. Assume that:
– (a) the rabbit pairs are not fertile during their first month
of life, but thereafter give birth to four new male/female
pairs at the end of every month;
– (b) the rabbits will never die.
Let  be the number of pairs of rabbits alive in the -th month.
Find a recurrence relation for 0 , 1 , 2 …
Fibonacci Variant
Initiation
(0 = 1)
Month 1
(1 = 1)
Month 2
(2 = 5)
(3 = 9)
Month 3
Month 4
(4 = 29)
Key:
Baby rabbit pair
Fertile rabbit pair
Fibonacci Variant
• Let  be the number of baby rabbit pairs in the -th
month.
• Let  be the number of fertile rabbit pairs in the -th
month.
Note that we have:
where,
=  +  ,
= −1 + −1 = −1 ,
= 4 ∗ −1 = 4 ∗ −2
Therefore:
= −1 + 4 ∗ −2 for  ≥ 2, and 0 = 1 = 1.
The Josephus Problem
Flavius Josephus is a Jewish historian living in the 1st century.
During the Jewish-Roman war, he and his 40 soldiers were trapped in a
cave, the exit of which was blocked by Romans.
The soldiers chose suicide over capture and decided that they would
form a circle and proceeding around it, to kill every third remaining
person until no one was left.
However, Josephus wanted none of this suicide nonsense.
His task is to choose a place in the initial circle so that he is the last
one remaining and so survive.
The Josephus Problem in General Form
There are n people numbered 1 to n around a circle. Start with people #1,
eliminate every j-th remaining people until only one survives. The task is to
find the survivor’s initial number.
A simple case with n=10 and j=2:
The elimination order: 2, 4, 6, 8, 10, 3, 7, 1, 9.
So, people #5 is the survivor.
The Case of j=2
If n is a even number, we have
J(2k) = 2J(k) – 1, for k >= 1.
If n is a odd number, we have
J(2k+1) = 2J(k) + 1, for k >= 1.
Base case, J(1) = 1.
The General Value of j
Consider eliminating people one by one. In the very beginning, the j-th
people is eliminated, then we start the next count with the j+1-th
people starting with people #1.
J(n-1) is the survivor’s number in the remaining circle of n-1 people,
starting with the j+1-th people in the initial circle.
Then, the survivor is the (J(n-1)+j)-th people starting with people #1
in the initial circle.
Note that, the position of the i-th people in the initial circle is
((i-1) mod n) + 1 , starting with people #1.
Therefore, we have the following recurrence relation
J(1) = 1,
J(n) = ((J(n-1)+j-1) mod n) + 1, for n >= 2.
Comparison of The Two Recurrence Relations
J(1) = 1,
J(n) = ((J(n-1)+j-1) mod n) + 1, for n >= 2.
V. S.
J(1) = 1,
J(2k) = 2J(k) – 1, for k >= 1,
J(2k+1) = 2J(k) + 1, for k >= 1.
Thank You!
Q&A?
```