Set by :

Molla K.
Outline
Introduction and Elementary Data Structures
1.1. Introduction to Algorithm analysis
1.1.1. Asymptotic Notations
1.1.2. Analysis of Algorithm
1.2. Review of elementary Data Structures
1.2.1. Heaps
1.2.2. Hashing
1.2.3. Set Representation
1.2.3.1. UNION, FIND Operation
2
What is an Algorithm?
 An algorithm is a finite set of well-defined instructions to be followed for solving a problem.
 It comes from the name of the Persian author Abu, JA, far Mohammed Ibn Musa
alkhowarizmi in 825 AD.
 The sequence of computational steps to solve a problem is said to be algorithm.
 Data Structure: It is the arrangement of data in Computer memory.
E.g linked list, Stack, Queue, Array.

Problem
Program= Algorithm + Data Structure
Algorithm

Input Computer Output

3
Characteristics of an Algorithm
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. It is absence of ambiguity
 Finiteness: If we trace out the instructions of an algorithm, then for all cases, the
algorithm terminates after a finite number of steps.
 Effectiveness: Doing the right thing and it should give the correct result all the time.
 Completeness: It must solve the problem completely.
 Sequential: it indicates start step and end step  Precision and simplicity
 Correctness: it must compute correct answer for all possible valid inputs.
 Efficiency:: using low resources such as time and space.
4
Algorithm Analysis
 AA : refers to the process of determining the amount of computing time and storage space
required by different algorithms.
 It is the determination of the amount of time and space resources required to execute it.
 Analyzing an algorithm has come to mean predicting the resources that the algorithm requires.

 An algorithm is mainly analyzed to determine the execution time of the

program and how much memory space required.
 Analysis of algorithm is important for the following reasons:
 Analysis is more reliable than the experimental testing.
 Analysis helps to select better algorithm.
 Analysis predicts performance.
 Analysis identifies the scope of improvement of algorithm 5
…Cont’d
 The efficiency of the algorithm can be decided by measuring the performance of an
algorithm.

 We can measure the performance of an algorithm by computing two factors:

1.Amount of time required by an algorithm to execute.
2.Amount of storage required by an algorithm.

6
Space Complexity
 The space complexity of an algorithm is the amount of memory it needs to run to completion.

 To compute the space complexity we use two factors: Constant and Instance characteristics.

S(P) = C + SP

Where SP is the instance characteristics and c is a constant.

 Space complexity must be taken seriously for multiuser systems and in
situations where limited memory is available.
 Space complexity refers to the total amount of memory space used by an algorithm/program, including
the space of input values for execution.
 Calculate the space occupied by variables in an algorithm/program to determine space complexity.
7
Calculating the Space Complexity
 For calculating the space complexity, we need to know the value of memory used by
different type of datatype variables.
// n is the length of array a[]
//4*n bytes of space is required for the
array a[] elements.
int sum(int a[], int n) {
int x = 0; // 4 bytes for x
for(int i = 0; i < n; i++) // 4 bytes for i
{
x = x + a[i]; //4 bytes each for x, n, i and the return value.
}
return(x);
}
Total memory requirement will be (4n + 12)

8
Time Complexity
 The time complexity of an algorithm is the amount of computer time it
needs to run to completion.

 It is a function describing the amount of time an algorithm takes in terms

of the amount inputs to algorithm.

 The time taken by a program is the sum of the compile time and run time.
 The compile time does not depend on the instance characteristics.
 The only factor that affects the measure complexity is the input size of an algorithm. There are 3
types of analysis of program efficiency

9
Cont’d
 Worst-Case (Usually): It is the amount of time an algorithm takes on the worst case possible set
of inputs.

 T (n) = Maximum time of algorithm on any input of n size. It compute upper bond of T (n),
longest running time for any input size n

 Average-Case (Sometimes): It is the amount of time the algorithm takes on any inputs size.

 T (n) = Expected time (mean time) of an algorithm over all inputs of size n.

 It computes optimal (the one which is found on most of the time) bound of T (n).

 Best-Case (Bogus): It is the amount of time the algorithm takes on the smallest possible set of
inputs. It computes the lower bound of T (n).

 Best-Case is the cheapest among all input of size n.

10
Cont’d
Example1:

int count(){
1 for the assignment statement: int k=0
int k=0;
1 for the output statement.
cout<< “Enter an integer”;
1 for the input statement.
cin>>n;
for (i=0;i<n;i++) In the for loop:
k=k+1; 1 assignment, n+1 tests, and n increments.
return 0; n loops of 2 units for an assignment, and an addition.
} 1 for the return statement.

T (n)= 1+1+1+(1+n+1+n)+2n+1 = 4n+6 = O(n)

11
Cont’d
Exercise 1 while (i<n){
Example 2: x++; i++;
void func()
i=0 }
{
While(i<n)
int x=0; while (j<n) {
{
Statement; int i=0; j++;
i++ }}
int j=1;
}
cout<< “Enter an integer value”;
T(n)= 3n+2
T(n)= O(n) cin>>n;

T (n)= 1+1+1+1+1+n+1+2n+n+n-1 = 5n+5= O(n)

12
Asymptotic Analysis
 Asymptotic analysis is concerned with how the running time of an algorithm
increases with the size of the input in the limit, as the size of the input
increases without bound.
 Algorithm Analysis: T (n) -> is the computing time of an algorithm for
input size n.

 Generally, the complexity is investigated in three cases.

1.Best Case − Minimum time required for program execution.
2.Average Case − Average time required for program execution.
3.Worst Case − Maximum time required for program execution.
13
Asymptotic Notations
 Asymptotic Notation: analysis of algorithm concerned with how running time
of an algorithm increase with the size of the input.
Following are the commonly used asymptotic notations to
calculate the running time complexity of an algorithm. There are
more than 3 notations
Big-Oh Notation (O)

Big-Omega Notation (W)

Theta Notation (Θ)

14
Big-Oh Notation(O)
 The notation Ο(n)is the formal way to express the upper bound of an algorithm's running time.
 It is always upper bound and worst-case.
 It has more than a solution for big oh and big omega.
 It measures the worst case time complexity or the longest amount of time an algorithm can
possibly take to complete.

 The function f (n) = O(g (n)), Iff ∋ +ve constants C and n0 , such that f(n) ≤ (c*g(n)) for ∀ n≥ n0

Example. Let f(n) =2n+3

2n+3 ≤ 2n2+3n2
2n+3 ≤ 5n2 , n≥ 1
f(n) =2n+3, c= 5, g(n)=n2
So, f(n) = O(n2 )
15
Omega Notation(Ω)
 The notation Ω(n) is the formal way to express the lower bound of an
algorithm's running time.
 It is also called lower bound and Best case.
 It measures the best case time complexity an algorithm can possibly take to complete.

f (n) = (g(n)). Iff ∋ +ve constants C and n0 such that

f(n)  c*g (n) ∀ n  n0, C>0, n0 ≥ 1
The growth rate of f (n) is greater than or equal to the
growth rate of g (n).

Example: f(n) =2n+3

2n+3  1*n ∀ n≥ 1
f(n) =2n+3, c= 1, g(n)= n
So, f(n) = (n)
16
Theta Notation(Θ)
 Theta notation encloses the function from above and below.
 Average case and it is called tight bound.
 Since, it represents the upper and the lower bound of the running time of an algorithm.
 It is used for analyzing the average case complexity of an algorithm.
f (n) = 𝜽(g(n)). Iff ∋ +ve constants C1, C2 and n0 such that
c1*g (n) ≤ f(n) ≤ c2*g(n). ∀ n  n0, C>0, n0 ≥ 1
Example: f(n)= 2n+3
=> 1*n ≤2n+3 ≤5n
=> c1= 1, g(n)= n. f(n)= 2n+3, c2= 5, g(n)=n
so, f(n)= (n).
 The theta describes the best idea about the growth of the
function rate because it gives tight bound.
 If both WC and BC are the same we use average case.
17
Rate of Growth

18
Recurrence Relation
 It is an equation which is defined in terms of it. So many algorithms are recursive
in nature.
e.g. : void Test (int n) { // T (n)
if (n>0) //1
for(i=0;i<n;i++){ //n+1
Print (”%d”, n); //n
}
Test(n-1); // T(n-1)
}}

T(n)=T(n-1)+2n+2=2n+2=O(n)

19
Cont‟d
by using back substitution method we can solve it:
1
T (n) = T (n-1) +n ......
2
T (n) = T(n-2) +(n-1) +n…..
3
T (n) = T(n-3) + (n-2) + (n-1) +n…
T (n) = T(n-k) + (n-(k-1) + (n-(k-2)+…(n-1)+n…. 4
Let n-k=0=> n=k
T (n) = ((n-n) + (n-n+1) + (n-n+2) +….+ (n-1) + n)
T (n) = ((0) + (1) + (2) +3+……………….+ (n-1) +n
𝑛+1
T (n) =1+𝑛( )= O (n2)
2
so, O(n2)

20
Masters Theorem
 Let a≥1 and b≥1 be constant, let f (n) be defined on the non-negative integers by the
recurrence i.e T (n) =aT (n/b) +f (n).
 Some functions that are not evaluated by using BS and recursion tree method can be
solved by using this theorem.
Note: E.g. T (n) = 9T (n/3) +n= θ(n2)
1. If a > bk , then T(n) = (nlogba )
Example. 3T(n/2)+n2
2. If a=bk
Ans: a=3, b=2, k=2, p=0
If p> -1, then T(n)= (nlogbalogp+1 n)
Compare a<bk
If p= -1, then T(n)= (nlogbaloglogn)
3 22 =3<4, so use
If p < -1, then T(n)= (nlogba)
T(n)= (nklogpn)= (n2log0n)= (n2)
3. If a<bk
If p≥0, then T(n)= (nklogpn) e.g. 2 T(n)= 2T(n/2)+nlogn………exercise

If p<0 ,then T(n)= (nk) 21

Type of Time Functions
O (1) -> Constant
O (logn) ->Logarithmic
O (n) - >Linear
O (n2) ->Quadratic
O (n3) ->Cubic
O (2n) -> Exponential
O (3n) ->O (Nn)

Note: 1<logn< 𝑛 <n <Nlogn<N2<n3---2n<3n <N n in increasing order of classes of
function

22
Review of Elementary Data Structures
 One of the basic techniques for improving algorithms is to structure the data in such a
way that the resulting operations can be efficiently carried out.

 We should be familiar with stacks and queue, binary trees, and graphs and be able to refer
to the other structures as needed.
 Array: It is the simplest data structure.
 It is used to store similar type‟s data.
 We can access element of an array by using index.
 It runs from 0 to n-1.
 Adjacency between two elements is essential.
 There are two types of an array:
23
One Dimensional Array:

Example:

 Multi-Dimensional Array: It is an array of array. It has more than one dimensional array.
Eg

 Linked List: It is the list consists of a series of cells (record). Adjacency is NOT essential.
Each record contains elements and pointer.

24
Stacks and Queues
 Stack : It is also list with a restriction that insertion and deletion of an element is done
at the same end.
 The two operations are used pop and push.
 LIFO principle is applied.
 Queue: It is also list where insertion and deletion done at the opposite end.
 Two operations are used enque and deque.
 It follows a FIFO principle is applied

25
Sets
 It is a collection of non-repetitive element where each element is a set or atomic. Two operations
UNION and FIND.

e.g. S1= {1, 3, 4} S2 = {5, 6, 7} S1 U S2= S2 U S1- false

26
Graphs
 It is defined as G= (V, E) where ‘V’ is a set of vertices and ‘E’ a set of edges where E ≤VxV.

27
Tree
 It is non-linear data structure. It is a graph where it is exactly one between
E.g any pair of vertices. A graph connected with out cycles.

28
Disjoint Set
It has two operations i.e FIND and UNION

Given S1= {1, 2, 3, 4} S2= {5, 6, 7, 8}

S2= {5, 6, 7, 8}

S1nS2= ∅ // Disjoint set use (4, 8) and (1, 5)

S1US2= {1, 2, 3, 4, 5, 6, 7, 8} // new set

So (1, 5) exist in the set there is cycle in the graph. 29

Cont’d

Example 2: Given U= {1, 2, 3, 4, 5, 6, 7, 8}

(1,2) (3,4) (5,6) (7,8) (2,4) (2,5) (1,3) (6,8) (5,7) (1, 2)
(3, 4)
S1= {1, 2} // Remove
(5, 6)
S2= {3, 4} (7, 8)
(2, 4)
S3= {5, 6}
(2, 5)
S4= {7, 8} (1, 3)

S5=S1US2= {1, 2, 3, 4} (6, 8)

(5, 7)
S6= {1, 2, 3, 4, 5, 6}
S7 = {1, 2, 3, 4, 5, 6, 7, 8}

30
Heap
 It is binary tree or 3-nary tree. It is FIFO.
 It is almost complete binary tree which leaves must be present in the last.
 A heap is a complete binary tree with some special properties.
 The basic requirement of a heap is that the value of a node must be ≥ (or ≤)
than the values of its children. Example

Heap Not a heap

31
Heap Representation
 An efficient representation of the heap is using array.
 The root is stored at the first place, that is a[0].
 The children of the node i is at the locations ((2*i) and ((2*i) +1).

L=2i and R=2i+1

i.e LC (i) =2i, RC (i) = 2i+1 and
P (i) = 𝑖/2

1 2 3 4 5 6
100 10 20 1 4 3

6
 So to find the parent of node we use the following formula: 5/2 = 2 = 𝑖/2 =2 and = 3 = 20
2

32
Cont’d
 Note: if n-number array is given to construct or create max heap: O (Nlogn) and we apply
descending order. Therefore, height of any binary tree is O(logn)
H (T) =2
 This is complete binary tree having 7-nodes. It has the property
height 2, 1, 0=H (T) =2
 All nodes existing the same level has the same height.
 What is the maximum number of node in complete binary tree at
height 2? Ans: 7
 So Max Node = (2 h+1_1) where h is a height since height=
logn=if a heap has 3-nodes=log3=1.
 Example: h= 6, max node= 2 h+1_1= 2 6+1 -1= 128-1= 127 max
node with height h. If I have 3, 7, 15 nodes the time complexity is
calculated by using 𝑙𝑜𝑔𝑛 . = 𝑙𝑜𝑔3 .=1, log 7 .=2 and
𝑙𝑜𝑔15 =3 33
Cont’d
 Both time & space complexity T (n) = O (logn) and S (n) =
O (logn)

Where the node is start?

 If n- is given find n-position in binary tree ( 𝒏/𝟐 +1 to n).
 This shows leaves. E.g if I have n=5 =( 5/2 +1 to 5)

=2+1=3-leaves
How to find non-leaves?
No of non-leaves= 1 to 𝒏/𝟐 e.g. n=8, 1 to 𝟖/𝟐 =1 to 4.

34
Building Heaps
1 5 6 8 12 14 16

 To heap compare each node. It takes O (nlogn)

 The time complexity of heap sort is O(nlogn).

35
Example
A 9 6 5 0 8 2 7 1 3
 The number recursive call is equal to
N/2 to n if N=9= 9/2 to 9=4+1 to 9=5 to 9 leaves the number of leaves.
 The time complexity depends on size
leaves for O (log0) O (log1) O (log2)…
It depends on height heap.

9 6 5 0 8 2 1 3
=
A

36
Cont’d
 How many nodes will be present at height “h” in binary tree? After heap building
H0 =
What is the height degree?
Ans :( O (logn), T (n) =O (nlogn)

𝑛 15
Example n=15, h=0, = ℎ +1 = 0 + 1 = 7.5 = 8- nodes.
2 2

 Since the number of nodes in completes or almost complete binary tree at height „h‟ is
 If the height is increase the work done also increase.
 The space complexity max-Heapify is O (logn). Because the max-Heapify called at the root and goes to
down.
 In order to build heap we do not need extra memory but we need stack.

37
Types of Heaps

 Based on the property of a heap we can classify heaps into two types:
1.Max heap: The value of a node must be greater than or equal to the values of its children
2. Min heap: The value of a node must be less than or equal to the values of its children

 The definition of a max heap implies that one of the largest elements is at the root of the heap.
 The definition of a mini heap implies that one of the largest elements is at the node of the heap.

Max heap Min heap

38
Extract-max-heap
Checks if the heap contains at
least one element. Delete 100 &
replace with 5

It decreases heap size

 If we want delete max we call the max-Heapify function i.e Max-Heapify (A, 1). So both time and
space complexity is O (logn).

 We can delete root element only from the heap and can delete the max element from the heap.

39
Insertion of an Element
Example: Insert an element 60 to the heap

Note: The time complexity for insertion logn but the minimum time complexity is O(1) and max is O(Logn)

40
Heapify
 Heapify the procedure to create a heap for the given array.
 Let consider a binary tree in which left and right subtrees of the root are
satisfying the heap property, but not the root. See the following figure. Time
complexity for Heapify is O(n)

10 20 15 12 40 25 18
A
1 2 3 4 5 6 7

 Now question is how to make the above tree into a heap?

 Swap the root and left child of root, to make the root satisfies the heap property.
 Then check the subtree rooted at left child of the root is heap or not.
41
Heap Sort
 Heap sort operates by first converting the list in to a heap tree.
 Heap tree is a binary tree in which each node has a value greater than both its children.

 It uses a process called "adjust to accomplish its task (building a heap tree) whenever a
value is larger than its parent. The time complexity of heap sort is O(nlogn)

 The time complexity of creating heap & deletion heap is O(nlogn).

 That is nlogn +nlogn=2nlogn= O(nlogn)

 There are two steps to sort heap

First create an array

Then delete all elements from the heap

42
Cont’d

43
Cont’d

44
Cont‟d

45
Hashing
 Hashing is the process of mapping large amount of data item to smaller table
with the help of hashing function.

 Hashing is also known as Hashing Algorithm or Message Digest Function.

 It is a technique to convert a range of key values into a range of indexes of an array.
 It is used to facilitate the next level searching method when compared with the linear or binary
search.

 Hashing allows to update and retrieve any data entry in a constant time O(1).
 Constant time O(1) means the operation does not depend on the size of the data.
 Hashing is used with a database to enable items to be retrieved more quickly.
 It is used in the encryption and decryption of digital signatures.
46
Cont’d
 A hash function generates a signature from a data object.
 Hash functions have security and data processing applications.
 A hash table is a data structure where the storage location of data is computed from
the key using a hash function.

 A hash table is a collection of items which are stored in such a way as to make it easy to
find them later.
 Each position of the hash table, often called a slot, can hold an item and is named
by an integer value starting at 0.
 Insertion and deletion at one time O (1). Hash function is nothing but it is simple function.
 Hashing technique is useful for searching.
47
Cont’d
 For example, we will have a slot named 0, a slot named 1, a slot named 2,
and so on. Initially, the hash table contains no items so every slot is empty.
 Figure below shows a hash table of size m=11.
 In other words, there are m slots in the table, named 0 through 10.

 The mapping between an item and the slot where that item belongs in the hash
table is called the hash function.

 The hash function will take any item in the collection and return an integer in the range
of slot names, between 0 and m-1.

48
Cont’d
 Given a collection of items, a hash function that maps each item into a unique slot is
referred to as a perfect hash function.
 If we know the items and the collection will never change, then it is possible to
construct a perfect hash function.

 One way to always have a perfect hash function is to increase the size of the hash
table so that each possible value in the item range can be accommodated.

 This guarantees that each item will have a unique slot.

 Although this is practical for small numbers of items, it is not feasible when the
number of possible items is large.
49
Cont’d
 Suppose we have integer items {26, 70, 18, 31, 54, 93}. One common method
of determining a hash key is the division method of hashing and the formula is :

 Hash Key = Key Value % Number of Slots in the Table

 Division method or reminder method takes an item and divides it by the table
size and returns the remainder as its hash value.

Data Item Value % No. of Slots Hash Value

26 26 % 10 = 6 6
70 70 % 10 = 0 0
18 18 % 10 = 8 8
31 31 % 10 = 1 1
54 54 % 10 = 4 4
93 93 % 10 = 3 3

50
Cont’d
 In the hash table, 6 of the 10 slots are occupied, it is referred to as the load
factor and denoted by, λ = No. of items / table size. For example , λ = 6/10.
 It is easy to search for an item using hash function where it computes the slot
name for the item and then checks the hash table to see if it is present.
 Constant amount of time O(1) is required to compute the hash value and index of
the hash table at that location.
 We can eliminate clustering by using chaining. Hash function amount is the
combination of two distinct things with which are quite familiar:
 Hash Function: it returns non-negative integer called hash code
 Array.
51
Cont’d
• A collision occurs when two pieces of data when run via the hash function
gives the same hash code.
 Resolving Collision: Linear probing. In this method, if we have a collision, we
try to place the data in the next consecutive element in the array (wrapping
around to the beginning if necessary) until we find a vacancy.
 Linear probing is subject to problem called clustering.
 Take the above example, if we insert next item 40 in our collection, it would
have a hash value of 0 (40 % 10 = 0).
 But 70 also had a hash value of 0, it becomes a problem. This problem is
called as Collision or Clash. Collision creates a problem for hashing technique.
52
1. What is an algorithm? Review Questions
2. Describe some important characteristics of algorithms?
3. Why analysis algorithms? List criteria's that affect run time of algorithm.

4. List commonly used asymptotic notations and explain with example?

5. Explain the difference between max heap and min heap
6. how to construct heap tree from unsorted array.
7. Write at least three applications of stack and queue.
8. Illustrate the operation of BUILD-MAX-HEAP on the array A =(15, 3,17, 10, 8, 4, 19, 6, 22, 9).
9. Perform the operation of HEAPSORT on the array A =(16, 5, 33, 2, 25, 7, 17, 20, 8, 4)
10. Describe asymptotic notation and analysis of algorithm .
11. f(x) =5n2+2n+1, find big-oh, omega and theta of the given function.
12. Solve the following recursive functions:
a. T(n)= 2nT(n/2)+nn c. T(n)= 2T(n/2)+nlogn
d. T(n)= 2T(n/2)+𝑛 𝑙𝑜𝑔𝑛
b.T(n)= 16T(n/4)+n
53
Cont‟d
1. Describe recursive algorithms with example.
2. What is recurrence relations? Submission date: 21/05/2014

3. List three techniques/ways to solve/analysis algorithms and briefly discuss with example.
4. What is the time complexity of HEAPSORT on an array A of length n that is already sorted in ascending order?
What about descending order?
5. Perform operation of heap deletion and MAX-HEAP-INSERT (A, 20) on the heap A=(15, 13, 9, 5, 12, 8, 7,
40, 6, 2, 11).
6. Solve the following recursive functions:
i. T(n)= 2T(n/2)+𝑛 𝑙𝑜𝑔𝑛
ii. T(n)= 6T(n/3)+n2logn

7. Show that is 2n+1 = O(2n) and is 22n = O(2n)? iii. T(n)= 7T(n/3)+n2
8. How to solve collision in hash table? iv. T(n)= 4T(n/2)+nlogn
9. What is Priority queue
10. What is the pros and cons of using algorithm?
11. Assume there are 50 students in the course tutorial. How will you compute the number of absentees in the tutorial?
54
Questions, Ambiguities, Doubts, … ???

Problem: Suppose there are 60 students in the

class. How will you calculate the number of
absentees in the class?

55
Questions, Ambiguities, Doubts, … ???

Cheaw !!!

See You Next Class!

56