~ASIF KHAN ~MAAZ KHAN

23EC29 23EC28
Data Structure & Algorithm
Module 1: Introduction to Data Structures

INTRODUCTION TO DATA STRUCTURE

Q.1 What is Data structure [5M MAY 15]
Data Structures
A data structure is a way of storing and organizing data in such way that we can perform
operation on these data in an efficient way.
Areas in which data structures are applied extensively
• Compiler Design,
• Operating System,
• Database Management System,
• Statistical analysis package,
• Numerical Analysis,
• Graphics,
• Artificial Intelligence

Q. 2 Explain different types of data structure with example [M-5 May-18]

Types of Data structure [5M MAY17, DEC17]
Data structure is divided into two types

Primitive & Non-Primitive

1. Primitive: The integers, reals, logical data, character data, pointers and reference are
primitive data structures. these data types are available in most programming language as
build in type.
2. Non-primitive: These data structure is derived from primitive data
structures.
examples of non-primitive data structures: array, structure, union, linked list, stack, queue,
tree, graph.

List data structure is divided into two types [5M DEC-16]

a. Linear data structure:
Elements are arranged in a linear fashion, A linear data structure traverses the data elements
sequentially, in which only one data element can directly be reached, Linked list stores data
in an organized linear fashion
All one-one relation can be handled through linear data structure.
e.g Stack, Queue

b. Non-Linear data structure:

Element are arranged in nonlinear fashion, In this, the data elements can be attached to
more than one element exhibiting the hierarchical relationship, all one-many, many-one or
many- many relations are handled in Non-linear data structure.
e.g Trees, Graphs

ADT (Abstract Data Type)

Abstract data type are like user defined data type on which we can perform functions without
knowing what is there inside the datatype and how the operations are performed on them.
• An ADT is composed of
o A collection of Data
o A set of operations on that data
• Specification of an ADT indicate
o What the ADT operations do, not how to implement them
• Implementation of an ADT
o Includes choosing a particular data structure.
Q.3 What are various operations on data structure. [M-3 DEC- 18]
Operations on Data Structures
• Traversing:
Traversing a data structure is accessing each data and accessing only once.
• Searching:
Searching is finding the location of a data in within the given data
structure.
• Inserting:
Inserting is adding a new data in the data structure.
• Deleting :
Deleting is removing a data from the data structure.
• Sorting:
Sorting is arranging of data in some logical order.
• Merging:
Merging is combining of two similar data structures.
Static Array Dynamic Array

1. The memory allocation 1. The memory allocation

occurs during compile time. occurs during run time.

2. The array size is fixed and 2. The array size is not fixed and
cannot be changed. can be changed.

3. The location is in Stack 3. The location is in Heap

Memory Space. Memory Space.
4. The array elements are set to 4. The array elements can be
0 or to empty strings. destroyed during erase
statement and the memory is
then released.
5. This array can be Initialized 5. This array cannot be read or
but not erased. written after destroying.

To find the address of an element in an array the following formula is used-

Address of A[I] = B + W* (I - LB)
I = Subset of element whose address to be found,
B = Base address,
W = Storage size of one element store in any array(in byte),
LB = Lower Limit/Lower Bound of subscript(If not specified assume zero).

Example: Given the base address of an array A[1300 ............1900] as 1020 and the size of
each element is 2 bytes in the memory, find the address of A[1700].
Solution:
Given:
Base address B = 1020
Lower Limit/Lower Bound of subscript LB = 1300
Storage size of one element store in any array W = 2 Byte
Subset of element whose address to be found I = 1700
Formula used:
Address of A[I] = B+W (1 - LB)
Solution:
Address of A[1700] = 1020 + 2 * (1700 - 1300)
= 1020 + 2 * (400)
= 1020 + 800
Address of A[1700] = 1820
Application of Stack:
A stack is a data structure that uses LIFO order.
Some Applications of a stack are:
• Converting infix to postfix expressions.
• Undo/Redo button/operation in word processors.
• Syntaxes in languages are parsed using stacks.
• It is used in many virtual machines like JVM
• Forward-backward surfing in the browser.
• History of visited websites.
• Message logs and all messages you get are arranged in a stack.
• Call logs, E-mails, Google photos' any gallery, YouTube downloads, Notifications (latest
appears first).
• Scratch card's earned after Google pay transaction.

Application of Linked Lists:

A linked list is a sequence data structure, which connects elements, called nodes, through
links.
Some other applications of the linked list are:
• Images are linked with each other. So, an image viewer software uses a linked list to view
the previous and the next images using the previous and next buttons.
• Web pages can be accessed using the previous and the next URL links which are linked
using a linked list.
• The music players also use the same technique to switch between music.
• To keep the track of turns in a multi- player game, a circular linked list is used.
• MS-Paint drawings and shapes are connected via a linked list on canvas.
• Social media content "feeds".

Application of Queue:
A queue is a data structure that uses FIFO order.
Some applications of a queue are:
• Operating System uses queues for job scheduling.
• To handle congestion in the networking queue can be used.
• Data packets in communication are arranged in queue format.
• Sending an e-mail, it will be queued.
• Server while responding to request
• Uploading and downloading photos, first kept for uploading/downloading will be
completed first (Not if there is threading)
• Most internet requests and processes use queue.
• While switching multiple applications, windows use circular queue.
• In Escalators, Printer spooler, Car washes queue.
• A circular queue is used to maintain the playing sequence of multiple players in a game.
Application of Graph:
Graph is a data structure where data is stored in a collection of interconnected vertices
(nodes) and edges (paths).
Some applications of a graph are:
• Facebook's Graph API uses the structure of Graphs.
• Google's Knowledge Graph also has to do something with Graph.
• Dijkstra algorithm or the shortest path first algorithm also uses graph structure to find the
smallest path between the nodes of the graph.
• The GPS navigation system also uses shortest path APIs.
• Networking components have a huge application for graph
• Facebook, Instagram, and all social media networking sites every user is Node
• Data organization
• React's virtual DOM uses graph data structures.
• MS Excel uses DAC (Directed Acyclic Graphs)

Application of Tree:
Trees are hierarchical structures having a single root node.
Some applications of the trees are:
• XML Parser uses tree algorithms.
• The decision-based algorithm is used in machine learning which works upon the
algorithm of the tree.
• Databases also use tree data structures for indexing.
• Domain Name Server(DNS) also uses tree structures.
• File explorer/my computer of mobile/any computer
• BST used in computer Graphics
• Posting questions on websites like Quora, the comments are a child of questions.
• Parsers(XML parser).
• Code Compression(zip).
• DOM in Html.
• Evaluate an expression (i.e., parse).
• Integral to compilers/automata theory.
• To store the possible moves in a chess game.

Application of Binary Search Tree:

• D Game Engine.
• Computer Graphics Rendering.
• Routing table.
Application of Sorting Algorithms
• Order things by their value.
• Backend Databases (Merge Sort).
• Playing Cards with your friends (Insertion Sort).
• sort()-uses IntroSort (a hybrid of Quicksort, Heapsort, and Insertion Sort), Faster than
qsort()
• The contact list on the phone
• Online shopping. To sort prize in different range. example: flipkart and amazon.

Application of Hash Tables:

Hash Tables are store data in key-value pairs. It only stores data that has a key associated with
it. Inserting and Searching operations are easily manageable while using Hash Tables.
Some applications of a hashtable are:
• Data stored in databases is generally of the key-value format which is done through hash
tables.
• Every time we type something to be searched in google chrome or other browsers, it
generates the desired output based on the principle of hashing.
• Message Digest, a function of cryptography also uses hashing for creating output in such
a manner that reaching the original input from that generated output is almost next to
impossible.
• In our computers we have various files stored in it, each file has two very crucial pieces of
information that is, the filename and file h in order to make.

Data structures have many advantages, including:

• Efficient data management: Data structures like trees and hash tables help with faster
data retrieval and management.
• Organized data: Data structures help organize data in memory.
• Scalability: Well-chosen data structures can handle increases in data volume.
• Reusability: Data structures can be used by many parts of a program without needing to
recreate or reorganize the original data.
• Error handling: Using appropriate data structures can help detect and handle
errors.

disadvantages
• Memory access: Some complex data structures can have slow memory access.
• Developer experience: Working with complex data structures requires good
programming skills and experience.
• Fixed size: Arrays have a fixed size, which can limit their use.
BIG O NOTATION
Big O notation is used to measure the performance of any algorithm by providing the order of
growth of the function.
It gives the upper bound on a function by which we can make sure that the function will never
grow faster than this upper bound.
We want the approximate runtime of the operations performed on data structures.
We are not interested in the exact runtime.
Big O notation will help us to achieve the same.

If f(n) and g(n) are the two functions, then

f(n) = O(g(n))
If there exists constants c and no such that c.g(n), for all n no
f(n)
This simply means that f(n) does not grow faster than g(n)

Big O notation is important for several reasons:

• Big O Notation is important because it helps analyze the efficiency of algorithms.
• It provides a way to describe how the runtime or space requirements of an algorithm grow
as the input size increases.
2. Omega Notation
Omega notation represents the lower bound of the running time of an algorithm. Thus, it
provides the best-case complexity of an algorithm.
The execution time serves as a lower bound on the algorithm's time complexity. It is defined
as the condition that allows an algorithm to complete statement execution in the shortest
amount of time.

3. Theta Notation
Theta notation encloses the function from above and below. Since it represents the upper and
the lower bound of the running time of an algorithm, it is used for analyzing the average-case
complexity of an algorithm. The execution time serves as both a lower and upper bound on the
algorithm's time complexity. It exists as both, the most, and least boundaries for a given input
value.
4. Little o asymptotic notation
Big-O is used as a tight upper bound on the growth of an algorithm's effort (this effort is
described by the function f(n)), even though, as written, it can also be a loose upper bound.
"Little-o" (o()) notation is used to describe an upper bound that cannot be tight.

1. Time Complexity.
The time complexity of an algorithm is defined as the amount of time taken by an algorithm to
run as a function of the length of the input. Note that the time to run is a function of the length
of the input and not the actual execution time of the machine on which the algorithm is running
on
How is Time complexity computed?
To estimate the time complexity, we need to consider the cost of each fundamental instruction
and the number of times the instruction is executed.
• If we have statements with basic operations like comparisons, return statements,
assignments, and reading a variable. We can assume they take constant time each O(1).
Statement 1: int a=5;
// reading a variable
statement 2; if( a==5) return
true; // return statement
statement 3; int x= 4>5 ? 1:0;
// comparison
statement 4; bool flag=true;
// Assignment

This is the result of calculating the overall time complexity.

total time = time (statement1) +

time(statement2) + ... time
(statementN)
Assuming that n is the size of the input, let's use T(n) to represent the overall time and t to
represent the amount of time that a statement or collection of statements takes to execute.

T(n) = t(statement1) +
t(statement2) + ... +
t(statementN);

Overall, T(n)= O(1), which means constant complexity.

• For any loop, we find out the runtime of the block inside them and multiply it by the number
of times the program will repeat the loop.

for (int i = 0; i < n; i++) {

cout << "GeeksForGeeks" << endl;
}

For the above example, the loop will execute n times, and it will print "GeeksForGeeks" N
number of times. so the time taken to run this program is:

T(N)= n *( t(cout statement))

= n * 0(1)
=0(n), Linear complexity.

For 2D arrays, we would have nested loop concepts, which means a loop inside a loop.

for (int i = 0; i < n; i++) {

for (int j = 0; j <m; j++) {
cout << "GeeksForGeeks" <<endl;
}
}

For the above example, the cout statement will execute n*m times, and it will print
"GeeksForGeeks" N*M number of times. so the time taken to run this program is:

T(N)= n * m * (t(cout statement))

= n * m * 0(1)
=0(n * m), Quadratic
Complexity.
2. Space Complexity:
The amount of memory required by the algorithm to solve a given problem is called the space
complexity of the algorithm. Problem-solving using a computer requires memory to hold
temporary data or final result while the program is in execution.
How is space complexity computed?
The space Complexity of an algorithm is the total space taken by the algorithm with respect to
the input size. Space complexity includes both Auxiliary space and space used by input.
Space complexity is a parallel concept to time complexity. If we need to create an array of size
n, this will require O(n) space. If we create a two-dimensional array of size n*n, this will require
O(n2) space.

In recursive calls stack space also counts.

Example:
int add (int n){
if (n <= 0){
return 0;
}
return n + add (n-1);
}
Here each call add a level to
the stack :
1. add(4)
2. -> add(3)
3. -> add(2)
4. -> add(1)
5. -> add(0)
Each of these calls is added to
call stack and takes up actual memory.
So it takes O(n) space.

However, just because you have n calls total doesn't mean it takes O(n) space.