Discrete Mathematics
Algorithm and types of
algorithm in data structure
Group Members
Komal Javid (Reg # 19101220-55)
Jawaria Naz (Reg # 19101220-62)
Sarwat Naqab (Reg # 19101220-85)
Sunila Kiran (Reg # 19101220-79)
Sidra Batool (Reg # 19101220-76)
Algorithm
Algorithm is a step-by-step procedure for calculation.
Algorithm is an affective method expressed as a finite list of well-
defined instructions for calculating functions.
Algorithm are used for calculation, data processing and automated
reasoning.
Algorithm
Most networking algorithms use the greedy approach. Here is a list
of few of them −
Travelling Salesman Problem
Prim's Minimal Spanning Tree Algorithm
Kruskal's Minimal Spanning Tree Algorithm
Dijkstra's Minimal Spanning Tree Algorithm
Graph - Map Coloring
Graph - Vertex Cover
Knapsack Problem
Job Scheduling Problem
Algorithm flowchart
Informal definition:
“set of rules that precisely defines a sequence of operations.”
Algorithm
Characteristics of an Algorithm
Not all procedures can be called an algorithm. An algorithm should have the
following characteristics −
Unambiguous − Algorithm should be clear and unambiguous. Each of its steps (or
phases), and their inputs/outputs should be clear and must lead to only one meaning.
Input − An algorithm should have 0 or more well-defined inputs.
Output − An algorithm should have 1 or more well-defined outputs, and should
match the desired output.
Finiteness − Algorithms must terminate after a finite number of steps.
Feasibility − Should be feasible with the available resources.
Independent − An algorithm should have step-by-step directions, which should be
independent of any programming code.
Algorithm Analysis
Efficiency of an algorithm can be analyzed at two different stages,
before implementation and after implementation. They are the
following −
A Priori Analysis − This is a theoretical analysis of an algorithm.
Efficiency of an algorithm is measured by assuming that all other
factors, for example, processor speed, are constant and have no
effect on the implementation.
A Posterior Analysis − This is an empirical analysis of an
algorithm. The selected algorithm is implemented using
programming language. This is then executed on target computer
machine. In this analysis, actual statistics like running time and
space required, are collected.
We shall learn about a priori algorithm analysis. Algorithm analysis
Algorithm Complexity
Suppose X is an algorithm and n is the size of input data, the time
and space used by the algorithm X are the two main factors, which
decide the efficiency of X.
Time Factor − Time is measured by counting the number of key
operations such as comparisons in the sorting algorithm.
Space Factor − Space is measured by counting the maximum
memory space required by the algorithm.
The complexity of an algorithm f(n) gives the running time and/or
the storage space required by the algorithm in terms of n as the size
of input data.
Algorithm
From the data structure point of view, following are some important
categories of algorithms −
Search − Algorithm to search an item in a data structure.
Sort − Algorithm to sort items in a certain order.
Insert − Algorithm to insert item in a data structure.
Update − Algorithm to update an existing item in a data structure.
Delete − Algorithm to delete an existing item from a data structure.
Types of Algorithm
Collections
A collection is a group of elements treated a single object.
Collection types can be:
Homogeneous or heterogeneous
Unordered or ordered
Linear, Hierarchical, Networked, or Non-Positional
The latter classification looks like this:
Types of Algorithm
Types of Algorithm
There are some top algorithm in data structure, every programmer should know –
Binary Search Algorithm
Sort Algorithm
Hashing
Binary Search Algorithm:
Binary search is the simple and basic algorithm in the data structure. Binary search
is used to find data quickly and easily. In Binary search, data should be stored in a
list and arranged in a sequential order. For a random number, we can’t apply binary
search algorithm. In binary search, we have to find the middle of the list. Then
compare that middle value with targeted value if middle value is less than targeted
value then consider remaining half and again find the middle of the list continue
this process until we get our targeted value.
Types of Algorithm
Read the targeted value from the user
Example: Find no. 23
2 5 8 12 16 23 38 56 72 91
Step 2: Find the middle of the list
2 5 8 12 16 23 38 56 72 91
Step 3: Compare the middle value with the targeted value of the list
Here
2z23 > 5
16 so we
8 can say
1223 is16
not in 23
1st half38
part 56 72 91
(2nd half)
Types of Algorithm
Step 4: If the middle-value match with targeted value then we say
targeted no. find and can close the procedure.
Step 5: If a middle value doesn’t match with targeted value then
compare a middle value with 2nd half, is smaller or greater than
targeted value.
Now middle value is 56, so compare 23 with 56
23 < 56
2 5 8 12 16 23 38 56 72 91
Step 6: 23 > 56 so number is on left side and we compare between 23
& 38
2 5 8 12 16 23 38 56 72 91
Types of Algorithm
Step 7: Repeat the same process until we find the search element in the list
We found 23 at 5th position
Step 8: If that element also doesn’t match with the search element, then
display “Element not found in the list!!!” and terminate the function.
Sorting Algorithms
Sorting is the process of arranging the data in a sorted order. The sorted
data in a list in ascending or descending order. There are many things in our
day-to-day life where we use sorting and searching, searching is very
simple if we have sorted data, for example, if we want to find a phone
number from phone directory, to find roll number of student etc. for that we
use sorting.
Types of Algorithm
There are no. of sorting algorithm –
Bubble Sort
Insertion Sort
Selection Sort
Bubble Sort :
Bubble sort is the simple algorithm used to sort a large amount of
data. It is a comparison based algorithm compare each pair of a
number until the entire array is sorted.
Example:
Step 1: Take unsorted array
Types of Algorithm
4 1 5 9 8
Step 2: Compare first two elements, and sort them in ascending
order.
In this case, value 4 is greater than 1, so swap
them
4 to sort.1 5 9 8
Step 3: Compare next two elements 4 and 5.
4 is smaller than 5 so they are already sorted.
1 4 5 9 8
Types of Algorithm
Step 4: Compare next two elements 5 and 9.
Here also 5 is smaller than 9, means they are also in sorted order.
1 4 5 9 8
Step 5: Compare next two elements 9 and 8.
1 4 5 9 8
Here
1 9 is greater than
4 8 so we swipe
5 these two 8
elements to sort
9
In the end, we will get a sorted array.
Types of Algorithm
2. Insertion Sort:
Insertion sort is also a comparison based algorithm but in that we
maintain sub-list. This algorithm is not suitable for a large amount of
data sorting. Let us see an example.
Step 1: Take unsorted array
25 14 31 27
Step 2: Compare first two values 25 and 14.
Here 14 is smaller than 25, so swap these two elements. Now element 14
is in sub-list
14 25 31 27
Types of Algorithm
Step 3: Check next two elements 25 and 31.
In this case 25 and 31 are already in ascending order, so no need to swap.
Step 4: Now we have 14 and 25 in sub-list.
These values are in ascending order, so no need to swap.
Step 5: Now move ahead and check next element 31 and 27
14 25 31 27
Here 31 and 27 are not in correct order so swap these elements
14 25 27 31
Step 6: Now we have 25 and 27 are in sub-list so compare them.
Types of Algorithm
25 and 27 also in ascending order so we close the process and we get below
sorted list.
3. Selection Sort:
Selection sort is the simplest sorting algorithm. Firstly it scans the array and finds
the smallest element from an array then this smallest element replace with first
position element. Continue this procedure until we find the sorted element.
Let’s see step by step procedure –
Step 1: Take unsorted array
25 14 31 27
Scan the whole array to find the smallest number. After scanning we got 14 is the
lowest number.
Types of Algorithm
Step 2: Replace the lowest number with the first element and we will
get
14 25 31 27
Step 3: Now find second lowest number and replace with the second
position. Second lowest no. is 25 and is already at correct position.
Step 4: Continue this procedure until we get a sorted array.
14 25 27 31
In the end, we will get a sorted array.
Data Structure
Data Structure is a way of collecting and organizing data in such a way that we can
perform operations on these data in an effective way.
_ anything that can store data.
_ Integer, Float, Boolean, Char etc, all are data structures(known as Primitive
Data Structures).
_some complex Data Structures used to store large and connected data(known as
Abstract Data Structure).
Some example of Abstract Data Structure are :
Linked List
Tree
Graph
Stack, Queue etc.
All these data structures allow us to perform different operations on data.
Data structure
Any question….?
Thank you