## Transcribed Text

Consider the recurrence relation an = C1an-1 + C2an-2 + c3an-3 for 72 Assume that to,
I1
and
.2 are the roots of the characteristic equation x3 - - - C3 = 0.(So,
- - - x2) = -33-422 - C2.T - c3=0). =
Proof (without using a theorem) that an = is a solution of this recurring relation, if and only if To is a
multiple zero point of the characteristic equation. So, T1 = To and/or T2 =xo
2.
Solve the following recurrence relations. You can always reuse the already found results/outcome of
previous sections concerning homogeneous solution and particular solution.
a) an = 3an-1 - 2 with ao = 2 and a1 = 3
b) an = 3an-1 - 2an-2 - 1 for n >2 with ao = 2 and a1 = 4
c)n = 3an-1 - 2an-2 + 2" for n >2 with ao = 2 and a1 = 7
d)an = 3an-1 - 2an-2 + 2n - 1 for n >2 with ao = 2 and a1 = 8
3.
Solve the following recurrence relation using of the generated function.
b) an = 3an-1 - 2an-2 - 1 for 72 >2 with ao = 2 and a1 = 4
Show transcribed image text
4.
The Quicksort algorithm is used to sort an array of numbers. We are interested in the average number of
steps On for sorting an array of n numbers.We can tell that:
n-1
=
k=0
for n 2 3,
given is that C0 =C1 = = 0 and C2 = 3, give an expression for On (here may be in appearance,
a sum
but no Ci terms).
5.
A worm sends a clone to 3 computers on the first day, five on the second day and switches off again. There
is a 20% chance that he will find a computer which has an active worm; in this case, nothing happens (whether the
worm is active for one or two days). In 30% of cases the virus scan detects a worm at entry So before he can
transmit for the first time). Of the infected computers, in 50% of cases; the worm will be discovered immediately
after the transmission of the first three clones. Set one or more recurrent relations in order to determine the
number of infected computers (a computer worm that has disabled itself is not infected).
- What baseline data do you need for this?
Hint: It is wise to start with a chart/schedule detailing what happens every period and in what order.
6.
Given is the function:
f (n) = (2 + 0.5v/2) (2+ 2) n + (2 - 0.5v/2 - 2"
Prove dat f(n) is integer for all integers n = O
Show transcribed image text

These solutions may offer step-by-step problem-solving explanations or good writing examples that include modern styles of formatting and construction
of bibliographies out of text citations and references. Students may use these solutions for personal skill-building and practice.
Unethical use is strictly forbidden.