Data Structure and

Algorithm
4330704
Rutvi S. Sheth
Unit-1 Basic Concepts of Data
Structures
CO1: Perform basic operations on arrays and strings.
 1.1 Data Structure Basic Concepts

• Data Structure: Data structure is a way of storing and organizing data in a

computer so that it can be used efficiently.
• Logical relation among the data items.
• The logical or mathematical model organization is called data structure.
• Data structure means Data + Algorithm(logical arrangement)
• Any processed data is also known as information.
• Storage Representation: Data is stored in RAM or ROM.
1.2 TYPES OF DATA STRUCTURES
 1.2 TYPES OF DATA STRUCTURES
• Primitive Data Structures : The Data structures that are directly processed
by machine using its instructions are known as primitive data structure.
• Following are the primitive data structure:
1. Integer: Integer represents numerical values.
• It can be + or -.
• No of student in a class.
• The sign - magnitude method and 1's complement method are used
to represent integer numbers. Ex: 1000
 1.2 TYPES OF DATA STRUCTURES
2. Real:
• The number having fractional part is called real number.
• Ex: 123.45
• Real numbers are also stored in scientific format.
3. Character:
• Character data structure is used to store nonnumeric information.
• It can be letters [A-Z], [a-z], digits and special symbols.
• A character is represented in memory as a sequence bits.
• Two most commonly known character set supported by computer are ASCII
and EBCDIC
 1.2 TYPES OF DATA STRUCTURES
4. Logical/Boolean:
• A logical data item is a primitive data structure that
• can assume the values of either “true” or “false”.
• Most commonly used logical operators Are AND, OR and NOT.
5. Pointer:
• Pointer is a variable which store the address of another variable.
• It provides faster insertion and deletion of elements.
 1.2 TYPES OF DATA STRUCTURES
• Non Primitive Data Structure: The data structures that are not directly
processed by machine using its instructions are known as non primitive data
structure.
• Non Primitive Data Structure is classified into two categories:
• Linear Data structure
• Non linear Data structure
 1.2 TYPES OF DATA STRUCTURES
• Linear Data structure :
• Logical relation among the data item is linear.
• Data is stored sequentially in memory location.
• Examples of the linear data structure are:
• Array
• Stack
• Queue
• Linked List
 1.2 TYPES OF DATA STRUCTURES
• Array:
• Set of data item using same data type.
• Set of fixed number of item. Insert and delete operation are time
consuming, searching and sorting are fast.
 1.2 TYPES OF DATA STRUCTURES
• Stack:
• A stack is a linear list in which insertion and deletion operations are
performed at only one end of the list.
• It is LIFO (Last In First Out).
 1.2 TYPES OF DATA STRUCTURES
• Queue : A queue is a linier list in which insertion is performed at one end
called rear and deletion is performed at another end of the list called
front.
• It is FIFO (First In First Out).
 1.2 TYPES OF DATA STRUCTURES
• Linked list:
• A linked list is a collection of nodes.
• Each node has two fields:
i. Data/ Information
ii. Address, which contains the address of the next node.
 1.2 TYPES OF DATA STRUCTURES
• Non Linear data structure:
• Logical relation among the data item is not linear.
• Data is not stored sequentially.
• Examples of the non linier data structure are: (A)Tree (B) Graph
o Tree:
• It consists of nodes connected by edge.
• Nodes represent data items. The node represent by circle.
 1.2 TYPES OF DATA STRUCTURES
o Graph:
• This data structure contains relationship between pairs of elements.
• Graphs are of many types:
✓ Directed graph
✓ Undirected graph
✓ Connected Graph
✓ Disconnected graph
 1.2 OTHER TYPES OF DATA STRUCTURES

• Static Data structure: The size of the Data Structure is fixed and not changed during
execution of program. Ex: Array
• Dynamic Data Structure: It is created using dynamic memory location. For that, we use a
pointer variable and its size is allocated during the execution of the program. We can
increase or decrease the size of the data structure easily. Ex: Linked List
• Homogeneous Data Structure: It stores all data of same data type. Ex: Array
• Non-Homogeneous Data Structure: It contains different data type. Ex: Structure, class
 OPERATIONS ON DATA STRUCTURES
1. Traversing: Access each element of the data structure and doing some processing over
the data.
2. Inserting: Insertion of new elements into the data structure.
3. Deleting: Deletion of specific elements.
4. Searching: Searching for a specific element.
5. Sorting: Sorting the data in ascending or descending ordered.
6. Merging: Combination of two data structure.
 1.3 DIFFERENTIATE PRIMITIVE AND NON-PRIMITIVE DATA
STRUCTURES
Feature Primitive Data Structures Non-Primitive Data Structures
Basic building blocks of data More complex structures built from primitive data types
Definition
manipulation
Examples int, char, float, double, boolean Arrays, Lists, Stacks, Queues, Trees, Graphs, Hash
Tables
Memory Directly operated upon by machine- Consist of multiple primitive data types
Structure level instructions
Access Speed Faster (due to direct memory access) Slower (involves more memory operations)
Data Storage Stores a single value Can store multiple values or complex relationships
Operations Basic operations (arithmetic, logical) More complex operations (traversal, insertion, deletion)
Memory Generally higher due to more complex storage
Generally lower
Consumption requirements
Examples of Sorting, searching, graph traversal, tree manipulation
Addition, subtraction, comparison
Operations
 1.4 INTRODUCTION TO ALGORITHMS
• An algorithm is a step-by-step, well-defined set of instructions to solve a
specific problem or perform a particular task.
• Advantage :
1. It is a step-wise representation of a solution to a given problem, which
makes it easy to understand.
2. It is not dependent on any programming language, so it is easy to
understand for anyone even without programming knowledge.
3. Every step in an algorithm has its own logical sequence so it is easy to
debug.
4. By using algorithm, the problem is broken down into smaller pieces or
steps, so it is easier for programmer to convert it into an actual program.
 PROPERTIES OF ALGORITHM
1. Finiteness: “An algorithm must always ter minate after a
finite number of steps”.
2. Definiteness: “Each steps of alg orithm must be precisely defined”.
3. Input: “quantities which are given to it initially before the
alg orithm begins”.
4. Output: “quantities which have a specified relation to the
input”.
5. Effectiveness: “all the operations to be perfor med in the alg orithm
must be sufficient”.
 1.5 KEY FEATURES OF ALGORITHM
1. Name of Algorithm: Every Algorithm is given an identifying name, written in
capital letters.
2. Steps: The algorithm is made of sequence of steps.
3. Assignment Statements: The assignment statement is indicated by arrow. Ex: x
←10
4. If Statements:
a) If (condition)
then
b) If (condition)
then
else
 1.5 KEY FEATURES OF ALGORITHM
5. Repeat Statement
• Repeat while(condition)
• Repeat thru step No for variable name=1,2,…N

6. Case Statement
Select case
Case value 1:
Case value 2:
Case value N:
Default:
 1.5 KEY FEATURES OF ALGORITHM

7. GOTO Statement: It is used for unconditional transfer of

controls.
8. Exit Statement: It is used to terminate an algorithm.
 EXAMPLE OF ALGORITHM
• Example: Write Algorithm to compute the average of n elements.
• Steps:
ALGORITHM: FIND AVERAGE OF N NUMBER
Assume that array contains n integer values.
• Step 1: [INITIALIZE] sum ←0.
• Step 2: [PERFORM SUM OPERATION]
Repeat thru step from i=0 to n-1
sum←sum+a[i]
• Step 3: [CALCULATE AVERAGE]
avg←sum/n
• Step 4: Write avg
• Step 5: [FINISHED]
Exit
 EXAMPLE OF ALGORITHM
• Example: Write Algorithm to compute the average of n elements.
• Steps:
ALGORITHM: FIND NUMBER IS ODD OR EVEN
• Step 1: [READ]
read(x)
• Step 2: [CHECK ODD OR EVEN]
if(x%2=0) then
Write “x is even number”
else
Write “x is odd number”

• Step 3: [FINISHED]
Exit
 1.6 Analysis Terms
• Complexity: Complexity of an algorithm is a function describing the efficiency of the
algorithm in terms of the amount of data.
• Time complexity: Time complexity is defined as the amount of time taken by an algorithm
to run, as a function of the length of the input.
• Space Complexity: It is a function describing the amount of memory an algorithm takes in
terms of the amount of input to the algorithm.
• Asymptotic Notation: Is a way of expressing the cost of an algorithm.
• Worst Case Complexity: Slowest time to complete with chosen input. When the
algorithm takes maximum no of steps on any instance of size n. Example: In
linear search, If searching element is at last position Or In ascending order sorting,
if all the elements are in descending order then time taken by the algorithm is
more.
 1.6 Analysis Terms
• Best Case Complexity: Fastest time to complete with chosen input. When the algorithm takes
minimum no of steps on any instance of size n. Example: In linear search, If searching element is
at First position Or In ascending order sorting, if all the elements are in ascending order then time
taken by the algorithm is less.
• Average case: In average case analysis, we take all possible inputs and calculate the computing
time for all of the inputs by calculating the total running time and divide by the no of trials.
• Big oh notation (O): It is define as upper bound and upper bound on an algorithm is the most
amount of time required ( the worst case performance). Big oh notation is used to describe
asymptotic upper bound. In computer science, big O notation is used to classify algorithms
according to how their run time or space requirements grow as the input size grows.
 1.6 Analysis Terms
• Big Omega Notation (Ω): It is defined as lower bound and lower bound on an
algorithm is the least amount of time required (the most efficient way
possible, in other words best case).Ω notation provides asymptotic lower
bound.
• Big Theta Notation (Θ):It is define as tightest bound and tightest bound is the
best of all the worst case times that the algorithm can take. In simple
language, Big Theta(Θ) notation specifies asymptotic bounds (both upper and
lower) for a function and provides the average time complexity of an
algorithm.
 1.7 Array
• One dimensional array can be declared as int a[20].
• Storage Representation of One Dimensional Array: Representation of
an array in memory location is shown below:
 1.7 Array
• Location(Address) of A[i] in the array is calculated as:
• L0 is the starting(Base) address or address of first element in the array.
• I is the array index.
• L is the starting index of an array.
• S is the size.
• If we want to find the address of A [2] then it is calculated as:
• Loc (A [9]) = Base + (I – L0) * s
• = 2000 + (9-0) * 2
• = 2000 + 18
• = 2018
 1.7 Array
• Two Dimensional Array (Storage Representation)
• Row-major Arrays: If two dimensional array element store sequentially
row by row then it is called Row major array.
 Row-major Arrays
• The address of element A[i, j] can be obtained by evaluating
expression:
• Loc (A [i, j]) = Base + ((i – L1) * n + (j – L2))* s
• i is the row index.
• j is the column index.
• m is the no. of rows .
• n is the no of column.
• s is size.
• L1 is the lower bound for row.
• L2 is the lower bound for column.
 Row-major Arrays
• A[1,2] in a[2][3] is calculated as:
• A [1, 2] = Base + ((i - L1) * n + (j - L2))* s
• Here, n=3, m=2, i=1, j=2,
• Base = 3000
=3000 + ((1 - 0) * 3 + (2 - 0))*2
=3000 + (3+2)*2
=3000 + 10
=3010
 Column-major Arrays
• Column-major Arrays: If two dimensional array elements store
sequentially column by column then it is called Column major array.
• Example: A two dimensional array consist of two rows and three
columns is stored sequentially in row major order as:
 Column-major Arrays
• The address of element A[i, j] can be obtained by evaluating expression:
• Loc (A [i, j]) = Base + ((j – L2) * m + (i – L1) )* s
• i is the row index.
• j is the column index.
• m is the no. of rows .
• n is the no of column.
• s is size.
• L1 is the lower bound for row.
• L2 is the lower bound for column.
 Column-major Arrays
• A[1,2] in a[2][3] is calculated as:
• A [1, 2] = Base + ((j – L2) * m + (i – L1))* s
• Here, n=3, m=2, i=1, j=2,
• Base = 3000
=3000 + ((2 - 0) * 2 + (1 - 0))*2
=3000 + (4+1)*2
=3000 + 10
=3010
 1.8 Overview of different array operations
• Insertion: Add a New data element into the list.
• Deletion: Remove an element from the list.
• Searching: Finding the specific location for specific data.
• Sorting: Arrange the list in Ascending or Descending order.
• Merging: Combine the two lists into single list.
• Traversal: Accessing each data element once in such a way that all the
data elements are processed.
 1.9 Searching an element into an array
• Searching: Search is used to find whether the desired data is present in
set of data or not. If it is present, the search operation provides us its
position. There are two types of searching technique.
1. Linear search / Sequential Search
2. Binary Search
 Linear Search
• This method is used to find out element in an unordered list.
• Suppose the list L consist of N elements and we want to find the
element from the list.
• It sequentially compares the given value with each value in list of values
one by one from start to end until value is found or list is ended.
• If the value is found, the position of the value is returned.
• https://www.youtube.com/watch?v=PDE8pCQ9Tz4 (For Visual
Learning)
 1.9 Searching an element into an array
• SEQENTIAL_SEARCH (L, N, X): 3. [Comparison]
• These function searches the list L If (L[i]= X ) Then
consist of N elements for the value
i. Flag ← 0
of X.
• L: Represents the list of element. ii. Write(“ Search is Successful”)
• N: Represents the no of elements in iii. Write (“ Value found at location: i +1”)
the list 4. If (flag=1) then
• X: Represent the value to be search in
the list Write (“Search is unsuccessful”)
1. [Initialization] 5. [Finished]
i←0 Flag←1
Exit
2. [Search the List]
Repeat thru step 3 for i=0, 1, N-1
 Linear Search
• Advantage:
1. Very Simple
2. Easy to understand and implement
3. Works on both sorted as well as unsorted data, but mainly used for unsorted
data.
• Disadvantage:
1. Search Time is not unique, if value is in start it takes less time, but if value is
near to end it takes more time.
2. As the size of data increase, the search time also linearly increases.
 Binary Search
• This method is used to find out element in an ordered list.
• It is very efficient method to search element.
• It first computes the middle which is index of the middle value. Then it compares the
value to be search with middle element.
• If both matches, the value is found and index of middle element is returned.
• If both doesn’t matches, then list is divided into two parts called lower half and upper
half.
• All the value in lower half are less than the middle element and all the value in upper
half are greater than the middle element.
• If value to be search is less than middle element then we have to repeat the process
with the lower half and if value to be search is greater than middle element then we
have to repeat the process with the greater half.
• https://www.youtube.com/watch?v=tfq_T2cM_fc (For Visual Learning)
 Binary Search
• BINARY_SEARCH (L, N, X) 4. [Compare]
• L: Represents the list of element. If X < L [MIDDLE] then
• N: Represents the no of elements in the list. HIGH ← MIDDLE – 1
• X: Represent the value to be search in the list. Else if X>L[MIDDLE] then
LOW ← MIDDLE+1
• LOW, HIGH and MIDDLE denotes the
lower, upper and middle limit of the list. Else
1. [Initialize] ← Write “Successful Search”
LOW ← 0 Flag ← 0
HIGH ← N-1 Return (MIDDLE)
Flag ← 1 5. If (Flag=1)
2. [Perform Search] Write “Unsuccessful Search”
Repeat thru step 4 while LOW ≤ HIGH 6. [Finished]
3. [Obtain Index of mid point interval] Exit.
MIDDLE ←[(LOW + HIGH)/2]
Binary Search Example
Binary Search Example
 Time Complexity
• Linear Search

• Binary Search