Mathematical Foundation of Computer Science

DHARM 64 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE Substituting P. 2n into the difference equation we obtain, P 2n + 5 P 2n–1 ...

DHARM RECURRENCE RELATIONS WITH CONSTANT COEFFICIENTS 65 NOTE Here f(n) is a constant and accordingly if we assume the general f ...

DHARM 66 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE In general j k nj j k i k i a j j = − = − = ∑∑∑=+ 0 1 0 1 0 CPα 1 () (3.21) ...

DHARM RECURRENCE RELATIONS WITH CONSTANT COEFFICIENTS 67 Difference Equation Numeric Function Generating Function Fig. 3.1 Proce ...

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 ...

DHARM RECURRENCE RELATIONS WITH CONSTANT COEFFICIENTS 69 Algorithm (divide-and-conquer sort) Input: Array S of n elements; k is ...

DHARM 70 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE From the recursion tree shown in Fig. 3.3, we observe that size as a functi ...

DHARM RECURRENCE RELATIONS WITH CONSTANT COEFFICIENTS 71 Let T(n) be the time needed to sort an n-element array. When n ≤ 1, T(n ...

DHARM 72 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE Now analyze the equation (3.30) so we have following statements, if a < ...

DHARM RECURRENCE RELATIONS WITH CONSTANT COEFFICIENTS 73 Example 3.9. Solve the following recurrence T(n) = 8 T(n/2) + n^2 for ...

DHARM 74 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE 3.7 Matrix Multiplication.................................................. ...

DHARM RECURRENCE RELATIONS WITH CONSTANT COEFFICIENTS 75 conclude that for n = 8 Stressman’s method is more efficient. In genera ...

DHARM 76 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE 3.7 Show that the solution of the Fibonacci recurrence i.e., fn = fn–1 + fn ...

ALGEBRAIC STRUCTURE 4.1 Introduction............................................................................................ ...

4.1 INTRODUCTION In the context of algebra a system consisting of a set and one or more n-ary operations on the set is called an ...

DHARM ALGEBRAIC STRUCTURES 79 For example, the additive inverse define the subtraction i.e., x + (– x) = ê. Similarly, the multi ...

DHARM 80 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE Since, Operation is associative and closed, because of, + + = + ∈ X and sim ...

DHARM ALGEBRAIC STRUCTURES 81 Therefore, algebraic system (Σ, .) is a monoid. If we replace the set Σ by Σ+, where Σ+ = Σ* – {ε} ...

DHARM 82 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE Hence, (X, ⊗) is a semigroup. Further, l Algebraic structure (X, ⊗) not pos ...

DHARM ALGEBRAIC STRUCTURES 83 From the result of equality (1), for any x ∈ X, we have the inverse element x–1, where x × x–1 = ...