S1 To S9 (Upto Mathematical Functions)
S1 To S9 (Upto Mathematical Functions)
S1 To S9 (Upto Mathematical Functions)
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
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
15/02/2024 5
HIGHLIGHT 4
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??
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
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
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
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
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
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
• Space Complexity
o We just need to store three values: `lower_bound`, `upper_bound`, and
`middle_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
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.
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 = 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
• 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
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.
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
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.
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
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.
9/11/21 114
Asymptotic Analysis of Insertion sort
• Worst case : If the array is in reverse sorted order
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
15/02/2024 116
Theta notation (θ)
15/02/2024 117
Theta notation (θ)
1 < log n < √n < n < n logn < n2 < n3 < ……………< 2n < 3n < …. <nn
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.