Mathematical Foundation of Computer Science

DHARM

68 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE

n

n

n

n

n

n

n

n

n

n

az a z a z zn

=

∞

=

∞

−

=

∞

−

=

∞

∑∑ ∑∑++=

22

1

2

2

2

56. (3.24)

Since,

n=

∞

∑

2

anzn = A(z) – a 0 – a 1 ⇒ A(z) – 1 – 2z

n=

∞

∑

2

an–1zn = z(A(z) – a 0 ) ⇒ z(A(z) – 1)

n=

∞

∑

2

an–2zn = z^2 .A(z) ⇒ z^2 .A(z)

and

n=

∞

∑

2

zn = z^2 + z^3 + z^4 ...... ∞⇒1/(1–z) – 1 – z = z^2 /(1–z) ;

putting these values in equation (3.24) and simplified for A(z),

A(z) – 1– 2z + 5z (A(z) – 1) + 6 z^2 A(z) = z^2 /(1 – z) ;

Thus, A(z) = (1+ 6z – 6z^2 )/(1 + 5z + 6z^2 ) (1– z) ;

Equivalent to, A(z) = (1/12)/(1 – z) + (14/3)/(1+2z) + (– 15/4)/(1+3z) ;

Therefore corresponding numeric equation an is,

an = (1/12) .1n + (14/3) (– 2)n – (15/4) (– 3)n ;

3.5 Common Recurrences from Algorithms...........................................................................

The purpose of this section is the study of the recurrence equation obtained from the proce-
dure codes, and describes some commonly occurring patterns from algorithms. Simultane-
ously, you will also find the methods to solve some of the typical recurrence equations obtain
by this way in the next section.
We can describe several categories of recurrence equations that occurs frequently and
can be solved (to some degree) by standard methods. In all cases sub problems refers to a
smaller instance of the main problem and that to be solved by recursive call.
Divide-and-Conquer
Divide-and-Conquer strategy is like modularization approach of the software design. A large
problem instance is divided into two/more smaller instance problems. Solve smaller instance
problems using divide-and-conquer strategy recursively. Finally, combine the solutions of the
smaller instance problems to get the solution of the original problem.
We can apply divide-and-conquer strategy to the sorting problems. Sorting problem is
the problem where we must sort n elements into non decreasing order. The divide-and-con-
quer paradigm suggests sorting algorithms with the following general structure :
If n is one, terminate; otherwise partition the set of elements into two/more subsets;
sort each; combine the sorted subsets into a single sorted set. Let one set gets a fraction n/k of
the elements and other set gets the rest (n – n/k). Now both slices are to be separately sorted
by recursive application of divide-and-conquer scheme. Then it merges the sorted fractions.
The procedure is shown in Fig. 3.2.