S1 To S9 (Upto Mathematical Functions)

Download as pptx, pdf, or txt
Download as pptx, pdf, or txt
You are on page 1of 122

18CSC201J

DATA STRUCTURES AND


ALGORITHMS
Course Learning Objective
• CLO-1 : Identify linear and non-linear data structures. Create
algorithms for searching and sorting
• CLO-2 : Create the different types of linked lists and evaluate its
• CLO-3 : Construct stack and queue data structures and evaluate its
operations
• CLO-4 : Create tree data structures and evaluate its types and
operations
• CLO-5 : Create graph data structure, evaluate its operations,
implement algorithms to identify shortest path
HIGHLIGHT 1

What is a Data Structure?


 Simply put, a data structure is a container that stores data in a specific layout. This “layout”
allows a data structure to be efficient in some operations and inefficient in others.

 Your goal is to understand data structures so that you can pick the data structure that’s most
optimal for the problem at hand.

A data structure is a way of organizing data in some fashion so that later on, it
can be accessed, queried, or even updated easily and quickly.

 Data structures are essential components in creating fast and powerful algorithms. They help to
manage and organize data.

15/02/2024 3
HIGHLIGHT 2

Why do we need Data Structures?

 As data structures are used to store data in an organized form, and since data is the most crucial entity in
computer science, the true worth of data structures is clear.

 No matter what problem are you solving, in one way or another you have to deal with data — whether it’s
an employee’s salary, stock prices, a grocery list, or even a simple telephone directory.

 Based on different scenarios, data needs to be stored in a specific format. We have a handful of data
structures that cover our need to store data in different formats.

A famous quote:
Program = Algorithms + Data Structures.

15/02/2024 4
HIGHLIGHT 3

To Know Commonly used Data Structures


Let’s first list the most commonly used data structures, and then we’ll cover them one by one:
1. Arrays
2. Stacks
3. Queues
4. Linked Lists
5. Trees
6. Graphs
7. Tries
8. Hash Tables

15/02/2024 5
HIGHLIGHT 4

Why Data Structures and Algorithms Are Important to Learn?

 Do you have questions that why should I study all the above-complicated stuff if it has absolutely no
use in real life??

 Why do companies ask questions related to data structures and algorithms if it’s not useful in a daily
job??

A lot of beginners and experienced programmers avoid learning Data


Structures and Algorithms because it’s complicated and they think that there is no use of all the
above stuff in real life.
What are Algorithms?

 Informally, an algorithm is nothing but a mention of steps to solve a problem. They are essentially a
solution.

15/02/2024 6
HIGHLIGHT 5

Reasons to Learn Data Structure and Algorithms

If you need to search your roll number in 20000 pages of PDF document (roll numbers are arranged in increasing order) how
would you do that?
• If you will try to search it randomly or in a sequential manner it will take too much time. You might get frustrated after some
time.
• You can try another solution which is given below…
 Go to page no. 10000
 If your roll no. is not there, but all other roll no. in that page are lesser than your than
 Go to page no. 15000
 Still if your roll no. is not there. but this time all other roll no. is greater than your.
 Go to page no. 12500

Continue the same process and within 30-40 seconds you will find your roll number.

Congratulations… you just have used the Binary Search algorithm unintentionally..

From the above example, we can straightforward give two reasons to Learn Data Structure and Algorithms…
 If you want to crack the interviews and get into the product based companies
 If you love to solve real-world complex problems.

15/02/2024 7
HIGHLIGHT 6

To Crack the Interviews of the Top Product Based Companies

 Data structures and algorithms play a major role in implementing software and in the hiring process as well.

 A lot of students and professionals have this question that why these companies’ interviews are focused on DSA
instead of language/frameworks/tools specific questions?

 When you ask someone to make a decision for something the good one will be able to tell you “ I choose to do X
because it’s better than A, B in these ways. I could have gone with C, but I felt this was a better choice because of
this“.

 In our daily life, we always go with that person who can complete the task in a short amount of time with efficiency
and using fewer resources.

 The same things happen with these companies. The problem faced by these companies is much harder and on a much
larger scale.

 Software developers also have to make the right decisions when it comes to solving the problems of these
companies.

15/02/2024 8
HIGHLIGHT 7

To Address Real World Problems


 Knowledge of data structures like Hash Tables, Trees, Graphs, and various algorithms goes a long way
in solving these problems efficiently and the interviewers are more interested in seeing how candidates
use these tools to solve a problem.

 Just like a car mechanic needs the right tool to fix a car and make it run properly, a programmer needs
the right tool (algorithm and data structure) to make the software run properly.

 So the interviewer wants to find a candidate who can apply the right set of tools to solve the given
problem. .

 If you know the characteristics of one data structure in contrast to another you will be able to make the
right decision in choosing the right data structure to solve a problem.

Data structure and algorithms help in understanding the nature of the problem at a deeper
level and thereby a better understanding of the world.

15/02/2024 9
HIGHLIGHT 8

Use of Data Structures and Algorithms to Make Your Code Scalable

 Time is precious.

 More on Scalability
Scalability is scale plus ability, which means the quality of an algorithm/system to handle the
problem of larger size.

 Memory is expensive
Memory is not always available in abundance. While dealing with code/system which
requires you to store or produce a lot of data, it is critical for your algorithm to save the usage of
memory wherever possible.

15/02/2024 10
HIGHLIGHT 9
Solutions through Data Structures in real life

1. You have to store social network “feeds”. You do not know the size, and things may need to be dynamically added. -
linked list or Hash table
2. You need to store undo/redo operations in a word processor. – stack (use 2 stack for including redo operation)
3. You need to evaluate an expression (i.e., parse). – stack or tree
4. You need to store the friendship information on a social networking site. I.e., who is friends with who – graph
5. You need to store an image (1000 by 1000 pixels) as a bitmap. – ArrayList(java) or 2D array
6. To implement printer spooler so that jobs can be printed in the order of their arrival. – queue
7. To implement back functionality in the internet browser. – stack
8. To store the possible moves in a chess game. – tree
9. To store a set of fixed keywords which are referenced very frequently. –dynamic programming or hash table
10. To store the customer order information in a drive-in burger place. (Customers keep on coming and they have to get
their correct food at the payment/food collection window.) – queue / min Priority Queue(if the order is simple and takes
less time)
11.To store the genealogy information of biological species. – Tree
15/02/2024 11
UNIT I
CLO-1 : Identify linear and non-linear data structures. Create algorithms for searching and
sorting
Topics to be covered

S1 : Introduction – Basic Terminology - Data Structures


S2 : Data Structure Operations - ADT
S3 : Algorithms – Searching Techniques – Complexity – Time, Space Matrix
S4 : Algorithms – Sorting - Complexity – Time, Space Matrix
S5 : Mathematical notations – Asymptotic notations – Big O, Omega
S6 : Asymptotic notations – Theta – Mathematical functions
S7 : Data Structures and its Types - Linear and Non Linear Data Structures
S8 : 1D, 2D Array Initialization using Pointers - 1D, 2D Array Accessing
using Pointers
S9 : Declaring Structure and accessing – Declaring Arrays of Structures and
accessing
INTRODUCTION
BASIC TERMINOLOGY
SLO-1 : Identify the basic terminology need for problem solving and types of data structures
used in problem solving
Introduction
• Data Structure can be defined as the group of data elements which
provides an efficient way of storing and organizing data in the computer
so that it can be used efficiently(accessed easily and quickly).
• Some examples of Data Structures are arrays, Linked List, Stack, Queue,
etc.
• Data Structures are widely used in almost every aspect of Computer
Science i.e. Operating System, Compiler Design, Artificial intelligence,
Graphics and many more.
Basic Terminology
• Data are values or sets of values
• A data item refers to a single unit of values. Data items are divided into
subitems are called group items.
o For example, an employee’s name
o three subitems
o first name,
o middle name and
o last name
o but the social security number would treated as a single name.
• Collections of data are organized into a hierarchy of fields, records and
files.
Basic Terminology (Cont..)
• Record can be defined as the collection of various data items.
o For example, if we talk about the student entity, then its name, address,
course and marks can be grouped together to form the record for the
student.
• Record is classified according to length. A file can have fixed length
records or variable length records.
• In fixed length records, all the records contain the same data items with
the same amount of space assigned to each data items.
• In variable length records, file records may contain different lengths.
Variable length records have a minimum and a maximum length.
o For example, student records have variable length, since different
students take different numbers of courses
Basic Terminology (Cont..)
• A File is a collection of various records of one type of entity.
o For example, if there are 60 employees in the company, then there will
be 60 records in the related file where each record contains the data
about each employee.
• An entity represents the class of certain objects. It contains various
attributes. Each attribute represents the particular property of that entity.
o For example, consider an employee of an organization:
Attributes: Name Age Sex Social Security Number
Values: JOHN 34 M 134-24-5533
• Field is a single elementary unit of information representing the attribute
of an entity.
Basic Terminology – Example
• A professor keeps a class list containing the following data for each student:
Name, Major, Student Number, Test Scores, Final Grades
a) State the entities, attributes and entity set of the list.
b) Describe the field values, records and file.
c) Which attribute can serve as primary keys for the list?

a) Each student is an entity, and the collection of students is the entity set. The properties, name,
major, and so on. of the students are the attributes.
b) The field values are the values assigned to the attributes, i. e., the actual names, test scores,
and so on. The field values for each student constitute a record, and the collection of all the
student records is the file.
c) Either Name or Student Number can serve as a primary key, since each uniquely determines
the student’s record. Normally the professor uses Name as the primary key, but the registrar
may use students Number.
DATA STUCTURES
Data Structures
• Data Structure can be defined as the group of data elements which
provides an efficient way of storing and organizing data in the computer
so that it can be used efficiently.
• Data Structures are the main part of many computer science algorithms as
they enable the programmers to handle the data in an efficient way.
• It plays a vital role in enhancing the performance of a software or a
program as the main function of the software is to store and retrieve the
user's data as fast as possible.
Classification of Data Structures
Primitive & Non-Primitive of Data Structures
• Primitive data structures are the fundamental data types which are
supported by a programming language.
• Some basic data types are integer, real(float), character, and Boolean.
• Non-primitive data structures are data structures which are created using
primitive data structures.
• Examples of such data structures include linked lists, stacks, trees, and
graphs.
• Non-primitive data structures can further be classified into two categories:
linear and non-linear data structures.
Linear Data Structures
• If the elements of a data structure are stored in a linear or sequential
order, then it is a linear data structure.
• Examples include arrays, linked lists, stacks, and queues.
• Linear data structures can be represented in memory in two different
ways.
• One way is to have a linear relationship between elements by means of
sequential memory locations.
• The other way is to have a linear relationship between elements by means
of links.
Non Linear Data Structures
• If the elements of a data structure are not stored in a sequential order,
then it is a non-linear data structure.
• The relationship of adjacency is not maintained between elements of a
non-linear data structure.
• Examples include trees and graphs.
Review Questions
• A hospital maintains a patient file in which each record contains the following data:
Name, Admission date, Social security number, Room, Bed number, Doctor
a) Which items can serve as primary keys?
b) Which pair of items can serve as a primary key?
c) Which items can be group items?
• Which of the following data items may lead to variable length records when included as
items in the record:
(a) age, (b) sex, (c) name of spouse, (d) names of children, (e) education,
(f) previous employers
DATA STUCTURE
OPERATIONS
Data Structure Operations

• The data in the data structures are processed by certain operations.


o Traversing
o Searching
o Inserting
o Updating
o Deleting
o Sorting
o Merging
Data Structure Operations (Cont..)
• Traversing - Visiting each record so that items in the records can be
accessed.
• Searching - Finding the location of the record with a given key or value or
finding all records which satisfy given conditions.
• Inserting - Adding a new record to the data structure.
• Updating – Change the content of some elements of the record.
• Deleting - Removing records from the data structure.
• Sorting - Arranging records in some logical or numerical order.
o (Eg: Alphabetic order)
• Merging - Combing records from two different sorted files into a single
file.
Example
• An organization contains a membership file in which each record contains
the following data for a given member:
Name, Address, Telephone Number, Age, Sex
a. Suppose the organization wants to announce a meeting through a
mailing. Then one would traverse the file to obtain Name and
Address of each member.
b. Suppose one wants to find the names of all members living in a
particular area. Again traverse and search the file to obtain the data.
c. Suppose one wants to obtain Address of a specific Person. Then one
would search the file for the record containing Name.
d. Suppose a member resigns. Then one would delete his or her record
from the file.
Example
e. Suppose a new person joins the organization. Then one would insert
a record into the file
f. Suppose a member has shifted to a new residence his/her address
and telephone number need to be changed. Given the name of the
member, one would first need to search for the record in the file.
Then perform the update operation, i.e. change some items in the
record with the new data.
g. Suppose one wants to find the number of members whose age is 65 or
above. Again one would traverse the file, counting such members.
ABSTRACT DATA TYPE
Abstract Data Types
• An Abstract Data type (ADT) is a type for objects whose behavior is
defined by a set of value and a set of operations.
• ADT refers to a set of data values and associated operations that are
specified accurately, independent of any particular implementation.
• The ADT consists of a set of definitions that allow us to use the functions
while hiding the implementation.
• Abstract in the context of data structures means everything except the
detailed specifications or implementation.
• Data type of a variable is the set of values that the variable can take.

ADT = Type + Function Names + Behaviour of each


function
• Examples: Stacks, Queues, Linked List
ADT Operations
• While modeling the problems the necessary details are separated out from
the unnecessary details. This process of modeling the problem is called
abstraction.
• The model defines an abstract view to the problem. It focuses only on
problem related stuff and that you try to define properties of the problem.
• These properties include
o The data which are affected.
o The operations which are identified.
ADT Operations ( Cont..)
• Abstract data type operations are
o Create - Create the data structure.
o Display - Displaying all the elements stored in the data structure.
o Insert - Elements can be inserted at any desired position.
o Delete - Desired element can be deleted from the data structure.
o Modify - Any desired element can be deleted/modified from the data
structure.
Abstract Data Types Model
• The ADT model has two different parts
functions (public and private) and data
structures.
• Both are contained within the ADT model
itself, and do not come within the scope of
the application program.
• Data structures are available to all of the
ADT’s functions as required, and a function
may call any other function to accomplish
its task.
• Data structures and functions are within the
scope of each other.
Abstract Data Types Model (Cont..)
• Data are entered, accessed, modified and
deleted through the external application
programming interface.
• For each ADT operation, there is an
algorithm that performs its specific task.
• The operation name and parameters are
available to the application, and they
provide only an interface to the
application.
• When a list is controlled entirely by the
program, it is implemented using simple
structure.
Review Questions

• ______ are used to manipulate the data contained in various data


structures.
• In ______, the elements of a data structure are stored sequentially.
• ______ of a variable specifies the set of values that the variable can take.
• Abstract means ______.
• If the elements of a data structure are stored sequentially, then it is a
______.
ALGORITHMS
SEARCHING TECHIQUES
Algorithms
• An algorithm is a well defined list of steps for solving a particular
problem.
• The time and space are two major measures of the efficiency of an
algorithm.
• The complexity of an algorithm is the function which gives the running
time and / or space in terms of input size.
Searching Algorithms
• Searching Algorithms are designed to check for an element or retrieve an
element from any data structure where it is stored.
• Based on the type of search operation, these algorithms are generally
classified into two categories:
• Linear Search
• Binary Search
Linear Search
• Linear search is a very basic and simple search algorithm.
• In Linear search, we search an element or value in a given array by
traversing the array from the starting, till the desired element or value is
found or we can establish that the element is not present.
• It compares the element to be searched with all the elements present in the
array and when the element is matched successfully, it returns the index of
the element in the array, else it return -1.
• Linear search is applied on unsorted or unordered lists, when there are
fewer elements in a list.
Linear Search - Example
• Search each record of the file, one at a time, until finding the given value.
Algorithm for Linear Search
• In Steps 1 and 2 of the algorithm, we initialize
the value of POS and I.
• In Step 3, a while loop is executed that would
be executed till I is less than N.
• In Step 4, a check is made to see if a match is
found between the current array element and
VAL.
• If a match is found, then the position of the
array element is printed, else the value of I is
incremented to match the next element with
VAL.
• If all the array elements have been compared
with VAL and no match is found, then it
means that VAL is not present in the array.
Program for Linear Search
Linear Search - Advantages
• When a key element matches the first element in the array, then linear
search algorithm is best case because executing time of linear search
algorithm is O(n), where n is the number of elements in an array.
• The list doesn’t have to sort. Contrary to a binary search, linear searching
does not demand a structured list.
• Not influenced by the order of insertions and deletions. Since the linear
search doesn’t call for the list to be sorted, added elements can be inserted
and deleted.
Linear Search - Disadvantages
• The drawback of a linear search is the fact that it is time consuming if the
size of data is huge.
• Every time a vital element matches the last element from the array or an
essential element does not match any element Linear search algorithm is
the worst case.
Binary Search
• Binary Search is used with sorted array or list. In binary search, we follow
the following steps:
1) We start by comparing the element to be searched with the element in
the middle of the list/array.
2) If we get a match, we return the index of the middle element and
terminate the process
3) If the element/number to be searched is greater than the middle
element, we pick the elements on the left/right side of the middle
element, and move to step 1.
4) If the element/number to be searched is lesser in value than the
middle number, then we pick the elements on the right/left side of the
middle element, and move to step 1.
Binary Search - Example
• Binary Search is useful when there are large number of elements in an
array and they are sorted.
Algorithm for Binary Search
• In Step 1, we initialize the value of variables, BEG,
END, and POS.
• In Step 2, a while loop is executed until BEG is
less than or equal to END.
• In Step 3, the value of MID is calculated.
• In Step 4, we check if the array value at MID is
equal to VAL. If a match is found, then the value
of POS is printed and the algorithm exits. If a
match is not found, and if the value of A[MID] is
greater than VAL, the value of END is modified,
otherwise if A[MID] is greater than VAL, then the
value of BEG is altered.
• In Step 5, if the value of POS = –1, then VAL is not
present in the array and an appropriate message is
printed on the screen before the algorithm exits.
Program for Binary Search
Binary Search (Cont..)
Advantages Disadvantages
• It eliminates half of the list from • It employs recursive approach
further searching by using the which requires more stack space.
result of each comparison. • Programming binary search
• It indicates whether the element algorithm is error prone and
being searched is before or after difficult.
the current position in the list. • The interaction of binary search
• This information is used to narrow with memory hierarchy i.e.
the search. caching is poor.
• For large lists of data, it works
significantly better than linear
search.
Difference between Linear & Binary Search
Linear Search Binary Search
• Linear Search necessitates the • Binary Search necessitates the
input information to be not sorted input information to be sorted.
• Linear Search needs equality • Binary Search necessitates an
comparisons. ordering contrast.
• Linear search has complexity • Binary Search has complexity
C(n)= n/2. C(n)= log 2 n.
• Linear Search needs sequential • Binary Search requires random
access. access to this information.
COMPLEXITY
TIME, SPACE MATRIX
Linear Search – Time & Space Matrix
• Time Complexity
o We need to go from the first element to the last so, in the worst case we
have to iterate through ‘n’ elements, n being the size of a given array.

Time Complexity is O(n)


• Space Complexity
o We don't need any extra space to store anything.
o We just compare the given value with the elements in an array one by
one.

Space Complexity is O(1)


Binary Search – Time & Space Matrix
• Time Complexity
o We start from the middle of the array and keep dividing the search area
by half.
o In other words, search interval decreases in the power of 2 (2048, 1024,
512, ..).

Time Complexity is O(Log n)

• Space Complexity
o We just need to store three values: `lower_bound`, `upper_bound`, and
`middle_position`.

Space Complexity is O(1)


Review Questions
• The worst case complexity is ______ when compared with the average
case complexity of a binary search algorithm.
(a) Equal (b) Greater (c) Less (d) None of these
• The complexity of binary search algorithm is
(a) O(n) (b) O(n2) (c) O(n log n) (d) O(log n)
• Which of the following cases occurs when searching an array using linear
search the value to be searched is equal to the first element of the array?
(a) Worst case (b) Average case (c) Best case (d) Amortized case
• Performance of the linear search algorithm can be improved by using a
______.
• The complexity of linear search algorithm is ______.
ALGORITHM
SORTING
SORTING
• Sorting is a technique to rearrange the elements of a list in ascending or
descending order, which can be numerical, lexicographical, or any user-
defined order.
• Sorting is a process through which the data is arranged in ascending or
descending order.
Sorting can be classified in two types;
1. Internal Sorts
2. External Sorts
SORTING - INTERNAL SORTS
• Internal Sorts:- This method uses only the primary memory during sorting
process. All data items are held in main memory and no secondary memory
is required for this sorting process.
• If all the data that is to be sorted can be accommodated at a time in memory
is called internal sorting. There is a limitation for internal sorts; they can only
process relatively small lists due to memory constraints. There are 3 types of
internal sorts based on the type of process used while sorting.
(i) SELECTION :- Ex:- Selection sort algorithm, Heap Sort algorithm
(ii) INSERTION :- Ex:- Insertion sort algorithm, Shell Sort algorithm
(iii) EXCHANGE :- Ex:- Bubble Sort Algorithm, Quick sort algorithm
SORTING – EXTERNAL SORTS
• External Sorts:- Sorting large amount of data requires external or secondary
memory. This process uses external memory such as HDD, to store the data
which is not fit into the main memory. So, primary memory holds the
currently being sorted data only.
• All external sorts are based on process of merging. Different parts of data are
sorted separately and merged together. Ex:- Merge Sort
INSERTION SORT
• Insertion Sort Algorithm sorts array by shifting elements one by one and inserting
the right element at the right position

• It works similar to the way you sort playing cards in your hands
INSERTION SORT
• Insertion sorts works by taking
elements from the list one by one Pseudo code
and inserting them in their current
position into a new sorted list. INSERTION-SORT(A)
• Insertion sort consists of N - 1 for i = 1 to n
passes, where N is the number of key ← A [i]
elements to be sorted. j←i–1
• The ith pass of insertion sort will while j > = 0 and A[j] > key
insert the ith element A[i] into its A[j+1] ← A[j]
rightful place among A[1], A[2] to j←j–1
End while
A[i - 1]. After doing this insertion
A[j+1] ← key
the records occupying A[1]....A[i] End for
are in sorted order.
Working of insertion sort – Ascending order
• We start by considering the second element of the given array, i.e. element at
index 1, as the key.
• We compare the key element with the element(s) before it, i.e., element at index 0:
– If the key element i.e index 1 is less than the first element, we insert
the key element before the first element.(swap)
– If the key element is greater than the first element, then we insert it remains at
its position
– Then, we make the third element of the array as key and will compare it with
elements to it's left and insert it at the right position.
• And we go on repeating this, until the array is sorted
.
Example
Let us now understand working
with the following example:
Consider the following array: 25, 17,
31, 13, 2 where N=5

First Iteration: Compare 17 with 25.


The comparison shows 17< 25.
Hence swap 17 and 25.
The array now looks like:
17, 25, 31, 13, 2
EXAMPLE (Cont..)
Second Iteration:.
• Now hold on to the third element
(31) and compare with the ones
preceding it.
• Since 31> 25, no swapping takes
place.
• Also, 31> 17, no swapping takes
place and 31 remains at its position.
• The array after the Second iteration
looks like:
17, 25, 31, 13, 2
EXAMPLE (Cont..)
Third Iteration: Start the following Iteration with
the fourth element (13), and compare it with its
preceding elements.
• Since 13< 31, we swap the two.
• Array now becomes: 17, 25, 13, 31, 2.
• But there still exist elements that we haven’t yet
compared with 13. Now the comparison takes
place between 25 and 13. Since, 13 < 25, we swap
the two.
• The array becomes 17, 13, 25, 31, 2.
• The last comparison for the iteration is now
between 17 and 13. Since 13 < 17, we swap the two.
• The array now becomes 13, 17, 25, 31, 2.
EXAMPLE (Cont..)
Fourth Iteration: The last 13, 17, 2, 25, 31.
iteration calls for the • Compare 2 with 17 and 13.
comparison of the last • Since, 2<17. Swap 2 and 17.
element (2), with all the
• Array now becomes:
preceding elements and
make the appropriate 13, 2, 17, 25, 31.
swapping between • The last comparison for the
elements. Iteration is to compare 2
with 13.
• Since, 2< 31. Swap 2 and
31. • Since 2< 13. Swap 2 and 13.
Array now becomes: 13, 17, • The array now becomes:
25, 2, 31. 2, 13, 17, 25, 31.
Insertion sort consists of N - 1 passes
• Compare 2 with 25, 17, • This is the final array after Where N=5 So 5-1=4
13. all the corresponding Number of pass=4(4th iteration all the
iterations and swapping of elements are sorted)
• Since, 2< 25. Swap 25 and elements.
2.
void InsertionSort(int arr[], int n)
void insertion(int a[], int n)
void insertion(int arr[], int n)
{
{
int i,j,tmp; int i,j,key;
for(i=1; i<n; i++) for(i=1; i<n; i++)
{ {
for(j=i-1; j>=0; j--)
key=a[i];
{
if(arr[j]>arr[j+1]) for(j=i-1; a[j] > key && j>=0; j--)
{ {
tmp=arr[j]; a[j+1]=a[j];
arr[j]=arr[j+1];
}
arr[j+1]=tmp;
}
a[j+1]=key;
} }
} }
}
Insertion Sort
#include<stdio.h> void insertion(int a[], int n)
#include<conio.h>
void insertion(int [], int ); {
int main() int i,j,key;
{ for(i=1; i<n; i++)
int a[30], i, size;
{
scanf("%d",&size);
for(i=0; i<size; i++) key=a[i];
{ for(j=i-1; a[j] > key && j>=0; j--)
scanf("%d",&a[i]); {
}
InsertionSort(a,size); a[j+1]=a[j];
for(i=0; i<size; i++) }
printf(" %d",a[i]); a[j+1]=key;
return 0;
}
}
}
Advantages & Disadvantages
Advantages
• The main advantage of the insertion sort is its simplicity
• It also exhibits a good performance when dealing with a small list.
• The insertion sort is an in-place sorting algorithm so the space requirement is
minimal
Disadvantages
• The disadvantage of the insertion sort is that it does not perform when
compared to few other, sorting algorithms
• With n-squared steps required for every n element to be sorted, the insertion
sort does not deal well with a huge list.
• The insertion sort is particularly useful only when sorting a list of few items
BUBBLE SORT
• The movement of air bubbles in the water that rise up to the surface, each element of the array move to
the end in each iteration. Therefore, it is called a bubble sort.
• Bubble sort is a simple sorting algorithm. This sorting algorithm is comparison-based algorithm in
which each pair of adjacent elements is compared and the elements are swapped if they are not in
order
Steps to implement bubble sort:
Assume that there are n elements in the list
1. In first cycle,
1. Start by comparing 1st and 2nd element
and swap if they are not in order.
2. After that do the same for 2nd and 3rd
element. Repeat till n-1th and nth
elements are compared.
3. At the end of cycle one element
(max/min) will be placed as the last
element in of list.
2. The process specified in step 1 is repeated for
another n-2 times, where in each time the
number of comparisons reduce by 1 as the
list of sorted elements grow.
Working of Bubble Sort – Ascending order
Suppose we are trying to sort the elements
in ascending order.
Let us now understand working with the following
example:
Consider the following array: -2,45,0,11,-9 where
N=5
First Iteration (Compare and Swap)
• Starting from the first index, compare the first and
the second elements.
• If the first element is greater than the second
element, they are swapped.
• Now, compare the second and the third elements.
Swap them if they are not in order.
• The above process goes on until the last element
Working of Bubble Sort (Cont..)

Second Iteration
• The same process goes on for the
remaining iterations.
• After each iteration, the largest
element among the unsorted
elements is placed at the end.

Put the largest element at the end


Working of Bubble Sort (Cont..)
Third Iteration Fourth Iteration
In each iteration, the comparison takes place The array is sorted when all the unsorted elements
up to the last unsorted element. are placed at their correct positions.

The array is sorted if all elements are kept in the right order.
Compare the adjacent elements Now all the elements are sorted
void BubbleSort(int a[],int n)
void bubblesort(int a[],int size)
{
int temp,i,j;
for(i=0;i<n;i++)
{
for(j=0;j<n-1;j++)
{
if(a[j]>a[j+1])
{
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}
}
}
Program: BubbleSort
#include<stdio.h> void bubblesort(int a[],int size)
#include<stdlib.h>
void bubblesort(int a[],int size); {
void main() int temp,i,j;
{
int a[50],n,i;
for(i=0;i<size;i++)
printf("\n Enter the size of the array"); {
scanf("%d",&n); for(j=0;j<size-1;j++)
if(n>50)
{ {
printf("\n error"); if(a[j]>a[j+1])
exit(0); {
}
temp=a[j];
printf("\n Enter the array elements: \n"); a[j]=a[j+1];
for(i=0;i<n;i++) a[j+1]=temp;
scanf("%d",&a[i]); }
bubblesort(a,n); }
printf("\n The sorted array is\n");
for(i=0;i<n;i++) }
printf("%d\t",a[i]); }
}
ADVANTAGES AND DISADVANTAGES
Advantage:
• It is the simplest sorting approach.
• The primary advantage of the bubble sort is that it is popular and easy to implement.
• In the bubble sort, elements are swapped in place without using additional temporary storage.
Stable sort: does not change the relative order of elements with equal keys.
• The space requirement is at a minimum
Disadvantage:
• Bubble sort is comparatively slower algorithm.
• The main disadvantage of the bubble sort is the fact that it does not deal well with a list
containing a huge number of items.
• The bubble sort requires n-squared processing steps for every n number of elements to be
sorted.
COMPLEXITY – TIME ,
SPACE TRADE OFF
SPACE COMPLEXITY
• Space complexity is the total amount of memory space used by an
algorithm/program including the space of input values for execution. So
to find space-complexity, it is enough to calculate the space occupied by
the variables used in an algorithm/program.
• Space complexity S(P) of any algorithm P is,
• S(P) = C + SP(I)
• Where C is the fixed part and S(I) is the variable part of the algorithm
which depends on instance characteristic I.
Example: Here we have three variables A, B & C and one
 Algorithm: SUM(A, B) constant. Hence S(P) = 1+3.
 Step 1 - START Space requirement depends on data types of given
 Step 2 - C ← A + B + 10 variables & constants. The number will be multiplied
accordingly.
 Step 3 – Stop
EXAMPLE

#include<stdio.h>
int main()
{
int a = 5, b = 5, c;
c = a + b;
printf("%d", c);
}
Space Complexity: size(a)+size(b)+size(c)
=>let sizeof(int)=2 bytes=>2+2+2=6 bytes
=>O(1) or constant
Example
#include <stdio.h> Space Complexity:
int main()
• The array consists of n integer
{
elements.
int n, i, sum = 0;
scanf("%d", &n); • So, the space occupied by the array
int arr[n]; is 4 * n. Also we have integer
for(i = 0; i < n; i++) variables such as n, i and sum.
{ Assuming 4 bytes for each variable,
scanf("%d", &arr[i]); sum = sum + arr[i]; the total space occupied by the
} program is 4n + 12 bytes.
printf("%d", sum); • Since the highest order of n in the
} equation 4n + 12 is n, so the space
complexity is O(n) or linear.
Time Complexity
• Time Complexity of an algorithm represents the amount of time
required by the algorithm to run to completion.
• Time requirements can be defined as a numerical function T(n), where
T(n) can be measured as the number of steps, provided each step
consumes constant time.
• Eg. Addition of two n-bit integers takes n steps.
• Total computational time is T(n) = c*n,
• where c is the time taken for addition of two bits.
• Here, we observe that T(n) grows linearly as input size increases.
Time Complexity (Cont..)
Two methods to find the time complexity for an algorithm
1. Count variable method

2. Table method

9/11/21 85
Count Variable Method

86
Example 1

9/11/21 87
Example 2

int sum(int A[], int n)

{
int sum = 0, i;
for(i = 0; i < n; i++)
sum = sum + A[i];
return sum;
}
Example 3

Cost Times
i = 1; c1 1
sum = 0; c2 1
whil e (i <= n) { c3 n+1
i = i + 1; c4 n
sum = su m + i; c5 n

}
3n+3
Total Cost = c1 + c2 + (n+1)*c3 + n*c4 + n*c5
The time required for this algorithm is proportional to n
Example 4

Total Cost = c1 + c2 + (n+1)*c3 + n*c4 +


n*(n+1)*c5+n*n*c6+n*n*c7+n*c8
The time required for this algorithm is proportional
to n2
INSERTION SORT -TIME COMPLEXITY
Time Complexity of Bubble Sort
TIME , SPACE TRADE OFF
• a space-time or time-memory tradeoff is a way of solving a problem or calculation in
1. less time by using more storage space (or memory), or
2. by solving a problem in very little space by spending a long time

• The best Algorithm is that which helps to solve a problem that requires less space in memory
and also takes less time to generate the output.
• But in general, it is not always possible to achieve both of these conditions at the same time.
• One way is to store the result and use it in calculation.
• Another way is to calculate the answers without writing down anything, which uses very little
space, but might take a long time. more time-efficient algorithms you have, that would be less
space-efficient.
Types of Tradeoff
• Compressed / Uncompressed data
• Re-rendering / Stored images
• Smaller code / Loop Unrolling
• Lookup Table / Recalculation
Review Questions
Sort the following numbers using bubble sort and Insertion sort
• 35,12,14,9,15,45,32,95,40,5
• 3, 1, 4, 1, 5, 9, 2, 6, 5
• 17 14 34 26 38 7 28 32
• 35,12,14,9,15,45,32,95,40,5
Review questions
1. Calculate the time complexity for the below algorithms using table
method

97
2.

3.

9/11/21 98
MATHEMATICAL
FUNCTIONS AND
NOTATIONS
MATHEMATICAL FUNCTIONS
AND NOTATIONS
• Analysis of the algorithm can be represented using mathematical
functions and notations.
MATHEMATICAL FUNCTIONS
1. Floor
2. Ceil
3. Modulus
4. Integer
5. Absolute
6. Factorial
7. Permutation
8. Exponents
9. Logarithm
10. Summation
Mathematical Functions and Notations
Mathematical Functions and Notations
Algorithm Analysis
• The time required by an algorithm falls under three types −
• Best Case − Minimum time required for program execution.
• Searching the key at Last Index
• Average Case − Average time required for program execution.
• Avg= Sum of all possible case time/no.of cases
• Worst Case − Maximum time required for program execution.
• Searching the key at Last Index

104
Asymptotic Analysis
• Asymptotic analysis of an algorithm refers to defining the mathematical
foundation/framing of its run-time performance.
• Asymptotic analysis is input bound.
• Specify the behavior of the algorithm when the input size increases
• Theory of approximation.
• Asymptote of a curve is a line that closely approximates a curve but does
not touch the curve at any point of time.

105
ASYMPTOTIC NOTATIONS
BIG O, OMEGA
Asymptotic notations
• Asymptotic notations are mathematical tools to represent the time
complexity of algorithms for asymptotic analysis.
• Representing time complexity of an algorithm in understandable form.
• Asymptotic order is concerned with how the running time of an
algorithm increases with the size of the input, if input increases from
small value to large values

1. Big-Oh notation (O)


2. Big-Omega notation (Ω)
3. Theta notation (θ)
4. Little-oh notation (o)
5. Little-omega notation (ω)

9/11/21 107
Big-Oh Notation (O)
• Big-oh notation is used to define the worst-case running time of an algorithm
and concerned with large values of n.

• Definition: A function t(n) is said to be in O(g(n)), denoted as t(n) ϵ O(g(n)), if


t(n) is bounded above by some constant multiple of g(n) for all large n. i.e., if
there exist some positive constant c and some non-negative integer n0 such
that

t(n) ≤ cg(n) for all n ≥ n0

• O(g(n)): Class of functions t(n) that grow no faster than g(n).


• Big-oh puts asymptotic upper bound on a function.

9/11/21 108
Big-Oh Notation (O)

9/11/21 109
Big-Oh Notation (O)
1 < log n < √n < n < n logn < n2 < n3 < ……………< 2n < 3n < …. <nn

• Let t(n) = 2n + 3 upper bound


2n + 3 ≤ _____??

2n + 3 ≤ 5n n≥1
here c = 5 and g(n) = n

t(n) = O(n)

2n + 3 ≤ 5n2 n≥1
here c = 5 and g(n) = n2

t(n) = O(n2 )

110
Big-Omega notation (Ω)
• This notation is used to describe the best case running time of algorithms and
concerned with large values of n.

• Definition: A function t(n) is said to be in Ω(g(n)), denoted as t(n) ϵ Ω(g(n)), if


t(n) is bounded below by some positive constant multiple of g(n) for all large
n. i.e., there exist some positive constant c and some non-negative integer n0.
Such that

t(n) ≥cg(n) for all n ≥ n0

• It represents the lower bound of the resources required to solve a problem.

9/11/21 111
Big-Omega notation (Ω)

9/11/21 112
Big-Omega notation (Ω)
1 < log n < √n < n < n logn < n2 < n3 < ……………< 2n < 3n < …. <nn

• Let t(n) = 2n + 3 lower bound


2n + 3 ≥ _____??

2n + 3 ≥ 1n n≥1
here c = 1 and g(n) = n

t(n) = Ω(n)

2n + 3 ≥ 1log n n≥1
here c = 1 and g(n) = log n

t(n) = Ω(log n)
9/11/21 113
Asymptotic Analysis of Insertion sort
• Time Complexity:

• Best Case: the best case occurs if the array is already sorted, tj=1 for
j=2,3…n.

• Linear running time: O(n)

9/11/21 114
Asymptotic Analysis of Insertion sort
• Worst case : If the array is in reverse sorted order

• Quadratic Running time. O(n2)

9/11/21 115
Theta notation (θ)
• Definition: A function t(n) is said to be in θ(g(n)), denoted t(n) ϵ θ(g(n)),
if t(n) is bounded both above and below by some positive constant
multiples of g(n) for all large n. i.e., if there exist some positive constant
c1 and c2 and some non-negative integer n0 such that

c2g(n) ≤ t(n) ≤ c1g(n) for all n > n0


θ(g(n)) = O(g(n)) ∩ Ω(g(n))

15/02/2024 116
Theta notation (θ)

15/02/2024 117
Theta notation (θ)
1 < log n < √n < n < n logn < n2 < n3 < ……………< 2n < 3n < …. <nn

• Let t(n) = 2n + 3 average bound


_c2.g(n)___ ≤ 2n + 3 ≤ _c1. g(n)____??

1n ≤ 2n + 3 ≤ 5n n ≥ 1
here c1 = 5 , c2 = 1 and g(n) = n

t(n) = θ(n)

15/02/2024 118
Properties of O, Ω and θ
General property:
If t(n) is O(g(n)) then a * t(n) is O(g(n)). Similar for Ω and θ
Transitive Property :
If f (n) ϵ O(g(n)) and g(n) ϵ O(h(n)), then f (n) ϵ O(h(n))
that is O is transitive. Also Ω, θ, o and ω are transitive.
Reflexive Property
If f(n) is given then f(n) is O(f(n))
Symmetric Property
If f(n) is θ(g(n)) then g(n) is θ(f(n))
Transpose Property
If f(n) = O(g(n)) then g(n) is Ω(f(n))

9/11/21 119
order of growth of functions in algorithm
Review Questions
1.Indicate constant time complexity in terms of Big-O notation.
A. O(n)
B. O(1)
C. O(logn)
D. O(n^2)
2.Big oh notation is used to describe __________
3.Big O Notation is a _________function used in computer science to
describe an ____________
4.Big Omega notation (Ω) provides _________bound.
5.Given T1(n) =O(f(n)) and T2(n)=O(g(n).Find T1(n).T2(n)

121
Review Questions
1. Give examples of functions that are in Θ notation as well as functions
that are not in Θ notation.
2. Which function gives the positive value of the given input?
3. K (mod) M gives the reminder of ____ divided by ____
4. For a given set of number n, the number of possible permutation will be
equal to the ____________ value of n.
5. ________Notation is used to specify both the lower bound and upper
bound of the function.

You might also like