DESIGN AND ANALYSIS OF ALGORITHMS

Dr. PV Nageswara Rao

Professor, Dept. of CSE
GIT, GITAM(Deemed to be university)
Visakhapatnam

Lecture 3: Introduction

1
Dept. of Computer Science and Engineering, GIT, GU, Visakhapatnam 10/22/2024 3:32 PM
MODULE - I

 Introduction:
 Algorithm specification
 Performance analysis
 Divide and Conquer
 The general method, Program Abstraction
 Binary search
 Finding maximum and minimum
 Merge sort
 Quick sort selection
 Strassen's matrix multiplication.

Dept. of Computer Science and Engineering, GIT, GU, Visakhapatnam

2
10/22/2024 3:32 PM
ALGORITHM:
 An algorithm is a finite set of instructions, that if followed,
accomplishes a particular task. In addition, all algorithms must
satisfy the following criteria:
 Input: Zero or more quantities are externally supplied.
 Output: At least one quantity is produced.
 Definiteness: Each instruction is clear and unambiguous.
 Finiteness: If we trace out the illustration of a an algorithm, then for
all cases, the algorithm terminates after a finite number of steps.
 Effectiveness: Every instruction must be very basic so that it can be
carried out, in principle, by a person using only pencil and paper.
 (Algorithms that are definite and effective are also called as
computational procedures. Example: Operating System)

Dept. of Computer Science and Engineering, GIT, GU, Visakhapatnam

3
10/22/2024 3:32 PM
STUDY OF ALGORITHMS:

 How to devise algorithms

 How to validate algorithms
 How to analyze algorithms
 How to test a program

Dept. of Computer Science and Engineering, GIT, GU, Visakhapatnam

4
10/22/2024 3:32 PM
 How to devise algorithms:
 Writing an algorithm is an art which may never be fully automated
 By mastering some design strategies, new design strategies/algorithms can be devised.

 How to validate algorithms:

 Algorithm validation is the process of ensuring that it is generating correct results for all possible
legal inputs.
 The algorithm can be verified independently of the programming language
 Program proving and Program verification is the next step.
 Program proving or Program verification
 Annotated by set of assertions about the input and output as expressed in predicate calculus
 Specification in predicate calclus

 How to analyze algorithms: (Analysis of Algorithms or Performance Analysis)

 How much computing time and memory/storage required?
 Quantitative judgement about the value of one algorithm over another.
 To predict whether the software will meet efficiency constraints that exists.

Dept. of Computer Science and Engineering, GIT, GU, Visakhapatnam

5
10/22/2024 3:32 PM
 How to test a program:
 Debugging is the process of executing programs on sample data sets to
determine whether faulty results occur and, if so, to correct them.
 (Debugging can only points to the presence of errors but not to their absence:
E. Dijkstra)
 A proof of correctness is much more valuable than thousand tests.
 Two programmers concept.

 Profiling(Performance Measurement) is the process of executing the correct

program on data sets and measuring the time and space it takes to compute
the results.

Dept. of Computer Science and Engineering, GIT, GU, Visakhapatnam

6
10/22/2024 3:32 PM
ALGORITHM SPECIFICATION:

 Comments, Blocks, Identifiers, data types(not explicitly declared),

assignment statement, logical operations, elements of
multidimensional arrays and their access, records, sets, lists,
looping statements, conditional statements, input and output
statements, procedures, arguments passing, etc.

Dept. of Computer Science and Engineering, GIT, GU, Visakhapatnam

7
10/22/2024 3:32 PM
EXAMPLE: SELECTION SORT Comments, Blocks, Identifiers,

data types(not explicitly
declared), assignment
1. Algorithm SelectionSort(a,n) statement, logical operations,
elements of multidimensional
2. // Sort the array a[1:n] into non decreasing order. arrays and their access,
3. { Index element looping statements,
4. for i := 1 to n-1 do 1 22 conditional statements, input
and output statements,
5. { 2 27
procedures, arguments
3 20
6. lk := i passing, etc.
4 28
7. for k := i+1 to n do 5 12
8. If (a[k] < a[lk] then lk := k; 6 17
9. t := a[i]; a[i] := a[lk]; a[lk] := t; 7 8
8 23
10. } // end of for loop
11. } // end of SelectionSort Algorithm

Dept. of Computer Science and Engineering, GIT, GU, Visakhapatnam

8
10/22/2024 3:32 PM
RECURSIVE FUNCTIONS

 A recursive function is a function that is defined in terms of itself.

 Direct recursion
 Indirect recursion / mutual recursion
 Examples: Factorial, Binomial coefficient, Towers of Hanoi, Ackermann’s function.

Dept. of Computer Science and Engineering, GIT, GU, Visakhapatnam

9
10/22/2024 3:32 PM
ALGORITHM: TOWERS OF HANOI:

Dept. of Computer Science and Engineering, GIT, GU, Visakhapatnam

10
10/22/2024 3:32 PM
ALGORITHM: ACKERMANN’S FUNCTION

Dept. of Computer Science and Engineering, GIT, GU, Visakhapatnam

11
10/22/2024 3:32 PM
PERFORMANCE ANALYSIS

 1. Does it do what we want it to do?

 2. Does it work correctly according to the original specifications of the task?
 3. Is there documentation that determines how to use it and how it works?
 4. Are procedures created in such a way that they perform logical sub-functions?
 5. Is the code readable?

Dept. of Computer Science and Engineering, GIT, GU, Visakhapatnam

12
10/22/2024 3:32 PM
SPACE/TIME COMPLEXITY
 The space complexity of an algorithm is the amount of memory it
needs to run to completion.
 The time complexity of an algorithm is the amount of computer
time it needs to run to completion.

 Performance Evaluation
 A priori estimates(performance analysis)
 A posteriori testing(performance measurement)

Dept. of Computer Science and Engineering, GIT, GU, Visakhapatnam

13
10/22/2024 3:32 PM
SPACE COMPLEXITY S(P)=C+SP(I)

 Aggregate:
Fixed Space Requirements (C)
Independent of the characteristics of the inputs and outputs
 instruction space
 space for simple variables, fixed-size structured variable, constants
 Variable
Space Requirements (SP(I))
depend on the instance characteristic I
 number, size, values of inputs and outputs associated with I
 recursive stack space: formal parameters, local variables, return address

S(P)=c+SP(Instance Characteristics)

14
Dept. of Computer Science and Engineering, GIT, GU, Visakhapatnam 10/22/2024 3:32 PM
 15
Dept. of Computer Science and Engineering, GIT, GU, Visakhapatnam 10/22/2024 3:32 PM
TIME COMPLEXITY:

 The time T(P) taken by a program P is the sum of the compile time and the run
(or execution) time.
 The compile time does not depend on the instance characteristics.
 A compiled program will be run several times without recompilation.
 Consequently we concern ourselves with just the run time of a program.
 This run time is denoted by tp instance characteristics

16
Dept. of Computer Science and Engineering, GIT, GU, Visakhapatnam 10/22/2024 3:32 PM
 STEP COUNT

 A program step is loosely defined as a syntactically or semantically meaningful

segment of a program that has an execution time that is independent of the
instance characteristics.

17
Dept. of Computer Science and Engineering, GIT, GU, Visakhapatnam 10/22/2024 3:32 PM
 s/e : steps per execution
The s/e of a statement is the amount by which the count changes as a result of 18
the execution
Dept. of Computer of thatGIT,statement.
Science and Engineering, GU, Visakhapatnam 10/22/2024 3:32 PM
 19
Dept. of Computer Science and Engineering, GIT, GU, Visakhapatnam 10/22/2024 3:32 PM
 20
Dept. of Computer Science and Engineering, GIT, GU, Visakhapatnam 10/22/2024 3:32 PM
 Definition
ASYMPTOTIC NOTATION (O)
 f(n) = O(g(n)) (read as: “f of n is big oh of g of n”) iff there exist positive constants c and n0 such that
f(n)  c*g(n) for all n, n  n0.
 Examples
 3n+2=O(n) // 3n+2  4n for n2
 3n+3=O(n) // 3n+3  4n for n3
 100n+6=O(n) // 100n+6  101n for n6
 10n2+4n+2=O(n2) // 10n2+4n+2  11n2 for n5
 1000n2+100n-6 = O(n2) // 1000n2+100n-6  1001n2 for n  100
 6*2n+n2=O(2n) // 6*2n+n2  7*2n for n4
 3n+3=O(n2) // 3n+3  3n2 for n  2
 10n2+4n+2=O(n4) // 10n2+4n+2  10n4 for n2
 3n+2 ≠O(1) as 3n+2 is not less than or equal to c for any constant c and all n>n0
 10n2+4n+2≠O(n)
 Conclusion: The statement f(n)=O(g(n)) states only that g(n) is an upper bound on the value of f(n) for all n,
n>=n0.
 The statement f(n)=O(g(n)) to be informative, g(n) should be as small a function of n as one can come up
with f(n)=O(g(n))
21
Dept. of Computer Science and Engineering, GIT, GU, Visakhapatnam 10/22/2024 3:32 PM
 ASYMPTOTIC NOTATION (Ω)
 Definition
 f(n) = Ω(g(n)) (read as: “f of n is big omega of g of n”) iff there exist positive constants c and n0 such
that f(n)  c*g(n) for all n, n  n0.
 Examples
 3n+2=Ω(n) // 3n+2  3n for n1
 3n+3= Ω(n) // 3n+3  3n for n1
 100n+6= Ω(n) // 100n+6  100n for n1
 10n2+4n+2= Ω(n2) // 10n2+4n+2  10n2 for n1
 1000n2+100n-6 = Ω(n2) // 1000n2+100n-6  1000n2 for n  1
 6*2n+n2= Ω(2n) // 6*2n+n2  2n for n1
 3n+3= Ω(1) // even though correct, we never say
 10n2+4n+2= Ω(1) // even though correct, we never say
 10n2+4n+2 = Ω(n) // even though correct, we never say
 Conclusion: The statement f(n)= Ω(g(n)) states only that g(n) is an lower bound on the value of f(n) for all n,.
 The statement f(n)= Ω(g(n)) to be informative, g(n) should be as large a function of n as one can come up
with f(n)= Ω(g(n))

34
Dept. of Computer Science and Engineering, GIT, GU, Visakhapatnam 10/22/2024 3:32 PM
 ASYMPTOTIC NOTATION (Ѳ)

 Definition
 f(n) = Ѳ(g(n)) (read as: “f of n is big theta of g of n”) iff there exist positive constants c1, c2 and n0
such that c1*g(n)<= f(n)  c2*g(n) for all n, n  n0.
 Examples
 3n+2=Ѳ(n) // 3n+2  3n for all n  2 and 3n+2  4n for n2 c1=3 , c2=4 and n0=2
 3n+3= Ѳ(n) // 3n+3
 10n2+4n+2= Ѳ(n2) 6*2n+n2= Ѳ(2n)
 10* log n +4 = Ѳ(log n)
 3n+2 ≠ Ѳ(1)
 3n+3 ≠ Ѳ(n2)
 10n2+4n+2 ≠ Ѳ(n)

 The theta notation is more precise than both the big oh and big omega notations.
 The function f(n) = Ѳ (g(n)) iff g(n) is both an upper and lower bound on f(n).

35
Dept. of Computer Science and Engineering, GIT, GU, Visakhapatnam 10/22/2024 3:32 PM
  O(1): constant
 O(log n) : Logarithmic
 O(n): linear
 O(n log n) loglinear
 O(n2): quadratic
 O(n3): cubic
 O(2n): exponential

36
Dept. of Computer Science and Engineering, GIT, GU, Visakhapatnam 10/22/2024 3:32 PM
FUNCTION VALUES

37
Dept. of Computer Science and Engineering, GIT, GU, Visakhapatnam 10/22/2024 3:32 PM
PLOT OF FUNCTION VALUES

n log n

log n

38
Dept. of Computer Science and Engineering, GIT, GU, Visakhapatnam 10/22/2024 3:32 PM
TIMES ON A 1 BILLION INSTRUCTION PER SECOND COMPUTER

39
Dept. of Computer Science and Engineering, GIT, GU, Visakhapatnam 10/22/2024 3:32 PM
 LEARNING OUTCOMES
The student will be able to
define and specify the characteristics of an algorithm. (L-1)
learn how to evaluate the performance of an algorithm . (L-1)
list different methods in analyzing time complexity. (L-1)
illustrate the efficiency of algorithms designed. (L-2)

40
Dept. of Computer Science and Engineering, GIT, GU, Visakhapatnam 10/22/2024 3:32 PM