CS702 Mid Term SolvedMegaFile Khurshid PDF

CS702 Advance Algorithm and Design Khurshid Iqbal [MS160400288]
CS702 MID TERM PAPERS SOLVED
Question: Prove logab . logbc = logac

𝐥𝐨𝐠 𝒂 𝒃 . 𝐥𝐨𝐠 𝒃 𝒄 = 𝐥𝐨𝐠 𝒂 𝒄
Question: Prove 3log4n = nlog43

𝟑𝐥𝐨𝐠𝟒 𝒏 = 𝒏𝐥𝐨𝐠𝟒 𝟑
[Mid Term Solved Questions] 1

Question: Asymptotic Notations Properties
 Categorize algorithms based on asymptotic growth rate e.g. linear, quadratic, polynomial,
and exponential
 Ignore small constant and small inputs
 Estimate upper bound and lower bound on growth rate of time complexity function
 Describe running time of algorithm as n grows to ∞.
 Describes behavior of function within the limit.
Limitations
 Not always useful for analysis on fixed-size inputs.
 All results are for sufficiently large inputs.
Asymptotic Notations
Asymptotic Notations Θ, O, Ω, o, ω
 We use Θ to mean “order exactly”
 O to mean “order at most”
 Ω to mean “order at least”
 o to mean “tight upper bound”
 ω to mean “tight lower bound”

What is Complexity?
The level in difficulty in solving mathematically posed problems as measured by
 The time (time complexity)
 Number of steps or arithmetic operations (computational complexity)
 Memory space required (space complexity)
Major Factors in Algorithms Design

1. Correctness
An algorithm is said to be correct if
• For every input, it halts with correct output.
• An incorrect algorithm might not halt at all OR
• It might halt with an answer other than desired one.
• Correct algorithm solves a computational problem
2. Algorithm Efficiency
Measuring efficiency of an algorithm,
• Do its analysis i.e. growth rate.
• Compare efficiencies of different algorithms for the same problem.

Question:
Prove n2 + n = O(n3)

Question: Prove that 2n2 ϵ O(n3)
Questions: Prove that f(n) = O(g(n))

f(n) ϵ O(g(n)) Big-Oh Notation (O) N log n

Transpose Symmetry
Question: Prove that f(n) = O(g(n)) ⇔ g(n) = Ω (f(n))

Question: Prove that f(n) = o(g(n)) ⇔ g(n) = ω (f(n))

Question: Big-Omega Notation (Ω)

Solution:
If f, g: N → R+, then we can define Big-Omega as
Question: Prove that f(n) = O (g(n)) ↔ g(n) = Ω (f(n)) (Omega)

Solution:

[Little Omega]
Question: Prove that f(n) = o(g(n))  g(n) = ω f(n))
Solution:
Question: Prove that 5.n2 Є ω(n) OR [5n2 Є ω(n)]

[Little Omega]
Question: Prove that 5.n + 10 ∉ ω(n) OR [5n + 10 ∉ ω(n)]
Question: Prove that 100.n ∉ ω(n) OR [100n ∉ ω(n)]

Question: For all integers a and b and any nonnegative integer n,
gcd(an, bn) = n gcd(a, b).
Proof
If n = 0, the corollary is trivial.
If n > 0, then gcd(an, bn) is the smallest positive element of the set {anx
+ bny},
i.e.
gcd(an, bn) = min {anx + bny}
= min{n.{ax + by}}
= n. min{ax + by}
n times smallest positive element of set {ax + by}.
Hence gcd(an, bn) = n.gcd(x, y)

Solving Modular Linear Equations

Question: A congruence of the form ax ≡ b (mod m) is called a linear
congruence.
Solving:
• To solve this congruence, objective is to find the x that satisfy the given equation.
• An inverse of a, modulo m is any integer a′ such that, a′a ≡ 1 (mod m).
• If we can find such an a′, then we can solve ax ≡ b by multiplying throughout by it,
giving a′ax ≡ a′b,
• Thus, 1·x ≡ a′b,  x ≡ a′b (mod m).
Question: Proof by Induction Prove that n2 ≥ n + 100 ꓯ n ≥ 11

Solution
Let P(n) * n2 ≥ n + 100 ꓯn ≥ 11
1. P(11) * 112 ≥ 11 + 100 121 ≥ 111, which is true
2. Suppose predicate is true for n = k, i.e.
P(k) * k2 ≥ k + 100, true k ≥ 11
3. Now it can be proved that
P(k+1) * (k+1)2 ≥ (k+1) + 100,

k2 + 2k +1 ≥ k +1 + 100
k2 + k ≥ 100 (by 1 and 2)
Hence P(k) ≥ P(K+1)

Question: If n Є Z, n >1, then n can be written as Product of Primes.

Question: Property: Totient Function
Prove that (p.q) = (p-1).(q-1), where p and q are prime numbers
Proof
If n = p, a prime number, then (p) = (p-1); e.g. ((7) = 6 because 7 is prime)

If n = p * q where p and q are both prime then (n) = (p*q)
As above (p) = p - 1
Similarly (q) = q - 1
For (n) = (p*q), the residues will be
S1 = {0, 1, 2,. . ., (pq-1)}
Out of S1, residues that are not relatively prime to n:
S2 = {p, 2p, ….(q-1)p}, S3 = {q, 2q,……(p-1)q}, S4 = {0}
The number of elements of S1 = pq
The number of elements of S2 = q-1
The number of elements of S3 = p-1
The number of elements of S4 = 1
Hence number of relatively prime elements in S1 is
(n) = pq – [(q-1)+(p-1)+1]
= pq – q + 1 – p + 1 -1
= pq – q – p + 1 = (p-1)(q-1) = (p) * (q)

Lemma:
Question: For any integer n and any prime number p, if p divides n then p does not
divide n + 1
Proof

Question: Lemma Statement:
The square of an odd integer is of the form 8m + 1 for some integer m.
• Suppose n is an arbitrary odd integer.
• By quotient remainder theorem any integer has the form
4m, 4m + 1, 4m + 2 OR 4m+3
• Now since n is an odd integer, hence n can be represented as
4m + 1 OR 4m+3
• Now we have to prove that squares of 4m + 1 and 4m + 3 are of the form
8m + 1.
Case 1
Square of 4m + 1
(4m + 1)2 = 16m2 + 8m + 1 = 8(2m2 + m) + 1
= 8m’ + 1, where m ‘ = (2m2 + m)
Case 2
Square of 4m + 3
(4m + 3)2 = 16m2 + 24m + 9 = 8(2m2 + 3m + 1) + 1
= 8m’’ + 1, where m’’ = (2m2 + 3m + 1)
• Hence any odd integer has the form 8m + 1 for some m

Question: Lemma : Statement
If n Є N, n > 1 is not prime then n is divisible by some prime number
p ≤ square root n i.e. p ≤ √𝒏.

Proof
• Since n is not prime hence it can be factored as
n = x.y where 1 <x ≤ y <n
• x or y is a prime, if not it can be further factored out.
• Also suppose without loss of generality that x ≤ y
• Now our claim is that x ≤ √𝒏
• This is because otherwise x.y > n, a contradiction
• We only require to check till √𝒏 for primality test.
Question: Theorem
Prove, by mathematical induction, that computational cost of generating
permutations is n!.
Proof
• If n = 1, then the statement is true, because 1! =1
• If there are k elements in set then number of permutation = k!
• If we add one more element in any of the permutations, there will be k+1
number of ways to add it, resulting k+1 no. of permutations.
• Now total number of permutations = k!(k+1) = (k+1)!
• Hence true for all n.

Question: Theorem
Statement: If a and b are any integers, not both zero, then gcd(a, b) is the smallest
positive element of the set {ax + by : x, y  Z} of linear combinations of a and b.
Proof
Let s be the smallest positive such linear combination of a and b, i.e.
s = ax + by, for some x, y Є Z
By quotient remainder theorem
a = qs + r = qs + a mod s, where q = ⌊a/s⌋.
a mod s = a – qs = a - q(ax + by) = a (1 - qx) + b(-qy)
• Hence a mod s is a linear combination of a and b.
• But, since a mod s < s, therefore, a mod s = 0
• Now a mod s = 0 ⇒ s | a
• Similarly we can prove that, s | b.
• Thus, s is a common divisor of both a and b,
• Therefore, s  gcd(a, b) (1)
• We know that if d | a and d | b then d | ax + by for all x, y integers.
• Since gcd(a, b)| a and gcd(a, b) | b, hence gcd(a, b) | s and s > 0 imply that
gcd(a, b) ≤ s (2)
• By (1) and (2) proved that gcd(a, b) = s

Question: Prove that 5.n2 ϵ Ω(n) (Omega n)

Solution:

Question: n3 + 4n2 = Ω(n2) [Omega]

Question: Prove that 100.n + 5 ∉ Ω (n2) OR 100n + 5 ∉ Ω (n2) [Omega]
Question: From asymptotic notation prove Theeta function / Theeta

Notation (Θ)
Solution

Question: Prove that 1/2.n2 – 1/2.n = Θ(n2) OR [1/2 n2 – 1/2n]

[Theeta]
Theeta
Question: Prove that a.n2 + b.n + c = Θ(n2) OR [an2 + bn + c]
Where a, b, c are constants and a > 0

Theeta
Question: Prove that 2.n2 + 3.n + 6 = Θ (n3) [2n2 + 3n + 6]
Solution:

Question: Prove that n2 Є O(n2)
Question: Prove that 1000.n2 + 1000.n Є O(n2)

Question: Prove that n3 Є O(n2)
Question: Prove by contradiction that g(n) = n3 is not O(n2)
Assume that g(n) is O(n2 ). Then there are positive reals c

and k such that
| n3 | ≤ c|n2 |, for all n ≥ k.
Without loss of generality, we can assume that n2 is non-
zero.
So then, dividing by n2 we have n ≤ c.
But this is going to fail for those values of n that are bigger
than c.
Contradiction! Thus, g(n) = n3 is not O(n2 ).

3 4
Questions: Prove that 2.n + 3.n + 10 ∈ O (n )
Solution 2
2n 3  3n  10  O ( n 4 )
let suppose f(n)=2n 3  3n  10 and g(n)=n 4
f ( n)  O ( g ( n)) ?
we have to find c1 and n 0  n  n 0
0  2n 3  3n  10  cn 4
let c1  1 we need to n 0 for which above is true
testing different values from 1 to onward
2(3)3  3(3)  10  34
73  81
hence c=1 for  n  3
hence f ( n)  O ( g ( n))  2n 3  3n  10  O ( n 4 )
c=1 for  n  3

Question: Prove that 5.n + 10.n + 16  Θ(n )
2 2
(Theeta)
5n2 + 10n + 16  Θ(n2)
Solution:
In order to prove the given Theta () notation, consider the following
Suppose
f(n) = 5n2 + 10n + 16 and g(n) = n2
On contrary assume that f(n)   (g(n)) i.e. there are some positive constants c1, c2 and n0 such that:
c1.g(n) ≤ f(n) ≤ c2.g(n) ꓯ n ≥ n0
0 ≤ c1g(n) ≤ f(n) ≤ c2g(n)
⇒ c1n2 ≤ 5n2 + 10n + 16 ≤ c2n2 [1]
Now, consider for c1 = 5 and find n0, which is true for the above
Let n0 = 1, so we have
5(1) ≤ 5(1) + 10(1) + 16 ⇒ 5 ≤ 31
𝐻𝑒𝑛𝑐𝑒 c1 = 5 ꓯn≥1
Now taking c2 = 6, and find n0, for this above [1] is true
5n2 + 10n + 16 ≤ 6n2
For n = 1 ⇒ 5 + 10 + 16 ≤ 6
⇒ 31 ≤ 6 [test is failed for n = 1]
For n = 2 ⇒ 5(4) + 10(2) + 16 ≤ 6(4)
⇒ 56 ≤ 24 [test is failed for n = 2]
.
.
.
By testing the different values in [1] starting from 1 to onward, find that n0 = 12 as
For n = 12 ⇒ 5(144) + 10(12) + 16 ≤ 6(144)
⇒ 856 ≤ 864
𝐻𝑒𝑛𝑐𝑒 c2 = 6 ꓯ n ≥ 12
Finally is proved that f(n)   (g(n)), therefore 5n2 + 10n + 16  (n2)

Question: Little-o Notation

o-Notation is used to denote a upper bound that is not asymptotically tight.
Question: Prove that 2n2 ϵ o(n3) [Little o]

Little-o Notation
Question: Prove that n2 ∉ o(n2)
Question: Prove that 1000.n2 + 1000.n ∉ o(n2)

Question: Let N be a set of natural numbers. The symbols, < (less than), ≤ (less than or equal)
and = (equal) are relations over N. Prove or disprove the following.
1. < is reflexive, symmetric and transitive
2. ≤ is reflexive, symmetric and transitive
3. = is reflexive, symmetric and transitive
Solution:
1. < is reflexive, symmetric and transitive?
Reflexive:
A binary relation R on a set A is said to be reflexive if
(x, x) Є R, for all x Є A.
‘<’ Relationship is not reflexive.
Example:
x < x is not possible.
Symmetric:
A relation R between the elements in a universal set is called symmetric when x
R y always implies y R x; in other words, when R is symmetric it does not
matter whether x is written first or y is written first in the expression x R y.
‘<’ Relationship is not symmetric.
Example:
If x < y then y < x is not possible.
Transitive:
A relation R between the elements in a universal set is called transitive when x
R y and y R z always imply x R z.
‘<’ is transitive.
Example:
If x < y and y < z; then x < z is true.

2. ≤ is reflexive, symmetric and transitive?

Reflexive:
‘≤’ Relationship is reflexive.
Example:
x ≤ x is true.
Symmetric:
‘≤’ Relationship is not symmetric.
Example:
If x ≤ y then y ≤ x is not possible for x < y.
Transitive:
‘≤’ Relationship is transitive.
Example:
If x ≤ y and y ≤ z; then x ≤ z is true.

3. = is reflexive, symmetric and transitive

Reflexive:
‘=’ Relationship is reflexive.
Example:
x = x is true.
Symmetric:
‘=’ Relationship is symmetric.
Example:
If x = y then y = x is true.
Transitive:
‘=’is transitive.
Example:
If x = y and y = z then x = z is true.

Question: Use the logical equivalences above to show that ¬(p ∨ ¬(p ∧ q)) is a
contradiction.
¬ (p ∨ ¬ (p ∧ q))
Question: Proof by Contradiction [B ∧ (B ⇒ C)] ⇒ C

Question: Prove that ¬ B → ¬ (A ˄ (A → B)) by
a) Logical Equivalence b) Rules of Inference c) Contradiction
Answer
(a) Prove by Logical Equivalence ¬ B → ¬ (A ˄ (A → B)) (Solution-1)

¬ B  ¬ (A ˄ (A → B))
Step Description
⇒ ¬ B  ¬ (A ˄ (¬ A ˅ B)) Implication Equivalence
⇒ ¬ B  ¬ ((A ˄ ¬ A) ˅ (A ˄ B)) Distributive Law
⇒ ¬ B  ¬ (false ˅ (A ˄ B)) Contradiction

⇒ ¬ B  ¬ (A ˄ B) Tautology / False is left one of ∨
⇒ ¬ ¬ B ˅ ¬ (A ˄ B) Implication Equivalence
⇒ B ˅ ¬ (A ˄ B) Double Negation Law
⇒ B˅¬A˅¬B De Morgan’s Laws
⇒ B˅¬B˅¬A Commutative Law
⇒ True ˅ ¬ A Tautology
⇒ True Domination
Therefore, proved that ¬ B  ¬ (A ˄ (A → B))
(Solution-2 By Instructor)

(b) Prove by Rules of Inference ¬ B → ¬ (A ˄ (A → B)) (Solution-1)
A rule of inference is a general pattern that allows us to draw some new

conclusion from a set of given statements. If we know A then we can conclude B.
In order to prove the given statement we will apply contraposition;
¬ (¬ (A ˄ (A → B))) → ¬ (¬ B)
⇒ (A ˄ (A → B)) → B
Modus ponens: if (A ˄ (A → B)) then B
Proof is as follows
Consider that (A ˄ (A → B)) is true
⇒ A is true
⇒ A → B is True
⇒ B is True
Thus it is proved with contraposition that (A ˄ (A → B)) → B
Therefore,
¬ B → ¬ (A ˄ (A → B)) is true
(Solution-2 By Instructor)
By rules of inference
Taking contraposition
(A ˄ (A → B)) → B
If A is true and A→ B is true then B is true
Hence proved.

(c) Prove by Contradiction ¬ B → ¬ (A ˄ (A → B))
(Solution-1)
We will assume ¬ B to prove ¬ (A ˄ (A → B))
On contrary, suppose the statement (A ˄ (A → B)) is true;
Step Description
⇒ (A ˄ (A → B)) ˄ ¬ B
⇒ (A ˄ (¬A ˅ B)) ˄ ¬ B Implication Equivalence
⇒ ((A ˄ ¬A) ˅ (A ˄ B)) ˄ ¬ B Distributive Law
⇒ (false ˅ (A ˄ B)) ˄ ¬ B Tautology
⇒ (A ˄ B) ˄ ¬ B Contradiction
⇒ A˄B˄¬B Distributive Law
⇒ A ˄ False Contradiction
⇒ False
Therefore proved that ¬ (A ˄ (A → B)) is true by contradiction
(Solution-2 by Instructor)
Suppose ¬ (A ˄ (A → B)) is false then (A ˄ (A → B)) is true

It means A is true and A → B is true
if A is true and A → B is true then B must also be true
but we have ¬ B true, which is contradiction
hence proved.

Question: Prove ~C → ~ ( B ˄ (B → C))
1. By Logical Equivalences
2. Truth Table
3. Rules of inference
4. Contradiction

3. Rules of Inference

4. Contradiction

Question: Show that (p ∨ q) ∧ (¬ p ∨ r) → (q ∨ r) is a Tautology?
Solution:
p q r p∨q ¬p (¬ p ∨ r) (p ∨ q) ∧ (¬ p ∨ r) (q ∨ r) (p ∨ q) ∧ (¬ p ∨ r) → (q ∨ r)
T T T T F T T T T
T T F T F F F T T
T F T T F T T T T
T F F T F F F F T
F T T T T T T T T
F T F T T T T T T
F F T F T T F T T
F F F F T T F F T
Since (p ∨ q) ∧ (¬ p ∨ r) → (q ∨ r) is always T, it is a tautology.
Question: Show that [(p → q) ∧ (q → r)] → (p → r) is a tautology?

Solution:

Question: Show [(p ∨ q) ∧ (p → r) ∧ (q → r)] → r is a Tautology?
Solution:
Question: Show [¬ p ∧ (p → q)] → ¬ q is a Not Tautology?
Solution:

Question: Show that (p ∨ q) ∧ (¬p ∨ r) → (q ∨ r) is a Tautology?

Solution:
Question: Prove that each of the following pairs of propositional formulae are
equivalent using propositional equivalences.
(a) p ↔ q (p ∧ q) ∨ (¬p ∧ ¬q)
(b) ¬p → (q → r) q → (p ∨ r)

Question: Prove that each of the following propositional formulae are tautologies by
showing they are equivalent to T.
(a). ((p → q) ∧ (q → r)) → (p → r)
(b). (p ∧ q) ∨ (p ∧ r) → (q ∨ r)
(c). (p ∧ q) ∨ (¬p ∧ q) ∨ ¬q

Question: Construct Truth Tables for each of the following compound propositions.
(a) (p ∧ q) ∨ (p ∧ r)
(b) (q ∧ p) ↔ (q ⊕ p)

Question: Are the following compound propositions Tautologies?

(a) ((p → q) ∧ (q → r)) → (p → r)
(b) ((p ∧ q) ∧ (q ∧ r)) → (p ∧ r)
(c) ((p ⊕ q) ∧ (q ⊕ r)) → (p ⊕ r)
In other words are the logical operator’s implication, conjunction and exclusive-or
transitive?
(b) ((p ∧ q) ∧ (q ∧ r)) → (p ∧ r)

(c) ((p ⊕ q) ∧ (q ⊕ r)) → (p ⊕ r)
This is not a tautology as seen by the case where p and r are True and q is False,
or the case where p and r are False and q is True.
Thus the operator → and ∧ are transitive but ⊕ is not transitive.
Question: Let p, q, r denote primitive propositions. Determine whether the statements

(p ∨ q) → r and (p → r) ∧ (q → r) are Logically Equivalent.
Solution:
The truth table for the formula [(p ∨ q) → r] ↔ [(p → r) ∧ (q → r)]:

Question: Let p, q, r denote primitive propositions. Determine whether the statements

p → q ∧ r and (p → q) ∧ (p → r) are Logically Equivalent.
Solution:

Theorem
Let A and B are real numbers. A recurrence of the form
ak = Aak-1+ Bak-2 is satisfied by the
sequence 1,t,t2 ,....tn ,....t ≠ 0 where t is a non-zero real no, if and
only if t satisfies the equation t2 - At - B = 0
Proof:

Question: Using characteristic equation, find solution to a recurrence
relation
ak = ak-1+ 2ak-2 ꓯ k ≥ 2
Find all sequences that satisfy relation and have the form 1,t,t2 ,....tn
,....t ≠ 0
are both particular solutions for this recurrence relation.

Question: Solve the Recurrence / Solve First Order Recurrences
bk = a.bk-1 if b0 = c
Solution:
Question: Solve the Recurrence bk = 5bk-1 if b0 = 3

Solution:

Question: Suppose sequence, b0, b1, b2,. . . satisfies recurrence relation
bk = 4bk-1 - 4bk-2 ꓯk≥2

With initial condition: b0 = 1 and b1 = 3
Then find explicit formula for b0, b1, b2 , . . . , using characteristic equation
of the above recursion.

Question: Suppose sequence, b0, b1, b2, . . . , satisfies Recurrence Relation
bk = 5bk-1 - 6bk-2 ꓯ k ≥ 2
Solution:

Question: Solve the recurrence bk = a.bk-1 if b0 = c
Question: Solve the recurrence bk = 5bk-1 if b0 = 3

Question: Consider the Recurrence
tn = n if n = 0, 1, 2
tn = 7.tn-2 + 6.tn-3 otherwise
Find the general solution of the recurrence above.

Question: Consider the Recurrence
tn = n if n = 0, 1, 2
tn = 5tn-1 - 8tn-2 + 4tn-3 otherwise
Find general solution of the recurrence above.

Generalization: Non-homogeneous Recurrences
Question: Consider the Recurrence below. Find its solution
tn – 2tn-1 = 3n
Solution:

Problem: Tower of Hanoi

Question: Find General Solution of the following Recurrence.
tn - 2tn-1 = (n + 5) 3n ; n≥1
Solution:

Non-Homogeneous Recurrences
Question: Consider the recurrence
tn = 2tn-1 + n + 2n otherwise

Substitution Method
Question: Solve the recurrence relation T(n) given below. [Otherwise 3T(n/4) + n]
1 𝑖𝑓 𝑛 = 1
𝑇(𝑛) = { 𝑛
3. 𝑇 ( ) + 𝑛 𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒
4


Question: Consider the recurrence
tn = n if n = 0, 1, 2
tn = 6.tn-1 - 11.tn-2 + 6.tn-3 otherwise
Find the general solution of the recurrence above.
Solution:
Rewriting the recurrence,
tn - 6.tn-1 + 11.tn-2 - 6.tn-3 = 0

The characteristic equation becomes
x3 – 6x2 + 11x – 6 = 0
Testing whether 1 or -1 is a root of the equation or not, we find that 1 is a root of the equation,
hence

Question: Consider the recurrence given below. Find its general solution.
tn – 4tn-1 = (n + 3)5n
Solution:
Finding general solution of the following recurrence
tn - 4tn-1 = (n + 3) 5n n >= 1 (1)
Replacing n with n-1
tn-1 - 4tn-2 = (n + 2) 5n-1 n >= 2 (2)
Replacing n with n-2 we get
tn-2 - 4tn-3 = (n + 1) 5n-2 n >= 3 (3)
Above equations can be written as follows
tn - 4tn-1 = 25(n + 3) 5n-2 n >= 1 (4) [from eq.1 52, n-1]
tn-1 - 4tn-2 = 5(n + 2) 5n-2 n >= 2 (5) [from eq.2, n-1-1]
tn-2 - 4tn-3 = (n + 1) 5n-2 n >= 3 (6) [from eq.3]
Our objective is to eliminate the right hand side of the above equations to make it
homogenous.
Multiply equation (5) by -10 and equation (6) by 25 we get
tn - 4tn-1 = 25(n + 3) 5n-2
-10tn-1 + 40tn-2 = -50(n + 2) 5n-2
25tn-2 -100tn-3 = 25(n + 1) 5n-2
Adding the above equations we get
tn - 14tn-1 + 65tn-2 – 100tn-3 = 0
The characteristics equation of the above homogenous equation is
x3 – 14x2 + 65x - 100 = 0
⇒ (x - 4) (x2 – 10x + 25) = 0
⇒ (x – 4) (x – 5)2 = 0
Hence x = 4, 5, 5
The general solution is
tn = c1.4n + c2.5n + c3.n5n

Question: Find general solution of the following recurrence.

tn - 4tn-1 = (n + 5) 3n , n >= 1
Solution:
Finding general solution of the following recurrence
tn - 4tn-1 = (n + 5) 3n n >= 1 (1)
Replacing n with n-1
tn-1 - 4tn-1-1 = (n-1 + 5) 3n-1
tn-1 - 4tn-2 = (n + 4) 3n-1 n >= 2 (2)
Replacing n with n-2 we get
tn-2 - 4tn-2-1 = (n-2 + 5) 3n-2
tn-2 - 4tn-3 = (n + 3) 3n-2 n >= 3 (3)
Above equations can be written as follows
tn - 4tn-1 = 9(n + 5) 3n-2 n >= 1 (4) [from eq.1 32, n-1]
tn-1 - 4tn-2 = 3(n + 4) 3n-2 n >= 2 (5) [from eq.2, n-1-1]
tn-2 - 4tn-3 = (n + 3) 3n-2 n >= 3 (6) [from eq.3]
Our objective is to eliminate the right hand side of the above equations to make it
homogenous. So, multiply equation (6) by -12 we get
-12tn-2 + 48tn-3 = -12(n + 3) 3n-2 (7)
Adding equation (4), (5) and (7)
tn - 3tn-1 - 16tn-2 + 48tn-3 = 0
The characteristics equation of the above homogenous equation is
x3 – 3x2 - 16x + 48 = 0
⇒ (x-3)(x+4)(x-4)
Hence x = 3, -4, 4
The general solution is
tn = c1.3n – c2.4n + c3.n4n

Substitution Method
Question: Solve the recurrence relation T(n) given below using substitution method?
[4T(n/5) + n]
1 𝑖𝑓 𝑛 = 1
𝑇(𝑛) = { 𝑛
4. 𝑇 ( ) + 𝑛 𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒
5
Solution:


Recursive Tree Method

Question: Solve the recurrence relation given below using recursive tree method.
[3T(n/2) + n2]
1 𝑖𝑓 𝑛 = 1
𝑇(𝑛) = { 𝑛
3. 𝑇 ( ) + 𝑛2 , 𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒
2
Solution


Question: Use Mathematical Induction to prove that sum of first m positive integers is
m(m+1)/2?
OR
Use Mathematical Induction to prove
𝒎(𝒎 + 𝟏)
𝟐

Question: Show that in any base b ≥ 2, the sum of any three single-digit numbers is no
more than two digits long.
Solution [1]
A single digit number is at most b−1, therefore the sum of any three such numbers is at most
3(b−1)=3b-3.
On the other hand, a two-digit number can be as large as b2 −1.
It is enough to show that b2 −1 ≥ 3b−3.
Indeed, b2 − 1 − 3b + 3 = (b − 1) · (b − 2), which is ≥ 0 for b ≥ 2.
Solution [2]: By Induction Method

Question:
Start with some special kind of pair of rabbits, one male and one female, born on January 1.
Assume all months are of equal length and that rabbits begin to produce four months after
their own birth. After reaching age of four months, each pair produces two mixed pairs, two
males and two females, and then other two mixed pairs each month, and no rabbit dies.
1. Develop a model using tree diagram
2. Describe a recursive mathematical model

3. Compute the number of pairs of rabbits after one year?

Question: Use Mathematical Induction to prove that sum of first m even positive
integers is m(m+1)? OR Use Mathematical Induction to prove [2i = m(m+1)]
𝒊=𝒎
∑ 𝟐𝒊 = 𝒎(𝒎 + 𝟏)
𝒊=𝟏
Instructor Solution
My Solution from Assignment No: 1

i=m
∑ 2i = m(m + 1)
i=1
Let compute m = 1 on both sides, we will get

i=1
∑ 2 ∗ 1 = 1(1 + 1)
i=1
2 = 2 (True)

Therefore P (1) is true.
Now, suppose the statement is true for m = k
k
∑ 2i = k(k + 1)
i=1
In order to prove it for m = k + 1, add 2(k+1) on both sides

k
∑ 2i + 2(k + 1) = k(k + 1) + 2(k + 1)

i=1
By solving and taking k+1 as common, we will get

k+1
∑ 2i = (k + 1)(k + 2)
i=1
= (k+1) ((k+1) + 1)
= True
Hence, proved.
Question: Given two integers a and b, how to find their greatest common divisor
(gcd(a, b))?
Proof:
Euclid’s rule: If x and y are positive integers with x ≥ y, then
gcd(x, y) = gcd(x mod y, y).
It is enough to show the slightly simpler rule
gcd(x, y) = gcd(x − y, y).
Any integer that divides both x and y must also divide x − y, so
gcd(x, y) ≤ gcd(x − y, y).
Likewise, any integer that divides both x − y and y must also divide both x and y,
so gcd(x, y) ≥ gcd(x − y, y).

Question: Suppose sequence, b0, b1, b2, . . . , satisfies Recurrence Relation
bk = 6bk-1 - 9bk-2 k2
Solution:
bk = 6bk-1 - 9bk-2
or
bk - 6bk-1 + 9bk-2 = 0
The characteristic equation for the above is given below
Let consider the followings
bk = x2
Therefore, bk-1 = x
Similarly, bk-2 = x0
The characteristic equation will become as;
x2 - 6x + 9 = 0
By simplifying
(x)2 – 2(x)(3) + (3)2 = 0
(x – 3)2 = 0
⇒ t = 3, is repeated root
Thus
3n and n.3n are the sequences which satisfy the recurrence relation
Now, suppose general solution is:
bn = X.3n + Z.n.3n
Which satisfies the original recurrence, here X and Z are constants.

By computing initial conditions: b0 = 2 and b1 = 6

For n = 0
b0 = X.30 + Z.0.30
2 = X + 0 [b0 = 2]
⇒X=2 [i]
For n = 1
b1 = X.31 + Z.1.31
6 = 3X + 3Z [b1 = 6]
6 = 3(X + Z)
2=X+Z
2=2+Z [i]
⇒Z=0
Thus,
bn = 2 . 3n is the required explicit formula.

Question / Theorem: For any integer n ≥ 2, n is divisible by a prime.
Proof
By strong mathematical induction:

• Basis step:
The statement is true for n = 2. This is because 2 | 2 and 2 is a prime
number.
• Inductive step:
Assume the statement is true for all i with 2 ≤ i < k (inductive
hypothesis) ;
To show that it is true for k
• We know that ꓯ i Є Z, with 2 ≤ i < k, P(i), i.e. i is divisible by a prime
number. (1)
• Now we show P(k), i.e., k is divisible by a prime.
Take two cases:
Case 1: k is prime.
Then k is divisible by itself. And nothing to prove
Case 2: k is composite.
Then k = a·b, where 2 ≤ a < k and 2 ≤ b <k
Based on (1), p|a for some prime p. (2)
Based on Case 2, a|k (3)
By transitivity, p | a and a | k ⇒ p|k
Thus, P(n) is true by strong induction.

Question: (Part-1) Use Mathematical Induction to prove that sum of the first m odd
positive integers is m2? OR Σ (2i - 1) = m2 OR Σ (2i - 1) = n2 (replace m with n)
Use Mathematical Induction to prove that sum of the first n odd positive integers is n2?

Question: (Part 2) Use Mathematical Induction to prove that sum of first m even
positive integers is m(m+1)? Σ 2i = m(m+1)
[Note: Repeated Solution]

Question [Part 3]: Deduce the result of Part 2 from Part 1 and vice versa?

Question: Use mathematical Induction to prove that the inequality
n < 2n for all n Є Z+

Question: Show by Mathematical Induction that any amount in cents ≥ 8
cents can be obtained using 3 cents and 5 cents coins only.
Continue to next page….


Question: Prove that postage ticket of amount ≥ 12 cents can be formed
using only 4 cent and 5 cent stamps.

Question
Show by mathematical induction that any amount in cents ≥ 18 cents can be
obtained using 4 cents and 7 cents coins only.
Answer:
We have to prove that, amount = 4.m + n, m ≥ 0, n ≥ 0
Basis Step:
4*1 + 7*2 = 18
4*3 + 7*1 = 19
4*5 + 7*0 = 20
4*0 + 7*3 = 21
4*2 + 7*2 = 22
4*4 + 7*1 = 23
4*6 + 7*0 = 24
Let P(n) be the statement that: “n cents can be obtained using 4 and 7 cents”.
Inductive Hypothesis:
We want to show that
P(k) is true ⇒ P(k + 1), ꓯ k ≥ 18
Suppose k – 3 = 4 * m + 7 * n
Then k – 3 + 4 = 4 * m + 7 * n + 4
k + 1 = 4 * (m + 1) + 7 * n
By Strong Induction, P(n) is true if n Є Z and n ≥18

Question: Show by mathematical induction that any amount in cents ≥ 20 cents can be
obtained using 5 cents and 6 cents coins only?
Solution:

Existence of Binary Integer Representation
Theorem:
Given any positive integer n, there exists a unique representation of n in the form:
n = cr . 2r + cr-1 . 2r-1 + … + c1 . 21 + c0
Where r is non-negative integer, cr= 1, and cj = 0 or 1, ꓯ j = 0, 1, 2, . . . , r-1
Continue Next Page…


Fibonacci Sequences
Computing Values using Mathematical Model
Since Fk = Fk-1 + Fk-2 F0 = 0, F1= 1

F2 = F1 + F0= 1 + 0 = 1
F3 = F2 + F1= 1 + 1 = 2
F4 = F3 + F2= 2 + 1 = 3
F5 = F4 + F3= 3 + 2 = 5
F6 = F5 + F4= 5 + 3 = 8
F7 = F6 + F5= 8 + 5 = 13
F8 = F7 + F6= 13 + 8 = 21
F9 = F8 + F7= 21 + 13 = 34
F10 = F9 + F8= 34 + 21 = 55
F11 = F10 + F9= 55 + 34 = 89
F12 = F11 + F10= 89 + 55 = 144 . . .

Rabbits Problem
Refer to Handouts: CS702 Handouts_MidTerm_Genrica
Statement Page No
After reaching age of two months , each pair produces two
35 to 37
other mixed pairs, two male and two female
After reaching age of three months, each pair produces
another mixed pairs, one male and other female, and then 37 to 38
another mixed pair each month
Within This File: Scroll to Page No 71

Statement Page No
Begin to produce four months after their own birth. After
reaching age of four months, each pair produces two mixed 71 to 72
pairs.

Applications of Fibonacci Sequences
Fibonacci sequences are used
 In trend analysis
 By some pseudorandom number generators
 The number of petals is a Fibonacci number.
 Many plants show the Fibonacci numbers in the
arrangements of the leaves around the stems.
 Seen in arrangement of seeds on flower heads
 Consecutive Fibonacci numbers give worst case
behavior when used as inputs in Euclid’s algorithm.
 As n approaches infinity, the ratio F(n+1)/F(n)
approaches the golden ratio: Φ
=1.6180339887498948482...
 The Greeks felt that rectangles whose sides are in the
golden ratio are most pleasing
 The Fibonacci number F(n+1) gives the number of
ways for 2 x 1 dominoes to cover a 2 x n
checkerboard.
 Sum of the first n Fibonacci numbers is F(n+2)-1.
 The shallow diagonals of Pascal’s triangle sum to
Fibonacci numbers.
 Except n = 4, if F(n) is prime, then n is prime.
 Equivalently, if n not prime, then F(n) is not prime.
 gcd( F(n), F(m) ) = F( gcd(n, m))

What is Recursion?
 Sometimes problems are too difficult or too complex to solve
because these are too big.
 A problem can be broken down into sub-problems and find a way
to solve these sub-problems
 Then build up to a solution to the entire problem.
 This is the idea behind recursion
 Recursive algorithms break down problem in pieces which you
either already know the answer, or can be solved applying same
algorithm to each piece
 And finally combine the results of these sub-problems to find the
final solution
 More concisely, a recursive function or definition is defined in
terms of itself.
 Recursion is a computer algorithm that calls itself in a steps having
a termination condition.
 The successive repetitions are processed up to the critical step
where the condition is met.
 In recursive algorithms, each repetition is processed from the last
one called to the first.
 Recursion is a wonderful technique for dealing with many
problems where problems and sub-problems have same mechanism
to solve it.
 Merits and Demerits of Recursion
 Recursive solutions are much easier to conceive of and code than
their iterative counterparts.
 Every problem is not solvable using this approach
 What kinds of problems are solved with recursion?
 Generally, problems which are defined in terms of themselves are
usually good candidates for recursive techniques.

Question: Algorithm: Maxima Finding Problem
Solution:

Merge Sort
Merge-sort is based on divide-and-conquer approach and can be
described by the following three steps:
Divide Step:
• If given array A has zero or one element, return S.
• Otherwise, divide A into two arrays, A1 and A2,
• Each containing about half of the elements of A.
Recursion Step:
• Recursively sort array A1, A2
Conquer Step:
• Combine the elements back in A by merging the sorted arrays A1
and A2 into a sorted sequence.
Visualization of Merge-sort as Binary Tree

• We can visualize Merge-sort by means of binary tree where each
node of the tree represents a recursive call
• Each external node represents individual elements of given array
A.
• Such a tree is called Merge-sort tree.
• The heart of the Merge-sort algorithm is conquer step, which
merge two sorted sequences into a single sorted sequence

Merge Sort Algorithm

Algorithm: Maxima Finding Problem
Input: A set S of 2-dimensional points.
Output: The maximal set of S.
Maxima(P[1..n])
1. Sort the points in ascending order w. r .t. X axis
2. If |S| = 1, then return it, else
Find a line perpendicular to X-axis which separates S into SL and SR, each
of which consisting of n/2 points.
3. Recursively fined the maxima’s SL and SR
4. Project the maxima’s of SL and SR onto L and sort these points according to
their y-values.
5. Conduct a linear scan on the projections and discard each of maxima of S L if
its y-value is less than the y-value of some maxima’s of SR.
Time Complexity

Question: Why the Optimal Weight Convex Polygon Problem cannot be solved using Divide
and Conquer Approach?
Solution:
Optimal Weight Convex polygon problem cannot be solved using divide and conquer
approach because:
 Its sub problems are not independent from each other.
 We need an optimal solution of the problem, which may not be found using divide and
conquer approach.
Question: Consider the problem of a chain of A1, A2 and A3 of three matrices, suppose
the dimensions of the matrices are 10x100, 100x5, and 5x50. For the sequence of
matrices given above compute the order of product A1, A2 and A3 is such a way that
minimum total number of scalar multiplications.
Solution:
Order of A1= 10 x 100

Order of A2= 100 x 5
Order of A3= 5 x 50
Given sequence of matrices
A1 A2 A m[1,1] m[1,2] m[1,3]

. . 3
10  100 100  5 5  50 m[2,2] m[2,3]
m[3,3]
P0  10 , P1  100 , P2  5 , P3  50
Main Diagonal
m i, i   0, i  1, 2,3
m i, j   min  m i, k   m  k  1, j   pi 1. pk . p j 
i k  j
m 1,1  0 , m  2, 2  0 , m 3,3  0

Computing m[1,2] and m[2,3]
Computing m[1,2]
ik  j
m 1, 2  min  m 1, k   m  k  1, 2  p11. pk . p2 

1 k  2
Putting k = 1
m 1, 2  min  m 1,1  m  2, 2  p0 . p1. p2 
1 k  2
m 1, 2  min  0  0  10 100  5 

1 k  2
m 1, 2  5, 000
s 1, 2  k  1
Computing m[2,3]
ik  j
m  2,3  min  m  2, k   m  k  1,3  p21. pk . p3 

2  k 3
Putting k = 2
m  2, 3  min  m  2, 2  m 3,3  p1. p2 . p3 
2  k 3
m  2,3  min  0  0  100  5  50 

2  k 3
m  2,3  25, 000

s  2,3  k  2
Computing m[1,3]
ik  j
m 1,3  min  m 1, k   m  k  1,3  p11. pk . p3 

1 k 3
Putting k = 1 and k = 2

m 1,3  min  m 1,1  m  2,3  p0 . p1. p3  ,  m 1, 2   m 3,3  p0 . p2 . p3 
1 k 3

m 1,3  min   0  25, 000  10 100.50  ,  5, 000  0  10  5  50  
1 k 3
m 1,3  min  75000, 7500 

1 k 3
m 1,3  7500
s 1,3  k  2

Final Cost Matrix and its Order of Computation
Final Cost Matrix Order of Computation
0 5000 7500 1 4 6
0 25,000 2 5
0 3
k’s Values Leading to - Minimum m[i,j]
0 1 2
0 2
0
Order of Computation will be  A1. A2  . A3
1 A3
A1 A2

Question: For the sequence of matrices, given below, compute the order of the product,
A1.A2.A3.A4, in such a way that minimizes the total number of scalar multiplications, using
Dynamic Programming.
Order of A1 = 20 x 10
Solution:
Computing the optimal multiplication order for a series of matrices
𝐴1 𝐴2 𝐴3 𝐴4
. . .
20 𝑥 10 10 𝑥 30 30 𝑥 15 15 𝑥 25
From above we have

m[1,1] m[1,2] m[1,3] m[1,4]
P0 = 20
P1 = 10 x m[2,2] m[2,3] m[2,4]
P2 = 30 x x m[3,3] m[3,4]
P3 = 15
x x x m[4,4]
P4 = 25
Mathematical Model of dynamic programming
m[i,i] = 0 ꓯ i = 1,2,3,4
m[i,j] = min i ≤ k < j (m[i,k] + m[k+1, j] + Pi-1 . Pk . Pj)
Main Diagonals m[i,i]:

m[1, 1] = 0 m[2, 2] = 0 m[3, 3] = 0 m[4, 4] = 0
First Diagonals: m[1, 2], m[2, 3], m[3, 4]
Computing m[1, 2] i.e. i = 1 and j = 2:

m[1, 2] = min 1 ≤ k < 2 (m[1,k] + m[k+1, 2] + P0 . Pk . P2)
For k = 1, we will get
m[1, 2] = min 1 ≤ k < 2 (m[1,1] + m[2, 2] + P0 . P1 . P2)

Substitute the known values
m[1, 2] = min 1 ≤ k < 2 (0 + 0 + 20 . 10 . 30)
m[1, 2] = min 1 ≤ k < 2 (6000)
m[1, 2] = 6000 s[1, 2] = k = 1

m[2, 3] = min 2 ≤ k < 3 (m[2,k] + m[k+1, 3] + P1 . Pk . P3)
m[2, 3] = min 2≤k<3 (m[2,2] + m[3, 3] + P1 . P2 . P3)
m[2, 3] = min 2≤k<3 (0 + 0 + 10 . 30 . 15)
m[2, 3] = 4500 s[2, 3] = k = 2

m[3, 4] = min 3 ≤ k < 4 (m[3,k] + m[k+1, 4] + P2 . Pk . P4)
m[3, 4] = min 3 ≤ k < 4 (m[3,3] + m[4, 4] + P2 . P3 . P4)
m[3, 4] = min k = 3 (0 + 0 + 30 . 15 . 25)
m[3, 4] = 11250 s[3, 4] = k = 3

Second Diagonals: m[1, 3], m[2, 4]

m[1, 3] = min 1 ≤ k < 3 (m[1,k] + m[k+1, 3] + P0 . Pk . P3)
For k = 1 and k = 2 we will get
m[1, 3] = min 1 ≤ k < 3 ( m[1,1] + m[2, 3] + P0 . P1 . P3 ,
m[1,2] + m[3, 3] + P0 . P2 . P3)
m[1, 3] = min 1 ≤ k < 3 ( 0 + 4500 + 20 . 10 . 15 ,
6000 + 0 + 20 . 30 . 15)
m[1, 3] = min 1 ≤ k < 3 (7500 , 15000)
m[1, 3] = 7500 s[1, 3] = k = 1

m[2, 4] = min 2 ≤ k < 4 (m[2,k] + m[k+1, 4] + P1 . Pk . P4)
For k = 2 and k = 3 we will get
m[2, 4] = min 2 ≤ k < 4 ( m[2,2] + m[3, 4] + P1 . P2 . P4,
m[2,3] + m[4, 4] + P1 . P3 . P4)
m[2, 4] = min 2 ≤ k < 4 ( 0 + 11250 + 10 . 30 . 25,
4500 + 0 + 10 . 15 . 25)
m[2, 4] = min 2 ≤ k < 4 (18750 , 8250)
m[2, 4] = 8250 s[2, 4] = k = 3
Third Diagonal: m[1, 4]


m[1, 4] = min 1 ≤ k < 4 (m[1,k] + m[k+1, 4] + P0 . Pk . P4)
For k = 1, k = 2 and k = 3 we will get
m[1, 4] = min 1 ≤ k < 4 ( m[1,1] + m[2, 4] + P0 . P1 . P4 ,
m[1,2] + m[3, 4] + P0 . P2 . P4 ,
m[1,3] + m[4, 4] + P0 . P3 . P4)
m[1, 4] = min 1 ≤ k < 4 ( 0 + 8250 + 20 . 10 . 25 ,
6000 + 11250 + 20 . 30 . 25 ,
7500 + 0 + 20 . 15 . 25)
m[1, 4] = min 1 ≤ k < 4 (13250 , 32250 , 15000)
m[1, 4] = 13250 s[1, 4] = k = 1
Final Cost Matrix and Order of Computation
The procedure is as follows
 The table m[1. . n, 1. . n] for storing the m[i, j] costs
 The table s[1. . n - 1, 2. . n] records for which index of k achieved the optimal cost in
computing m[i, j]
 The table s is used to construct an optimal solution
Final Cost Matrix
0 6000 7500 13250

0 4500 8250
0 11250
0

Order of Computation
1 5 8 10
2 6 9
3 7
4
Values of k’s Leading to Minimum m[i,j]
0 1 1 1
0 2 3
0 3
0
From above final cost matrix, the computation shows that the minimum cost for multiplying
A1.A2.A3.A4 matrices, using Dynamic Programming is 13250 i.e. m[1,4].
Order of Computation to minimize the total number of scalar multiplications:
The optimal order for multiplication is A1 . ( ( A2 . A3 ) . A4)

Question: Consider the chain matrix multiplication for 4 matrices:
A1 A2 A3 A4
(7×5) (5×4) (4×6) (6×8)
Compute the cost table m in the dynamic programming algorithm for the Chain
Matrix Multiplication.
Solution:
𝐴1 𝐴2 𝐴3 𝐴4
. . .
7𝑥5 5𝑥4 4𝑥6 6𝑥8
From above we have

m[1,1] m[1,2] m[1,3] m[1,4]
P0 = 7
P1 = 5 x m[2,2] m[2,3] m[2,4]
P2 = 4 x x m[3,3] m[3,4]
P3 = 6
x x x m[4,4]
P4 = 8
Mathematical Model of Dynamic Programming
m[i,i] = 0 ꓯ i = 1,2,3,4
First super diagonal
m[1,2]=m[1,1] + m[2,2] + p0.p1.p2 = 0+0+7.5.4 = 140
m[2,3]=m[2,2] + m[3,3] + p1.p2.p3 = 0+0+5.4.6= 120
m[3,4]=m[3,3] + m[4,4] + p2.p3.p4 = 0+0+4.6.8 = 192
Second super diagonal
m[1,3]=m[1,1] + m[2,3] + p0.p1.p3 = 0+120+7*5*6 = 330
m[1,3]=m[1,2] + m[3,3] + p0.p2.p3 = 140+0+7*4*6 = 308
Minimum [1,3] = 308
for m[2,4]

m[2,4]=m[2,2] + m[3,4] + p1.p2.p4 = 0+192+5*4*8 =352
m[2,4]=m[2,3] + m[4,4] + p1.p3.p4 = 120+0+5*6*8 = 360
Minimum for m[2,4] = 352
Third super diagonal
m[1,4]=m[1,1] + m[2,4] + p0.p1.p4 = 0+352+7*5*8 = 632
m[1,4]=m[1,2] + m[3,4] + p0.p2.p4 = 140+192+7*4*8 = 556
m[1,4]=m[1,3] + m[4,4] + p0.p3.p4 = 308+0+7*6*8 =644
Minimum for m[1,4] = 556
Resultant is,

Question: Complexity function and j > k where j , k are numbers greater than 2.
Every function is separated by “comma” and note that there are 20 functions to
arrange.
Solution:

General Knapsack Problem
 Given a set of items, each with a cost and a value, then determine the items to
include in a collection so that the total cost is less than some given cost and the
total value is as large as possible.
 Knapsack problem is of combinatorial optimization
 It derives its name from the maximization problem of choosing possible
essentials that can fit into one bag, of maximum weight, to be carried on a trip.
 A similar problem very often appears in business, complexity theory,
cryptography and applied mathematics.
0-1 Knapsack Problem Statement
The knapsack problem arises whenever there is resource allocation with no financial
constraints
Problem Statement
A thief robbing a store and can carry a maximal weight of W into his knapsack. There
are n items and ith item weight is wi and worth is vi dollars. What items should thief
take, not exceeding the bag capacity, to maximize value?
Assumption:
The items may not be broken into smaller pieces, so thief may decide either to take an
item or to leave it, but may not take a fraction of an item.
Notations: 0-1 Knapsack Problem Construction
 You have prepared a list of n objects for which you are interested to buy, The
items are numbered as i1, i2, . . ., in
 Capacity of bag is W
 Each item i has value vi, and weigh wi
 We want to select a set of items among i1, i2, . . ., in which do not exceed (in total
weight) capacity W of the bag
 Total value of selected items must be maximum
 How should we select the items?

0-1 Knapsack Algorithm

Question: Brute Force Algorithm for 0-1 Knapsack problem?

Question: Complete Dynamic Programming / Algorithm for 0-1 Knapsack problem
Time complexity: Clearly, O(nW).

Question: Use the Backtracking algorithm for the 0-1 Knapsack problem to maximize
the profit for the following problem instance. Show actions step by steps. Maximum
Capacity = 8

Question: Using Brute Force Method to find an Optimal Solution for the 0-1 Knapsack
problem, knapsack capacity W = 32
Item Weight Value knapsack capacity W = 32
1 4 40
2 10 60
3 20 100
4 10 20
In Brute force Method to find an optimal solution for the 0-1 Knapsack problem, we find all
the subsets of the set of items and calculate the total weight and total value for each. We
exclude those subsets for which calculated weight is more than the capacity of knapsack.
Here, the subset {2,3} gives maximum value i.e. 160 with total weight of 30 (which is less
than the capacity of knapsack i.e. 32).
Hence, choosing items 2 and 3 gives us the maximum value, with weights within the
capacity of the knapsack.

Question: Below is a set of 9 points in 2-D. Compute the set of maximal points using
Brute Force Approach.
(2, 6), (4, 16), (8, 8), (8, 20), (10, 4), (14, 12), (16, 16), (18, 2), (22, 8).
Solution:
We have to compute the set of maximal points from following points, using Brute Force
Approach: (2, 6), (4, 16), (8, 8), (8, 20), (10, 4), (14, 12), (16, 16), (18, 2), (22, 8)
In maximal points using Brute Force approach, we have to compare each point with each of
the other points. And in each comparison we need to compare both the x and y coordinates of
the two points. Hence the procedure for computing maximal points will be as follows:
Procedure:
Points that dominate (2,6) = (4,16), (8,8), (8,20), (14,12), (16,16), (22,8)
Points that dominate (4,16) = (8,20), (16,16)
Points that dominate (8,8) = (8,20), (14,12), (16,16), (22,8)
Points that dominate (8,20) = No point dominate (8,20) So it is maximal
Points that dominate (10,4) = (14,12), (16,16), (22,8)
Points that dominate (14,12) = (16,16)
Points that dominate (18,2) = (22,8)
Set of maximal points = (8,20) , (16,16), (22,8)

Question: We have to compute the set of maximal points from following points, using
Brute Force Approach:
(2, 8), (6, 16), (8, 8), (10, 20), (12, 6), (16, 14), (18, 18), (20, 2), (24, 8)
Solution:
Points that dominate (2,8) = (6,16), (8,8), (10,20), (16,14), (18,18), (24,8)
Points that dominate (6,16) = (10, 20), (18, 18)
Points that dominate (8,8) = (10, 20), (16, 14), (18, 18), (24, 8)
Points that dominate (12,6) = (16, 14), (18, 18), (24, 8)
Points that dominate (16,14) = (18, 18)
Points that dominate (20,2) = (24, 8)
Set of maximal points = (10,20), (18,18), (24,8)
Algorithm

Question: Why Brute Force Approach is not Economical?
This is related to a famous function in combinatorics called the Catalan numbers. Catalan
numbers are related with the number of different binary trees on n nodes.
4𝑛
P(n) Є
𝑛3/2
The dominating term is the exponential 4n thus P(n) will grow large very quickly and hence
this approach is not economical.
Dynamic Programming Formulation

Cost Comparison Brute Force Dynamic Programming
A simple inspection of the nested loop structure yields a running time of O(n3)
for the algorithm. The loops are nested three deep, and each loop index (l , i, and
k) takes on at most
n-1 values.
4𝑛
Brute Force Approach: P(n) = C(n - 1) C(n) Є 3
𝑛2
Generalization: Sequence of Objects
Although this algorithm applies well to the problem of matrix chain

multiplication. Many researchers have noted that it generalizes well to solving a
more abstract problem
 Given a linear sequence of objects
 An associative binary operation on those objects hold
 The objective to find a way to compute the cost of performing that
operation on any two given objects
 Finally computing the minimum cost for grouping these objects to apply
the operation over the entire sequence.
It is obvious that this problem can be solved using chain matrix multiplication,
because there is a one to one correspondence between both problems.
Generalization: String Concatenation
One common special case of chain matrix multiplication problem is string

concatenation.
 For example, we are given a list of strings.

 The cost of concatenating two strings of length m and n is for example
O(m + n)
 Since we need O(m) time to find the end of the first string and O(n) time
to copy the second string onto the end of it.
 Using this cost function, we can write a dynamic programming
algorithm to fined the fastest way to concatenate a sequence of strings
 It is possible to concatenate all in time proportional to sum of their
lengths, but here we are interested to link this problem with chain matrix
multiplication.

Generalization: Parallel Processors
 Another generalization is to solve the problem when many parallel processors are
available.
 In this case, instead of adding the costs of computing each subsequence, we just take
the maximum, because we can do them both simultaneously.
 This can drastically affect both the minimum cost and the final optimal grouping
 But of course more balanced groupings that keep all the processors busy is more
favorable solution
 There exists some more sophisticated approaches to solve this problem

Question: Use Dynamic Programming to find an Optimal Solution for the 0-1
Knapsack problem.
Item Weight Value Knapsack Capacity W = 11
1 1 1
Use the given Knapsack
2 2 6 capacity to calculate
3 5 18
4 6 22
5 7 28
Solution:
We need to calculate V[n, W], where n is the number of items and W is the capacity of the
knapsack.
Base Case:
V[0, w] = 0, 0 ≤ w ≤ W No items are available
V[0, w] = -∞, w < 0 Invalid
V[i, 0] = 0, 0 ≤ i ≤ n No capacity available
Recursive Model:
V[i, w] = max ( V[i-1, w], vi + V[i-1, w - wi] )
for 1 ≤ i ≤ n, 0 ≤ w ≤ W
Now we have to calculate two tables V[5,11] and Keep[5,11], which is as follows:


Question: Use Dynamic Programming to find an optimal solution for the 0-1 Knapsack
problem. [Capacity W = 12]
Item Weight Value
1 4 40
2 3 30
3 5 40
4 4 50
5 5 70
Solution:


Question: Longest Common Subsequence?

Problem Statement:
In the longest-common-subsequence (LCS) problem, we are given two sequences
X = <x1, x2, . . . , xm> and Y = <y1, y2, . . . , yn>
And our objective is to find a maximum-length common subsequence of X and Y.
Note:
This LCS problem can be solved using brute force approach as well but using dynamic
programming it will be solved more efficiently.
Longest Common Subsequence: Brute Force Approach

 First we enumerate all the subsequences of X = <x1, x2, . . . , xm>.
 There will be 2m such subsequences.
 Then we check if a subsequence of X is also a subsequence of Y.
 In this way, we can compute all the common subsequences of X and Y.
 Certainly, this approach requires exponential time, making it impractical for long
sequences.
Note:
Because this problem has an optimal sub-structure property, and hence can be solved using
approach of dynamic programming
Longest Common Subsequence: Dynamic Programming Solution

Towards Optimal Substructure of LCS: Prefixes
 As we shall see, the natural classes of sub-problems correspond to pairs of “prefixes”
of the two input sequences.
 To be precise, given a sequence X = <x1, x2, ..., xm>, we define the ith prefix of X, for
i = 0, 1, ..., m, as Xi = <x1, x2, ..., xi>.
Examples,

Finding the LCS Length
• If one sequence is empty

the LCS has length 0
• The table b[1..m,1..n]
points to the table entry
corresponding to the
optimal sub-problem
solution when computing
c[i,j]
• Lines 7 through 16
compute the tables b and c
in row major order; the
structure matches the three
cases outlined (xm = yn and
two cases for xm  yn)
The figure on the next slide (sample solution) shows how the calculations are performed
Since the table c is (m+1) x (n+1) and each entry takes O(1) to compute, the complexity of
the algorithm is (mn)

Longest Common Sequence: A Sample Solution

• The answer is 4 from the c[m,n] entry
• If the letters match, the arrow points

 and the entry is one greater
• If the letters do not match the value is

the maximum of left and up and the
arrow points to the larger of left or up
(and up if equal)

Constructing Longest Common Sequence (LCS)

Question: Using Dynamic Programming, determine a Longest Common Subsequence
of <1, 0, 0, 1, 0, 1, 0, 1> and <0, 1, 0, 1, 1, 0, 1, 1, 0>.
Solution:
Note: There can be many Longest Common Subsequences of length 6 (e.g. as shown in the
table).

Question: Use Dynamic programming to determine a Longest Common Subsequence of
<1,0,0,1,0,1,0,1> and <0,1,0,1,1,0,1,1,0>

Question: If X = <A, B, D ,A ,D ,B ,A ,B>, and Y = <D, A ,B ,A ,B ,D ,A ,B , A > are two
sequences then compute a maximum-length common subsequence of X and Y.
Solution:

Question: Find the time complexity of each line of following algorithm.
1. Procedure sort(A[1…..n])
2. for i:=1 to n-1 do
3. for j:= to n-I do
4. if A[j] > A [j+1] then
5. Swap A[j] with A[j+1]
Solution:
The above algorithm is a bubble sort algorithm; step by step analysis of algorithm is as
follows
1- Consist of two nested loop
2- Compute in worst case for an array of size “n”
3- Outer loop is executed n-1 times, suppose the cost of checking the loop condition and
decrementing “i” is c1.
4- 1st passage through the inner loop, n-1 comparisons and n-1 swaps (n - 1)st and passage
through the inner loop consist of one comparison and one swap.
5- Gathering information of inner loop we get c ((n-1) + (n-2) + ... + 1)
Where “c” is the time required to do one comparison, one swap, check the inner loop
condition and increment j
6- We also spend constant time k declaring “i”, “j” and initializing “i”, “j”.
So finally we get

Question: Give a comparison of Divide & Conquer Approach and Dynamic
Programming. Give the reasoning that why the Optimal Weight Convex Polygon
Problem cannot be solved using Divide and Conquer Approach.
Solution:
Comparison of Divide and Conquer approach and Dynamic Programming:
Divide and Conquer Approach Dynamic Programming

Used when sub-problems are
independent of each other. So, pick Used when sub-problems are dependent
partition that makes algorithm most on each other. We don’t know where to
efficient & simply combine solutions to partition the problem.
solve entire problem.
Used to find an Optimal Solution of the
Used to find a solution of a problem
problem.
Combines the sub-problem solutions on Combine the sub-problem solutions on
the basis of some predefined functions. the basis of optimal value.
In dynamic programming algorithms,
Divide-&-conquer is best suited for the
we typically solve each sub-problem
case when no “overlapping sub-
only once and store their solutions. But
problems” are encountered.
this is at the cost of space.
Reasoning:
A simple polygon is convex if given any two points on its boundary or in its interior all
points on the line segment drawn between them are contained in the polygon’s boundary or
interior.
Optimal Weight Convex polygon problem cannot be solved using divide and conquer
approach because:
 Its sub problems are not independent from each other.

 We need an optimal solution of the problem, which may not be found using divide and
conquer approach.

Question: Brute Force Algorithm in n-Dimension | n-Line Assembly Language.
Solution: MAXIMAL-POINTS

Question: Plane Sweep Algorithm in n-Dimension?

Write pseudo code of Plane Sweep algorithm in n-Dimension?
Solution:

Optimal Weight Triangulation

Why Polygon Triangulation?
 Finite element method is a technique for solving numerical problems e.g. stress or heat
flow simulations of any kind of systems
 It involves dividing a shape into simple elements for example triangles
 Then formulating a set of linear equations describing relations between simulated
quantities in each element, and solving these equations.
 The time and accuracy both, in solution, depend on the quality of dividing into
triangles
 Generally, it is desired that triangles must be as close to equilateral as possible
Similarity: Optimal Polygon Triangulation, other Problem

 Optimal triangulation problem is very similar to matrix chain multiplication
 It is an excellent approach to make one to one corresponding between two problems
and
 Then solving one problem based on the approach already used in the solution of the
other problem
 This is what we are going to do in solving an optimal solution of the triangulation
problem which is very popular in computational geometry
 Applications of this problem can be observed in many other areas where division of
structures is required before performing computation over it.

Basic Concepts
 Polygon: A set of finite piecewise-linear, closed curve in a plane is

called a polygon
 Sides: The pieces of the polygon are called its sides
 Vertex: A point joining two consecutive sides is called a vertex
 Interior: The set of points in the plane enclosed by a simple

polygon forms interior of the polygon
 Boundary: The set of point on the polygon forms its boundary
 Exterior: The set of points surrounding the polygon form its

exterior
 Simple Polygon: A polygon is simple if it does not cross itself,

i.e., if its sides do not intersect one another except for two
consecutive sides sharing a common vertex.
 Subdivision of Polygon: A simple polygon subdivides the plane

into its interior, its boundary and it’s exterior.
 Convex Polygon: A simple polygon is convex if given any two

points on its boundary or in its interior, all points on the line
segment drawn between them are contained in the polygon’s
boundary or interior.

Proof of Lemmas
Lemma 1: A triangulation of a simple polygon, with n vertices, has n-2
number of triangles.
Proof:
Proof is done using mathematical induction
Basis Step
Suppose that there three vertices, polygon will be a triangle, i.e.
there are 3 - 2 = 1 number of triangles. Hence statement is true for
n=3
If there are 4 vertices, polygon will be in fact a rectangle, divide it
into two triangles. The result is true. Hence statement is true for n
=4
Inductive Hypothesis
Let us suppose that statement is true for n = k, i.e., if there are k
vertices then there are k-2 number of triangles
Claim:
Now we have to prove that if there are k+1 vertices there must be
k+1-2 = k-1, number of triangles.
Since for k vertices there are k-2 triangles. Insert one more point at
boundary of polygon
In fact point will be inserted at boundary of one of the triangles. So
the triangle will become rectangle. Divide it into two triangles. It
will increase one more triangle in the division.
Hence it becomes; k – 2 + 1 = k - 1, number of triangles.
It proves the claim. Hence by mathematical induction it proves that for n
number of vertices there are n - 2 number of triangles.

Lemma 2: A triangulation of a simple polygon, with n vertices, has n-3 chords.
Proof:
If there are three points, it will be triangle. To make a chord in a polygon, it requires at least
four points. So we have to give proof for n ≥ 4.
Basis Step
Suppose that there are four number of vertices, in this case polygon will be a
rectangle, there must be 4 - 3 = 1 number of chords. Hence statement is true for n = 4
Inductive Hypothesis
Let us suppose that the statement is true for n = k, i.e., if there are k vertices then there
are k - 3 number of chords of the polygon.
Claim
Now we have to prove that if there are k+1 vertices there must be k+1-3 = k-2, number
of chords.
Since for k vertices there are k-3 chords. Insert one more point at boundary of polygon
In fact point will be inserted at boundary of one of the triangles. So the triangle will
become rectangle. Divide it into two triangles. It will increase one more chord in the
division. Hence it becomes k – 3 + 1 = k - 2, number of chords.
Proved.

Question: In the optimal weight triangulation problem, prove that for a triangulation
of a convex polygon with n vertices, there will be n-1 number of leaf nodes for the
resultant binary tree generated from the dual graph.
Solution:


2
Question: Prove that for all integers n, if n is even then n is also even?

Question: Fractional Knapsak Psuedo Code?
Developing of algorithm if asked in the question.

Problem Statement: Chain Matrix Multiplication
Given a chain of [A1, A2, . . . , An] of n matrices where for i = 1, 2, . . . , n,
Matrix Ai has dimension pi-1 x pi,
Find the order of multiplication which minimizes the number of scalar multiplications.
Note:
Order of A1 is p0 x p1,
Order of A2 is p1 x p2,
Order of A3 is p2 x p3, etc.
Order of A1 x A2 x A3 is p0 x p3,
Order of A1 x A2 x . . . x An is p0 x pn
Why Dynamic Programming in this problem?

• Problem is of type optimization
• Sub-problems are dependent
• Optimal structure can be characterized and
• Can be defined recursively
• Solution for base cases exits
• Optimal solution can be constructed
• Hence here is dynamic programming


Question: Why we use dynamic programming? Give limitations?
Answer:
 Dynamic programming can be applied to any problem that observes the
principle of optimality.
 Generally, it means that partial solutions can be optimally extended with
regard to the state after the partial solution instead of the partial solution
itself.
 The biggest limitation using dynamic programming is number of partial
solutions we must keep track of
 For all examples we have seen, partial solutions can be described by
stopping places in the input.
 This is because combinatorial objects e.g. strings, numerical sequences, and
polygons etc., all have an implicit order defined upon their elements.
 This order cannot be changed without completely changing the original
problem.
 Once order fixed, there are relatively few possible stopping places, and we
get an efficient algorithms.
Why Dynamic Programming?

 Dynamic programming, like divide and conquer method, solves
problems by combining the solutions to sub-problems.
 Divide and conquer algorithms:
 Partition the problem into independent sub-problem
 Solve the sub-problem recursively and
 Combine their solutions to solve the original problem
 In contrast, dynamic programming is applicable when the sub-
problems are not independent.
 Dynamic programming is typically applied to optimization
problems.

Question: Write down the Brute Force Chain Matrix Multiplication Algorithm
and its complexity.
Generalization of Brute Force Approach
If there is sequence of n matrices, [A1, A2, . . . , An].
Ai has dimension pi-1 x pi, where for i = 1, 2, . . . , n.
Find order of multiplication that minimizes number of scalar multiplications
using brute force approach.

Question: Algorithm of chain matrix multiplication
Brute Force Approach
• If we wish to multiply two matrices: A = a[i, j]p, q and B = b[i, j]q, r

• Now if C = AB then order of C is p x r.
• Since in each entry c[i, j], there are q number of scalar of multiplications
• Total number of scalar multiplications in computing
C = Total entries in C x Cost of computing a single entry = p . r . q
• Hence the computational cost of AB = p . q . r will be
In particular, for 1 ≤ i ≤ p and 1 ≤ j ≤ r
There are p . r total entries in C and each takes O(q) time to compute, thus the
total time to multiply these two matrices is dominated by the number of scalar
multiplication, which is p . q . r.

Dynamic Programming: Matrix Chain Multiplication
Standard algorithm for multiplying two matrices
If A is a p x q and B is a q x r matrix, then C = AB is a p x r matrix.
Time complexity: O(pqr)

Procedure that prints an optimal parenthesis / parenthesization of a table
computed by MATRIX-CHAIN-ORDER.

Question: Write Algorithm for Recursive Matric Chain Multiplication?

Solution:

Question: Algorithm for Closest Pair in 2D using Brute Force approach?
Solution:
Brute Force Approach: Finding Closest Pair in 2-D

Question: Brute Force Improved Version: Finding Closest Pair in 2-D

Question: Brute Force Approach: Finding Closest Pair in 3-D

Question: Algorithm for Closest Pair in 2-D using Divide and Conquer
Closest Pair in 2-D Algorithm using Divide and Conquer approach.
Running Time: Running time of a divide-and-conquer algorithm can be described by a

recurrence
– Divide = O(1)
– Combine = O(n log n)
– This gives the recurrence given below
– Total running time: O(n log2 n)

Assembly-Line Scheduling Problem

 There are two assembly lines each with n stations
 The jth station on line i is denoted by Si, j
 The assembly time at that station is ai,j.
 An auto enters factory, goes into line i taking time ei
 After going through the jth station on a line i, the auto goes on to the (j+1)st
station on either line
 There is no transfer cost if it stays on the same line
 It takes time ti,j to transfer to other line after station Si,j
 After exiting the nth station on a line, it takes time xi for the completed auto
to exit the factory.
 Problem is to determine which stations to choose from lines 1 and 2 to
minimize total time through the factory.
Steps in Development of Dynamic Algorithms

1. Characterize the structure of an optimal solution
2. Recursively define the value of an optimal solution
3. Compute the value of an optimal solution in a bottom-up fashion
4. Construct an optimal solution from computed information
Note: Steps 1-3 form the basis of a dynamic programming solution to a problem.
Step 4 can be omitted only if the value of an optimal solution is required.

Question: Pseudo code of n line Assembly?
Write algorithm for n-line Assembly using Dynamic Programming /
Algorithm / The Fastest Way
n-Line Assembly: Dynamic Algorithm

Question: Write algorithm 2-Line Assembly language?
Solution:
The closest pair of points can be computed in O(n2) time by performing

a brute-force search. To do that, one could compute the distances
between all the n(n − 1) / 2 pairs of points, then pick the pair with the
smallest distance, as illustrated below.
minDist = infinity
for i = 1 to length(P) - 1
for j = i + 1 to length(P)
let p = P[i], q = P[j]
if dist(p, q) < minDist:
minDist = dist(p, q)
closestPair = (p, q)
return closestPair

Question: Print station n - Line assembly

Write pseudo code of n-line assembly: dynamic programming algorithm for print
stations?
Write pseudo code of Assembly line scheduling dynamic programming algorithm
for print station?
Constructing the Fastest Way: n-Line
-----------------------------------------------------------------
Generalization: Cyclic Assembly Line Scheduling

Title: Moving policies in cyclic assembly line scheduling
Source: Theoretical Computer Science, Volume 351, Issue (February 2006)
Summary: Assembly line problem occurs in various kinds of production
automation. In this paper, originality lies in the automated manufacturing of PC
boards.
• In this case, the assembly line has to process number of identical work pieces in
a cyclic fashion. In contrast to common variant of assembly line scheduling.
• Each station may process parts of several work-pieces at the same time, and
parts of a work-piece may be processed by several stations at the same time.

n-Line Assembly Problem
There are n assembly lines each with m stations

The jth station on line i is denoted by Si,j
The assembly time at that station is ai,j.
An auto enters factory, goes into line i taking time ei
After going through the jth station on a line i, the auto goes on to
the (j+1)st station on either line
It takes time ti,j to transfer from line i, station j to line i’ and
station j+1
After exiting the nth station on a line i, it takes time xi for the
completed auto to exit the factory.
Problem is to determine which stations to choose from lines 1 to
n to minimize total time through the factory.
n-Line: Brute Force Solution

Total Computational Time = possible ways to enter in stations at
level n x one way Cost
Possible ways to enter in stations at level 1 = n1
Possible ways to enter in stations at level 2 = n2 . . .
Possible ways to enter in stations at level m = nm
Total Computational Time = Θ(m.mn)

Application: Multiprocessor Scheduling
 The assembly line problem is well known in the area of multiprocessor
scheduling.
 In this problem, we are given a set of tasks to be executed by a system with
n identical processors.
 Each task, Ti, requires a fixed, known time pi to execute.
 Tasks are indivisible, so that at most one processor may be executing a
given task at any time
 They are un-interruptible, i.e., once assigned a task, may not leave it until
task is complete.
 The precedence ordering restrictions between tasks may be represented by a
tree or forest of trees

Recursion Tree Method
• Although substitution method can provide a sufficient proof
that a solution to a recurrence is correct, sometimes difficult to
give a good guess.
• Drawing out a recursion tree, is a straight forward way to
devise a good guess.
• In recursion tree, nodes represent costs of a sub-problems in the
set of recursive function invocations.
• We sum costs within each level of the tree to obtain a set of
per-level costs.
• And then we sum all per-level costs to determine the total cost
of all levels of the recursion.
• Recursion trees are particularly useful when recurrence
describes running time of divide and conquer algos.
• Recursion tree is best one used to generate a good guess, which
is then verified by substitution method
• When using a recursion tree to generate a good guess, we can
often tolerate a small amount of sloppiness since we have to
verify it later on.
• If we are careful when drawing out a recursion tree and
summing costs, then we can use a recursion tree as a direct proof
of a solution to any recurrence of any problem.
• Here, we will use recursion trees directly to prove theorem that
forms the basis of the master method.

Symmetry over Θ [Theeta]

Property: Prove that f(n) = Θ (g(n))  g(n) = Θ (f(n))

2 2
Question: n + 5n + 7 = Θ(n ) [Theeta]
Question: 5n2 – 6n = Θ(n2) [Theeta]

Question: Prove that Prn4ove 5n2 + 7n Є O(n2) [Big-Oh]

Proof:
5n2 + 7n Є O(n2)
Big-Oh notation formula is
0 ≤ f(n) ≤ cg(n) ꓯ n ≥ n0
Suppose that f(n) = 5n2 + 7n and g(n) = n2
f(n) Є O(g(n))?
Now, we have to find values of c1 and n0 ꓯ n ≥ n0
Computing the values of f(n) and g(n) in the formula
0 ≤ 5n2 + 7n ≤ c.n2
Let suppose c1 = 6, then we need to find n0, for which above is true
Let n0 = 1, then we have
5(1)2 + 7(1) ≤ 6(1)2
5+7≤6
12 ≤ 6
Now testing different values of n from 1 to onward
We find for n0 = 7
5(7)2 + 7(7) ≤ 6(7)2
245 + 49 ≤ 294
294 ≤ 294
Hence c1 = 6 ꓯ n ≥ 7
Proved that f(n) Є O(g(n)), therefore also proved that
5n2 + 7n Є O(n2)

2 2
Question: Prove that Prn4ove 5n + 7n = O(n) [Big-Oh]
Proof: 5n2 + 7n = O(n)2
Big-Oh notation formula is
0 ≤ f(n) ≤ cg(n) ꓯ n ≥ n0
Suppose that f(n) = 5n2 + 7n and g(n) = n2
f(n) ≤ O(g(n))?
Now, we have to find values of c1 and n0 ꓯ n ≥ n0
Computing the values of f(n) and g(n) in the formula
0 ≤ 5n2 + 7n ≤ c.n2
Let suppose c1 = 6, then we need to find n0, for which above is true
Let n0 = 1, then we have
5(1)2 + 7(1) ≤ 6(1)2
5+7≤6
12 ≤ 6
Now testing different values of n from 1 to onward
We find for n0 = 7
5(7)2 + 7(7) ≤ 6(7)2
245 + 49 ≤ 294
294 ≤ 294
Hence c1 = 6 ꓯ n ≥ 7
Proved that f(n) = O(g(n)), therefore also proved that
5n2 + 7n = O(n)2

𝟏 2 2 2
Question: Show that n + 3n = Θ(n ) OR [1/2 n + 3n] [Theeta]
𝟐

𝟏 2
Question: Show that n - 3n = Θ(n ) OR [1/2 n – 3n] [Theeta]
2 2
𝟐

Question: Prove 3n – 4n + 1 = Θ(n ) [Theeta]
2 2
Solution:

Question: Find a sequence that satisfies the recurrence relation
ak = ak-1 + 2ak-2 ꓯk≥2 and that also satisfies the initial condition a0 = 1
and a1 = 8
Solution:
The characteristic equation of the relation ak = ak-1 + 2ak-2 ꓯk≥2 is
t2 – t – 2 = 0
⇒(t – 2) (t + 1) = 0
⇒t = -1, 2

Theorem: Statement: Prove that any linear combination of solutions of
equation given below is also a solution.
a0tn + a1tn-1 + …+aktn-k = 0

Question: What is the solution of the recurrence relation?

an = an-1 + 2an-2 with a0=2 and a1=7?
Solution:
Since it is linear homogeneous recurrence, first find its

characteristic equation
r2 - r - 2 = 0
(r+1)(r-2) = 0
r1 = 2 and r2 = -1
So, by theorem an = 12n + 2(-1)n is a solution.
Now we should find 1 and 2 using initial conditions.

a0= 1 + 2 = 2
a1= 12 + 2(-1) = 7
So, 1= 3 and 2 = -1.

an = 3 . 2n - (-1)n is a solution.

fn = fn-1 + fn-2 with f0=0 and f1=1?

an = 6an-1 - 9an-2 with a0=1 and a1=6?

an = -3an-1 - 3an-2 - an-3

with a0=1, a1=-2 and a2=-1?

Question: Show that f(n) = n2 + 2n + 1 is O(n2).
Question: Show that f(n) = 3n + 7 is O(n)

Question: Show that f(n) = (n + 1)3 is O(n3)
Question: Show that f(n) = ∑𝒏𝒊=𝟏 𝒊 is O(n2)

Question: Prove n2 log n = Θ(n2) is incorrect. [Theeta]

Question: To Prove n log n ϵ O(n2)
Question: Prove n2 + 42n + 7 = O(n2)

Solution

Question: Show that (p ∨ q) ∧ (¬ p ∨ r) → (q ∨ r) is a tautology?

Designing Algorithms using Divide & Conquer Approach
Divide and Conquer Approach

Question: Algorithm of matrix chain multiplication

Question: Algorithm of 2-Dimension points. [Maxima]

Solution:

Question: The sequence <un> is defined by the recurrence [3un + 1 / 5un + 3]

3𝑢𝑛 +1
un+1 =
5𝑢𝑛 +3
You have initial conditionu1 = 1, Now you have to show un in terms of
Fibonacci / Lucasnumbers.
Solution:
We first prove a straightforward lemma.
Lemma: For all n>=1;

Which is (2) also

Now we can prove the result in Question.
Theorem: For all n>=1,
Notice that


Question: Find a general formula for the Fibonacci sequence
[fn = fn-1 + fn-2]

Question: Find the solution for the recurrence relation

[xn = 6xn-1 – 9xn-2]

Question: Find the solution for the recurrence relation

[xn = 2xn-1 – 5xn-2]

Question – 3: There are two assembly lines, as shown in the diagram below, each with 6 stations.
The auto is required to go through from all of these 6 stations from left to right. Nodes represent
stations. The assembly time at each station is shown at each node. The entering and exit times
for an auto are also given. The transfer time is represented at the edges when an auto moves to
next station on a different line. There is no transfer time if it stays on the same line. Determine
which stations to choose from lines 1 and 2 to minimize total time through the factory. Also
compute the optimal value in terms of time. Use Dynamic Programming Approach. You need
to calculate fi[j], li[j], f*, l* and the optimal path.
Solution:
Let
fi[j] = Denotes the fastest time from starting point station Si, j
f1[j] = Denotes the fastest possible time from starting point through jth station of
assembly line 1.
f2[j] = Denotes the fastest possible time from starting point through jth station of
assembly line 2.
li[j] = The line number, 1 or 2, whose station j-1 is used in a fastest way through
station Si, j.
It is to be noted that li[1] is not required to be defined because there is no station before
1
ti[j-1] = Denotes the transfer time cost from assembly line i to station S i-1, j or Si+1, j
Objective function f* = min(f1[n] + x1, f2[n] + x2)
l* = Denotes the line number whose last or nth station is used in a fastest way through
entire factory.

Mathematical Model: Finding Objective Function
f1[1] = e1 + a1,1
f2[1] = e2 + a2,1
f1[j] = min (f1[j-1] + a1,j , f2[j-1] + t2,j-1 + a1,j) for j ≥ 2;
f2[j] = min (f2[j-1] + a2,j , f1[j-1] + t1,j-1 + a2,j) for j ≥ 2;
Base Cases
f1[1] = e1 + a1,1 f1[1] = 3 + 5 f1[1] = 8
f2[1] = e2 + a2,1 f2[1] = 1 + 3 f2[1] = 4
Computation of f1[2], i.e. j = 2

f1[j] = min (f1[j-1] + a1, j , f2[j-1] + t2, j-1 + a1, j)
f1[2] = min (f1[1] + a1, 2 , f2[1] + t2, 1 + a1, 2)
f1[2] = min (8 + 5 , 4 + 2 + 5) = min (13,11)
f1[2] = 11 l1[2] = 2

f2[2] = min (f2[1] + a2, 2 , f1[1] + t1, 1 + a2, 2)
f2[2] = min (4 + 4 , 8 + 5 + 4) = min (8,17)
f2[2] = 8 l2[2] = 2


f1[3] = min (f1[2] + a1, 3 , f2[2] + t2, 2 + a1, 3)
f1[3] = min (11 + 3 , 8 + 4 + 3) = min (14, 15)
f1[3] = 14 l1[3] = 1

f2[j] = min (f2[j-1] + a2,j , f1[j-1] + t1,j-1 + a2,j)
f2[3] = min (f2[2] + a2,3 , f1[2] + t1,2 + a2,3)
f2[3] = min (8 + 8 , 11 + 4 + 8)
f2[3] = min (16 , 23)
f2[3] = 16 l2[3] = 2

f1[4] = min (f1[3] + a1, 4 , f2[3] + t2, 3 + a1, 4)
f1[4] = min (14 + 6 , 16 + 5 + 6)
f1[4] = min (20 , 27)
f1[4] = 20 l1[4] = 1
f2[4] = min (f2[3] + a2, 4 , f1[3] + t1, 3 + a2, 4)
f2[4] = min (16 + 6 , 14 + 1 + 6)
f2[4] = min (22 , 21)
f2[4] = 21 l2[4] = 1

f1[5] = min (f1[4] + a1, 5 , f2[4] + t2, 4 + a1, 5)
f1[5] = min (20 + 8 , 21 + 3 + 8)
f1[5] = min (28 , 32)
f1[5] = 28 l1[5] = 1

f2[5] = min (f2[4] + a2, 5 , f1[4] + t1, 4 + a2, 5)
f2[5] = min (21 + 4 , 20 + 6 + 4)
f2[5] = min (25, 30)
f2[5] = 25 l2[5] = 2

f1[6] = min (f1[5] + a1, 6 , f2[5] + t2, 5 + a1, 6)
f1[6] = min (28 + 7 , 25 + 1 + 7)
f1[6] = min (35 , 33)
f1[6] = 33 l1[6] = 2


f2[6] = min (f2[5] + a2, 6 , f1[5] + t1, 5 + a2, 6)
f2[6] = min (25 + 7 , 28 + 3 + 7)
f2[6] = min (32 , 38)
f2[6] = 32 l2[6] = 2
j 1 2 3 4 5 6
f1[j] 8 11 14 20 28 33
f2[j] 4 8 16 21 25 32
j 2 3 4 5 6
l1[j] 2 1 1 1 2
l2[j] 2 2 1 2 2
Keeping Track for Constructing Optimal Solution

f* = min (f1[6] + x1, f2[6] + x2)
f* = min (33 + 3, 32 + 6)
f* = min (36, 38)
f* = 36
Hence, the minimum time required by auto from starting point to exit point of the factory is
36.
The auto will take minimum time from starting point to the exit point if and only if it has
come out from the 6th station of assembly line 1.
Therefore, l* = 1

Fastest Way: Assembly-Line Scheduling – Optimal Path
l* = 1 => Station S1,6

l1[6] = 2 => Station S2,5
l2[5] = 2 => Station S2,4
l2[4] = 1 => Station S1,3
l1[3] = 1 => Station S1,2
l1[2] = 2 => Station S2,1

CS702 Mid Term SolvedMegaFile Khurshid PDF

Uploaded by

Copyright:

Available Formats

CS702 Mid Term SolvedMegaFile Khurshid PDF

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

CS702 Mid Term SolvedMegaFile Khurshid PDF

Uploaded by

Copyright:

Available Formats

CS702 Advance Algorithm and Design Khurshid Iqbal [MS160400288]

CS702 MID TERM PAPERS SOLVED

Question: Prove logab . logbc = logac

Question: Prove 3log4n = nlog43

[Mid Term Solved Questions] 1

Question: Asymptotic Notations Properties

[Mid Term Solved Questions] 2

Major Factors in Algorithms Design

[Mid Term Solved Questions] 3

[Mid Term Solved Questions] 4

Question: Prove that 2n2 ϵ O(n3)

Questions: Prove that f(n) = O(g(n))

[Mid Term Solved Questions] 5

[Mid Term Solved Questions] 6

Question: Prove that f(n) = o(g(n)) ⇔ g(n) = ω (f(n))

[Mid Term Solved Questions] 7

Question: Big-Omega Notation (Ω)

If f, g: N → R+, then we can define Big-Omega as

Question: Prove that f(n) = O (g(n)) ↔ g(n) = Ω (f(n)) (Omega)

[Mid Term Solved Questions] 8

Question: Prove that f(n) = o(g(n))  g(n) = ω f(n))

Question: Prove that 5.n2 Є ω(n) OR [5n2 Є ω(n)]

[Mid Term Solved Questions] 9

Question: Prove that 100.n ∉ ω(n) OR [100n ∉ ω(n)]

[Mid Term Solved Questions] 10

[Mid Term Solved Questions] 11

Solving Modular Linear Equations

Question: Proof by Induction Prove that n2 ≥ n + 100 ꓯ n ≥ 11

3. Now it can be proved that

P(k+1) * (k+1)2 ≥ (k+1) + 100,

Hence P(k) ≥ P(K+1)

[Mid Term Solved Questions] 12

Question: If n Є Z, n >1, then n can be written as Product of Primes.

[Mid Term Solved Questions] 13

If n = p, a prime number, then (p) = (p-1); e.g. ((7) = 6 because 7 is prime)

[Mid Term Solved Questions] 14

[Mid Term Solved Questions] 15

• Hence any odd integer has the form 8m + 1 for some m

[Mid Term Solved Questions] 16

p ≤ square root n i.e. p ≤ √𝒏.

[Mid Term Solved Questions] 17

[Mid Term Solved Questions] 18

Question: Prove that 5.n2 ϵ Ω(n) (Omega n)

[Mid Term Solved Questions] 19

Question: n3 + 4n2 = Ω(n2) [Omega]

[Mid Term Solved Questions] 20

Question: From asymptotic notation prove Theeta function / Theeta

[Mid Term Solved Questions] 21

Question: Prove that 1/2.n2 – 1/2.n = Θ(n2) OR [1/2 n2 – 1/2n]

[Mid Term Solved Questions] 22

[Mid Term Solved Questions] 23

Question: Prove that n2 Є O(n2)

Question: Prove that 1000.n2 + 1000.n Є O(n2)

[Mid Term Solved Questions] 24

Question: Prove that n3 Є O(n2)

Question: Prove by contradiction that g(n) = n3 is not O(n2)

Assume that g(n) is O(n2 ). Then there are positive reals c

[Mid Term Solved Questions] 25

[Mid Term Solved Questions] 26