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.

01/22/2023 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.

01/22/2023 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

01/22/2023 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.

01/22/2023 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.

01/22/2023 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.

01/22/2023 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.

01/22/2023 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. 

01/22/2023 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
01/22/2023 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.
• The array now becomes:
Array now becomes: 13, 17,
25, 2, 31. 2, 13, 17, 25, 31.
• This is the final array after Insertion sort consists of N - 1 passes
• Compare 2 with 25, 17, 13. Where N=5 So 5-1=4
all the corresponding Number of pass=4(4th iteration all the
• Since, 2< 25. Swap 25 and iterations and swapping of elements are sorted)
2. elements.
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);
key=a[i];
for(i=0; i<size; i++)
{ for(j=i-1; a[j] > key && j>=0; j--)
scanf("%d",&a[i]); {
} a[j+1]=a[j];
InsertionSort(a,size);
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-i-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 4

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 5

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 , 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

95
 2.

3.

9/11/21 96
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

102
Time Complexity of Bubble Sort
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))

01/22/2023 116
 Theta notation (θ)

01/22/2023 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)

01/22/2023 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
Properties of O
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)

122
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.
Activity
1. int sumN(int n)
2. {
3. int add = 0;
4. for(int i=1; i<=n; i++)
5. {
6. add += i;
7. }
8. return add;
9. }
DATA STRUCTURES AND
ITS TYPES
https://www.youtube.com/watch?v=d_XvFOkQz5k
Data Structure
• A data structure is basically a group of data elements that are put together
under one name
• Defines a particular way of storing and organizing data in a computer so
that it can be used efficiently
• Data Structures are used in
∙ Compiler design
∙ Operating system
∙ Statistical analysis package
∙ DBMS
• The selection of an appropriate data structure provides the most efficient
solution
Terms in Data Structure
• Data: Data can be defined as an elementary value or the collection of values, for example, student's
name and its id are the data about the student.

• Group Items: Data items which have subordinate data items are called Group item, for example,
name of a student can have first name and the last name.

• Record: Record can be defined as the collection of various data items, 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.

• File: A File is a collection of various records of one type of entity, for example, if there are 60
employees in the class, then there will be 20 records in the related file where each record contains the
data about each employee.

• Attribute and Entity: An entity represents the class of certain objects. it contains various attributes.
Each attribute represents the particular property of that entity.

• Field: Field is a single elementary unit of information representing the attribute of an entity.

Types in Data Structure
Types of Data Structure
Primitive Data Structures:
Primitive data structures are the fundamental data types which are supported by a programming
language. Some basic data types are
∙ Integer
∙ Real
∙ Character
∙ Boolean

Non-Primitive Data Structures:

Non-primitive data structures are those data structures which are created using primitive data
structures. Examples of such data structures include
∙ linked lists
∙ stacks
∙ trees
∙ graphs
LINEAR AND NON-
LINEAR DATA
STRUCTURES
Types of Data Structure – Non Primitive
Linear
Arrays Linked List
• An array is a collection of similar • Dynamic data structure in which
type of data items and each data elements (called nodes) form a
item is called an element of the sequential list
array.
Types of Data Structure – Non Primitive Linear

Stack Queue
• Linear data structure in which • Linear data structure in which the
insertion and deletion of elements element that is inserted first is the
are done at only one end, which is first one to be taken out
known as the top of the stack
Types of Data Structure – Non Primitive - Non Linear

• The data structure where data items are not organized sequentially is

called non linear data structure
• Types
• Trees
• Graphs
Types of Data Structure – Non Primitive - Non Linear

TREES
• A tree is a non-linear data structure which consists of a collection of nodes
arranged in a hierarchical order.
• One of the nodes is designated as the root node, and the remaining nodes
can be partitioned into disjoint sets such that each set is a sub-tree of the
root.
Types of Data Structure – Non Primitive - Non Linear
GRAPHS
• A graph is a non-linear data structure which is a collection of vertices (also
called nodes) and edges that connect these vertices.
• A graph is often viewed as a generalization of the tree structure.
• every node in the graph can be connected with another node in the graph.
• When two nodes are connected via an edge, the two nodes are known as
neighbours.
Review Questions
1. Compare a linked list with an array.
2. Array is dynamic structure (TRUE / FALSE)
3. The data structure used in hierarchical data model is _________
4. In a stack, insertion is done at __________
5. Which Data Structure follows the LIFO fashion of working?
6. The position in a queue from which an element is deleted is called as
__________
 POINTER
https://www.youtube.com/watch?v=BXY4dD6vaIE
Definition and Features of Pointer

⮚Definition:
• Pointer is a variable that stores the address of another variable.
⮚Features
• Pointer saves the memory space.
• Execution time of pointer is faster because of direct access to the memory
location.
• With the help of pointers, the memory is accessed efficiently, i.e., memory
is allocated and deallocated dynamically.
• Pointers are used with data structures.
Pointer declaration, initialization and accessing
• Consider the following statement 
int q = 159;
In memory, the variable can be represented as follows −

q Variable

159 Value

1000 Address
Pointer declaration, initialization and accessing(Cont..)
• Declaring a pointer
It means ‘p’ is a pointer variable which holds the address of another
integer variable, as mentioned in the statement below −
int *p;
• Initialization of a pointer
Address operator (&) is used to initialize a pointer variable.
For example −
int q = 159; Variable Value Address
int *p;
q 159 1000
p = &q;
p 1000 2000
Pointer declaration, initialization and accessing(Cont..)
• Accessing a variable through its pointer
To access the value of a variable, indirection operator (*) is used.

For example −
int q=159, *p, n;
p=&q;
n=*p
Here, ‘*’ can be treated as value at address.
p = &q;
n = *p; n =q
 1D INITIALIZATION &
ACCESSING USING POINTERS
Pointers and one-dimensional arrays
⮚The compiler allocates Continuous memory locations for all the elements of
the array.
⮚The base address = first element address (index 0) of the array.
⮚Syntax: data_type (var_name)[size_of_array] //Declaration
int *p;
• For Example − int a [5] = {10, 20,30,40,50}; int my_arr[] = {11, 22, 33, 44, 55};
p = my_arr;
⮚Elements
• The five elements are stored as follows −
Elements a[0] a[1] a[2] a[3] a[4]

Values 10 20 30 40 50
Address 1000 1004 1008 1012 1016

Base Address
a=&a[0]=1000
Pointers and one-dimensional arrays (Cont)
• If ‘p’ is declared as integer pointer, then, an array ‘a’ can be pointed by the
following assignment −
p = a; (or) p = &a[0];
• Every value of 'a' is accessed by using p++ to move from one element to another
element. When a pointer is incremented, its value is increased by the size of the
data type that it points to. This length is called the "scale factor".
• The relationship between ‘p’ and 'a' is explained below 
p = &a[0] = 1000
p+1 = &a[1] = 1004
p+2 = &a[2] = 1008
p+3 = &a[3] = 1012
p+4 = &a[4] = 1016
Pointers and one-dimensional arrays (Cont..)

• Address of an element is calculated using its index and the scale factor of
the data type. An example to explain this is given herewith.
• Address of a[3] = base address + (3* scale factor of int)
= 1000 + (3*4)
= 1000 +12
= 1012
• Pointers can be used to access array elements instead of using array
indexing.
• *(p+3) gives the value of a[3].
• a[i] = *(p+i)
Acitivity
• Write a C program to find the median of an array.
Example Program

• Following is the C program for pointers and one-dimensional arrays −

#include<stdio.h> main ( )
{ 
int a[5];    
int *p,i;    
printf ("Enter 5 lements");    
for (i=0; i<5; i++)      
scanf ("%d", &a[i]);  
 p = &a[0];    
printf ("Elements of the array are");    
for (i=0; i<5; i++)      
printf("%d", *(p+i));
}
Output
When the above program is executed, it produces the following result −
Enter 5 elements : 10 20 30 40 50
Elements of the array are : 10 20 30 40 50
 Example Program : 1D array using Pointer
#include<stdio.h>
int main()
{
int array[5];
int i,sum=0;
int *ptr;
printf("\nEnter array elements (5 integer values):");
for(i=0;i<5;i++)
scanf("%d",&array[i]);
/* array is equal to base address * array = &array[0] */
ptr = array;
for(i=0;i<5;i++)
{
//*ptr refers to the value at address
sum = sum + *ptr;
ptr++; Output
} Enter array elements (5 integer values): 1 2 3 4 5
The sum is: 15
printf("\nThe sum is: %d",sum);
}
2D INITIALIZATION &
ACCESSING USING
POINTERS
 Pointers and two-dimensional arrays

• Memory allocation for a two-dimensional array is as follows −

0 1 2
int a[3] [3] = {1,2,3,4,5,6,7,8,9};
0 1 2 3

1 4 5 6

Base Address=1000=&a[0][0] 2 7 8 9
a[0][0] a[0][1] a[0][2]
Row 1-> 1 2 3
1000 1004 1008
a[1][0] a[1][1] a[1][2]
Row 2-> 4 5 6
1012 1016 1020

a[2][0] a[2][1] a[2][2]

Row 3-> 7 8 9
1024 1028 1032
Pointers and two-dimensional arrays

• Assigning Base Address to pointer

int *p
p=&a[0][0] (or)
p=a
Pointer is used to access the elements of 2-dimensional array as follows
a[i][j]=*(p+(i*columnsize+j) * scale factor)
a[1] [2] = *(1000 + (1*3+2) *4)
= *(1000 + (3+2) * 4)
= *(1000 + 5*4) // 4 is Scale factor
= * (1000+20)
= *(1020)
a[1] [2] = 6
 Example Program

#include<stdio.h> main ( )
printf ("elements of 2d array Output
{    int a[3] [3], i,j;  
are");    
 int *p;     When the above program is
for (i=0; i<3; i++) executed, it produces the following
clrscr ( );  
result −
 printf ("Enter elements of 2D array");   {   
enter elements of 2D array 1 2 3 4 5
for (i=0; i<3; i++) for (j=0; j<3; j++) 6789
{    {     
Elements of 2D array are
for (j=0; j<3; j++)
printf ("%d \t", *(p+i*3+j));  
{      123
   }      
scanf ("%d", &a[i] [j]);       456
}  printf ("\n");    
789
 }   }  
 p = &a[0] [0];   getch ( );
}
Write a program to read the table elements into a two-dimensional array sales and find the following.
1. Find the total sales of a salesgirl 3
2. Find the salesgirl who gave maximum sales.
3. Find the salesgirl who gave minimum sales.
Review Questions

1. Let’s consider 60 students took this course. Each student is supposed to

give a rating 1, 2, 3 4 or 5; one being bad and 5 being good. Find the ratings
are spread count the number of times each rating was given.
2. Write a Program in C for the following Array operations
a. Creating an Array of N Integer Elements
b. Display of Array Elements with Suitable Headings
c. Inserting an Element (ELEM) at a given valid Position (POS)
d. Deleting an Element at a given valid Position(POS)
e. Exit.
Support the program with functions for each of the above operations.
DECLARING STRUCTURE
AND ACCESSING
https://www.youtube.com/watch?v=zsvTS3y3X24
What is Structure? How to define structures?
Size of structure and memory representation
Structure vs Arrays
Declaring Structure variables
Accessing Structure Members
Definition of Structures
• Structures are user defined data types
• It is a collection of heterogeneous data
• It can have integer, float, double or character data in it
• We can also have array of structures
struct<<structname>>
{
members;
}element;
We can access element.members;
Declaration of Structures
Syntax:
struct struct_Name Example: Structure to hold student
•{ details struct Student
• <data-type> {
member_name;
int regNo;
• <data-type>
member_name; char name[25];
•… int english, science, maths;

• } list of variables; } stud;

Declaration of Structures
Syntax: struct Student
struct struct_Name {
{ int regNo;
<data-type> char
member_name; name[25];
<data-type> int english, science,
member_name; maths;
… };
}; struct Student stud;
struct struct_Name struct_var;
 Declaration of Structures

//Static Initialization of stud

stud.regNo=1425; strcpy(stud.name,“Banu”);
stud.English=78; stud.science=89; stud.maths=56;

//Dynamic Initialization of stud

scanf(“%d %s %d %d %d”,&stud.regNo, stud.name, &stud.English,&stud.science,
&stud.maths);
Accessing and Updating Structures
struct Student
{
int regNo; char
name[25];
int english, science, maths;
};
struct Student stud;
scanf(“%d %s %d %d %d”,&stud.regNo,
stud.name,&stud.english,&stud.science, &stud.maths);
printf("Register number =%d\n",stud.Regno); //Accessing member Regno
//Accessing member name
printf("Name %s",stud.name);
//Updating member english
stud.english= stud.english +10; //Updating member science
stud.science++;
 Nested Structures
struct Student struct Student struct m
{
{ {
int regNo;
int regNo; int english;
char name[25];
char int science;
struct
{
name[25]; int maths;
int english, science, maths; struct m marks;
} marks; } Amar; };
} Amar;

Amar.regNo;
Amar.marks.english;
Amar.marks.science;
Amar.marks.maths;
 Example Program
#include <stdio.h>
#include <string.h>
struct Books
{
char title[50];
char author[50];
char subject[100];
int book_id;
};
int main( )
{
struct Books Book1; /* Declare Book1 of type Book */
struct Books Book2; /* Declare Book2 of type Book */

/* book 1 specification */ strcpy( Book1.title, "C

Programming"); strcpy( Book1.author, "Nuha Ali");
strcpy( Book1.subject, "C Programming Tutorial");
Book1.book_id = 6495407
 Example Program
/* book 2 specification */ strcpy( Book2.title,
"Telecom Billing"); strcpy( Book2.author, "Zara Ali");
strcpy( Book2.subject, "Telecom Billing Tutorial");
Book2.book_id = 6495700;

/* print Book1 info */

printf( "Book 1 title : %s\n", Book1.title); OUTPUT
printf( "Book 1 author : %s\n", Book1.author); Book 1 title : C Programming
printf( "Book 1 subject : %s\n", Book1.subject); Book 1 author : Nuha Ali
printf( "Book 1 book_id : %d\n", Book1.book_id); Book 1 subject : C Programming Tutorial
/* print Book2 info */ Book 1 book_id : 6495407
printf( "Book 2 title : %s\n", Book2.title); Book 2 title : Telecom Billing
printf( "Book 2 author : %s\n", Book2.author); Book 2 author : Zara Ali
printf( "Book 2 subject : %s\n", Book2.subject); Book 2 subject : Telecom Billing Tutorial
printf( "Book 2 book_id : %d\n", Book2.book_id); Book 2 book_id : 6495700
return 0;
}
 Example Program
#include<stdio.h>   void main()  
struct student   {  
{       struct student s1,s2,s3;  
    char name[20];       int dummy;  
    int id;       printf("Enter the name, id, and marks of student 1 ");  
    float marks;       scanf("%s %d %f",s1.name,&s1.id,&s1.marks);  
};       scanf("%c",&dummy);  
    printf("Enter the name, id, and marks of student 2 ");  
    scanf("%s %d %f",s2.name,&s2.id,&s2.marks);  
    scanf("%c",&dummy);  
    printf("Enter the name, id, and marks of student 3 ");  
    scanf("%s %d %f",s3.name,&s3.id,&s3.marks);  
    scanf("%c",&dummy);  
    printf("Printing the details....\n");  
    printf("%s %d %f\n",s1.name,s1.id,s1.marks);  
    printf("%s %d %f\n",s2.name,s2.id,s2.marks);  
    printf("%s %d %f\n",s3.name,s3.id,s3.marks);  
}  
Example Program
Output
Enter the name, id, and marks of student 1
James
90
90
Enter the name, id, and marks of student 2
Adoms
90
90
Enter the name, id, and marks of student 3
Nick
90
90
Printing the details....
James 90 90.000000
Adoms 90 90.000000
Nick 90 90.000000
DECLARING ARRAY OF
STRUCTURES AND
ACCESSING
 Array of Structures
struct Student
{
int regNo;
char
name[25];
int english, science, maths;
};
struct Student stud[10];
scanf(“%d%s%d%d%d”,&stud[1].regNo,stud[1].name,&stud[1].english,&stud[1].science,
&stud[1].maths);

printf("Register number = %d\ //Accessing member Regno

n",stud[1].Regno);
printf("Name %s",stud[1].name); stud. //Accessing member name
[1]english= stud[0].english +10; //Updating member english
stud[1].science++; //Updating member science
Example Program
#include<stdio.h>   int main()
#include <string.h>     {    
struct student{     int i;    
int rollno;     struct student st[5];    
char name[10];     printf("Enter Records of 5 students");    
};     for(i=0;i<5;i++){    
printf("\nEnter Rollno:");    
scanf("%d",&st[i].rollno);    
printf("\nEnter Name:");    
scanf("%s",&st[i].name);    
}    
printf("\nStudent Information List:");    
for(i=0;i<5;i++){    
printf("\nRollno:%d, Name:%s",st[i].rollno,st[i].name);    
}    
   return 0;    
}    
Example Program
OUTPUT
Enter Records of 5 students Enter
Rollno:1 Enter Name:Sonoo Enter
Rollno:2 Enter Name:Ratan Enter Rollno:3
Enter Name:Vimal Enter Rollno:4 Enter
Name:James Enter Rollno:5 Enter
Name:Sarfraz Student Information List:
Rollno:1, Name:Sonoo Rollno:2,
Name:Ratan Rollno:3, Name:Vimal
Rollno:4, Name:James Rollno:5,
Name:Sarfraz
Array of pointer to structures
Syntax: • Maintain database of 10 students

• 10 Structures are Placed in the Memory.

struct stud
• Base addresses are stored in Pointers
{
int roll; • Eg ptr[0],ptr[1] stores the address of First &
second structure respectively.
char name[10];
• The time required to access structure
}*ptr[20];
reduces.

• This is used in Dynamic Memory Allocation.

Accessing elements in Array of ptr
to struct
Eg:Reading the student details:
for(i=0;i<3;i++)
{
ptr[i] = (struct stud *) malloc(sizeof(struct stud));
 
printf("\nEnter the Roll Number : ");
scanf("%d",&ptr[i]->roll);
printf("\nEnter the Name : ");
scanf("%s",ptr[i]->name);
}
struct stud
{
int roll;
char name[10];
}*ptr[10]; Enter the Student Details :
Enter the Roll Number : 101
int main()
{ Enter the Name : arun
int i;
printf("Enter the Student Details : "); Enter the Roll Number : 102
for(i=0;i<3;i++)
{ Enter the Name : sam
ptr[i] = (struct stud *) malloc(sizeof(struct stud));
Enter the Roll Number : 103
printf("\nEnter the Roll Number : ");
scanf("%d",&ptr[i]->roll); Enter the Name : Jeba
printf("\nEnter the Name : ");
scanf("%s",ptr[i]->name); Student Details are :
} Roll Number : 101
printf("\nStudent Details are : "); Name : arun
for(i=0;i<3;i++) Roll Number : 102
Name : sam
{
Roll Number : 103
printf("\nRoll Number : %d",ptr[i]->roll); Name : Jeba
printf("\nName : %s",ptr[i]->name);
}
return(0);
}
Structures Containing Pointers
struct student
{
char *name;
int roll;
float percentage;
};

Name structure member is a pointer type which needs to be

dynamically allocated the memory space.
 Memory Representation
for(i=0;i<3;i++)
{
ptr[i] = (struct stud *) malloc(sizeof(struct stud));
printf("\nEnter the Roll Number : ");
scanf("%d",&ptr[i]->roll);
printf("\nEnter the Name : ");
ptr[i]->name=(char *)malloc(sizeof(char[strlen(name)
+1]));
scanf("%s",ptr[i]->name);
}
struct stud
{
int roll;
char *name;
}*ptr[10];
int main() Enter the Student Details :
{ Enter the Roll Number : 101
int i;
Enter the Name : Ram
printf("Enter the Student Details : ");
for(i=0;i<3;i++) Enter the Roll Number : 102
{
ptr[i] = (struct stud *) malloc(sizeof(struct stud)); Enter the Name : manas
printf("\nEnter the Roll Number : ");
scanf("%d",&ptr[i]->roll); Enter the Roll Number : 103
printf("\nEnter the Name : ");
Enter the Name : Govind
ptr[i]->name=(char *)malloc(sizeof(char[strlen(name)+1]));
scanf("%s",ptr[i]->name); Student Details are :
} Roll Number : 101
printf("\nStudent Details are : "); Name : Ram
for(i=0;i<3;i++) Roll Number : 102
{ Name : manas
printf("\nRoll Number : %d",ptr[i]->roll); Roll Number : 103
Name : Govind
printf("\nName : %s",ptr[i]->name);
}
return(0);
}
 Activity
• Define a structure for the following e-commerce application
e-market.
Array of pointers
Pointer Arrays
• Pointers stores the address of another variable or points to data.
• Pointer Arrays or Array of pointers stores the collection of
pointers.
Review Questions
1. Write a C program for student mark sheet using structure
2. Write a C program using structure to find students grades in a class
3. Write a C program for book details using structure
4. Calculating the area of a rectangle using structures in C language.
Revision
1. Write a traversal algorithm that traverses every alternate element of the linear array starting
with the first element.
69, 22, 46, 5, 83, 17, 49, 35
2. Using Bubble sort algorithm sort the following in ascending order. Find the number of
comparisons and number of interchanges done. Show the state of array after each pass.
1. P E O P L E
2. 32, 51,27,85, 66, 23, 13, 57
3. Using Insertion sort algorithm sort the following in ascending order. Find the number of
comparisons and number of interchanges done. Show the state of array after each pass.
69, 22, 46, 5, 83, 17, 49, 35
 Revision
4. Each student in a class of 51 students takes 4 tests in which scores range between 0 and 100.
a. Find the average grade for each test.
b. Find average grade for each student.
c. Find the number of students who have failed.
5. An array contains 25 positive integers. Write a module which
a. Finds all pairs of elements whose sum is 25.
b. Find the number ENUM of elements of A which are even, and the number ODNUM of elements
of A which is odd.
6. Define a structure called cricket that will describe the following information:
• player name
• team name
• batting average
Using cricket, declare an array player with 50 elements and write a program to read the information
about all the 50 players and print a team-wise list containing names of players with their batting average.