CCS 3102 Lecture 2_ Mathematical foundations.pdf

A lecture on Data Analysis and Algorithms

1. Design and Analysis of
Algorithms
Mathematical foundations
Department of Computer Science

2. Mathematical Background
❖Analysis of algorithms requires knowledge of
mathematical tools such as:
Methods for evaluating and bounding
summations
Sets, relations, functions, graphs and trees
Counting: permutations and combinations
Probability and statistics
Monday, March 6, 2023Design and Analysis of Computer Algorithm 2

3. Sets
❖A set is a collection of distinguishable objects; called
members or elements
❖A set cannot contain the same element more than
once; a variation of this is called multiset
❖Given a set say S and element x then we can write:
❖ ( “x is in S”) OR (“x is not in S”)
❖Frequently used sets
the empty set
Z set of integers {…, -2,-1,0,1,2,…}
R set of real numbers
N set of natural numbers {0,1,2,…}
Monday, March 6, 2023Design and Analysis of Computer Algorithm 3Sx Sx θ

4. Set relations / operations
❖Subset AisasubsetofB
❖Propersubset if but
❖Intersection
❖Union
❖DifferenceA-B
Monday, March 6, 2023Design and Analysis of Computer Algorithm 4 BA BA BA BA BA BA

5. Why study algorithms and performance?
❖Algorithmshelpustounderstandscalability.
❖Performanceoftendrawsthelinebetweenwhatis
feasibleandwhatisimpossible.
❖Algorithmicmathematicsprovidesalanguagefor
talkingaboutprogrambehavior.
❖Performanceisthecurrencyofcomputing.
❖Thelessonsofprogramperformancegeneralizeto
othercomputingresources.
❖Speedisfun!
Monday, March 6, 2023Design and Analysis of Computer Algorithm 5

6. Methods of Proof
❖ProofbyContradiction
Assumeatheoremisfalse;showthatthisassumption
impliesapropertyknowntobetrueisfalse--therefore
originalhypothesismustbetrue
❖ProofbyCounterexample
Useaconcreteexampletoshowaninequalitycannot
hold
❖MathematicalInduction
Proveatrivialbasecase,assumetruefork,thenshow
hypothesisistruefork+1
Usedtoproverecursivealgorithms
Monday, March 6, 2023 6Design and Analysis of Computer Algorithm

7. Review: Induction
❖Suppose
S(k)istrueforfixedconstantk
▪Oftenk=0
S(n)S(n+1)foralln>=k
❖ThenS(n)istrueforalln>=k
Monday, March 6, 2023 7Design and Analysis of Computer Algorithm

8. Proof By Induction
❖Claim:S(n)istrueforalln>=k
❖Basis:
Showformulaistruewhenn=k
❖Inductivehypothesis:
Assumeformulaistrueforanarbitraryn
❖Step:
Showthatformulaisthentrueforn+1
Monday, March 6, 2023 8Design and Analysis of Computer Algorithm

9. Induction Example:
Gaussian Closed Form
❖Prove1+2+3+…+n=n(n+1)/2
Basis:
▪Ifn=0,then0=0(0+1)/2
Inductivehypothesis:
▪Assume1+2+3+…+n=n(n+1)/2
Step(showtrueforn+1):
1+2+…+n+n+1=(1+2+…+n)+(n+1)
=n(n+1)/2+n+1=[n(n+1)+2(n+1)]/2
=(n+1)(n+2)/2=(n+1)(n+1+1)/2
Monday, March 6, 2023 9Design and Analysis of Computer Algorithm

10. Induction Example:
Geometric Closed Form
❖Prove a
0
+ a
1
+ … + a
n
= (a
n+1
-1)/(a -1) for
all a 1
Basis: show that a
0
= (a
0+1
-1)/(a -1)
a
0
= 1 = (a
1
-1)/(a -1)
Inductive hypothesis:
▪Assume a
0
+ a
1
+ … + a
n
= (a
n+1
-1)/(a -1)
Step (show true for n+1):
a
0
+ a
1
+ … + a
n+1
= a
0
+ a
1
+ … + a
n
+ a
n+1
= (a
n+1
-1)/(a -1) + a
n+1
= (a
n+1
–1+ a
n+1+1
–a
n+1
)/(a -1)
= (a
n+1+1
-1)/(a -1)
Monday, March 6, 2023 10Design and Analysis of Computer Algorithm

11. Induction
❖We’ve been using weak induction
❖Strong inductionalso holds
Basis: show S(0)
Hypothesis: assume S(k) holds for arbitrary k <=
n
Step: Show S(n+1) follows
❖Another variation:
Basis: show S(0), S(1)
Hypothesis: assume S(n) and S(n+1) are true
Step: show S(n+2) follows
Monday, March 6, 2023 11Design and Analysis of Computer Algorithm

12. Loop Invariants
❖Weuseloopinvariantstounderstandwhyan
algorithmiscorrectbyshowing3things:
1.Initialisation-itistruepriortothefirstiterationof
theloop
2.Maintenance–ifitistruebeforeaniterationofthe
loop,itremainstruebeforethenextiteration
3.Termination–whentheloopterminates,the
invariantgivesusausefulpropertythathelpsus
showthatthealgorithmiscorrect
Monday, March 6, 2023 12Design and Analysis of Computer Algorithm

13. Loop Invariants in Use
InsertionSort
1forj=2ton
2x=A[j]
3i=j−1
4whilei>0andA[i]>x
5A[i+1]=A[i];
6i=i−1
7A[i+1]=x
Monday, March 6, 2023 13Design and Analysis of Computer Algorithm

14. Correctness of insertion sort
❖Each time execution reaches (2), the
elements A[1..j − 1] (i.e. s′) are in sorted
order, and they are the same elements as
were originally in A[1..j − 1] (permuted).
❖The elements A[j ..n] (i.e. s) are unchanged.
(1) perm(A[1..j − 1],A0[1..j − 1])
(2) ordered(A[1..j − 1])
(3) A[j ..n] = A0[j ..n]
❖This is a loop invariant for the outer loop.
Monday, March 6, 2023 14Design and Analysis of Computer Algorithm

15. Using the invariant to prove correctness
❖Initialization: Show that the loop invariant
holds prior to the first iteration.
Here, j = 2, so A[1..j − 1] is just the singleton
A[1].
(1) A0[1] = A[1], so the permutation is trivial.
(2) {A[1]} is trivially ordered.
(3) A[2..n] = A0[2..n].
Monday, March 6, 2023 15Design and Analysis of Computer Algorithm

16. Using the invariant to prove correctness
❖Maintenance:Assume that the loop invariant holds
before some iteration. Show that it will hold again
before the next.
(1) Assume perm(A[1..j − 1],A0[1..j − 1]) and show
perm(A′[1..j ′ − 1],A0[1..j ′ − 1]), where j ′ = j + 1
and A′ is the array A after execution of lines 2–7.
(2) Assume ordered(A[1..j − 1]) and show ordered
(A′[1..j ′ − 1]).
(3) A[j ..n] = A0[j ..n] because we have not yet
touched this part of the array.
Monday, March 6, 2023 16Design and Analysis of Computer Algorithm

17. Using the invariant to prove correctness
❖Termination:Assume that the loop invariant
holds, and that the loop has terminated.
Show that the postcondition is satisfied.
❖Here, the loop terminates with j = n + 1.
(1) perm(A[1..j − 1],A0[1..j − 1]) implies
perm(A[1..n],A0[1..n]).
(2) ordered(A[1..j − 1]) implies ordered(A[1..n]).
(3) A[j ..n] is empty.
Monday, March 6, 2023 17Design and Analysis of Computer Algorithm

18. Using the invariant to prove correctness
❖We should also show that the program actually
does terminate. In this this case, the outer loop
executes exactly n − 1 times.
❖The inner loop starts with i = j − 1, which is a
positive value; at each iteration, i is decremented;
and the loop exits when i = 0 (or perhaps sooner,
depending on x and A). This guarantees
termination.
❖The other operations in the algorithm are all
assignments or comparisons, which (we assume)
always terminate.
Monday, March 6, 2023 18Design and Analysis of Computer Algorithm