TRB COMPUTER SCIENCE

2025

DATA STUCTURES &ALGORITHMS

CLASS 1

DIVYA RAJESH
Data Structures and Algorithms
SYLLABUS

Data Structures: Abstract data types, Arrays and their Applications, Sparse
Matrix, Stacks, Queues, Priority Queues, Linked Lists.

Trees and Graphs: Trees, Forest, Binary Tree, Threaded Binary Tree, Binary
Search Tree, AVL Tree, B Tree, B+ Tree, B* Tree, Graphs, Sorting and Searching
Algorithms, Hashing.

Performance Analysis of Algorithms and Recurrences: Time and Space

Complexities, Asymptotic Notation, Recurrence Relations.

Design Techniques: Divide and Conquer, Dynamic Programming, Greedy

Algorithms, Backtracking, Branch and Bound.
Data Structures and Algorithms
SYLLABUS

Graph Algorithms: Breadth-First Search, Depth-First Search, Shortest Paths,

Maximum Flow, Minimum Spanning Trees.

Advanced Algorithms: Parallel Algorithms for Sorting, Searching and Merging,

Approximation Algorithms, Randomized Algorithms.
 Introduction
DSA (Data Structures and Algorithms) is the study of organizing data efficiently
using data structures like arrays, stacks, and trees, paired with step-by-step
procedures (or algorithms) to solve problems effectively. Data structures manage
how data is stored and accessed, while algorithms focus on processing this data.
Data structures can be classified into two broad categories:
Linear Data Structure:
Non-linear Data Structure:
PIC COURTESY:Geeksforgeeks
• Linear Data Structures
• Elements arranged in sequential order
• Eg: Arrays, Stack ,Queue,Linked List
• Non Linear Data Structures
• Elements arranged in random order
• Eg: Trees, Graphs

• Static Data Structures

• Size is fixed
• Eg: Array
• Dynamic Data Structures
• Size is variable
• Can change at run time
• Eg: Linked List
 ARRAYS

• Type: Linear & static data structure.

• Definition: Collection of similar data items (all same data type).
• Memory: Stored in contiguous memory locations.
• Access: Elements accessed using index values (0-based indexing in
most languages like C, Python, Java).
• int a[10]; // 1D array
• int b[3][2]; // 2D array
Types of Arrays
By Size
Fixed-size → Size defined at creation, cannot change.
Dynamic-size → Size can grow/shrink during runtime.
By Dimensions
1-D → Single row (list).
2-D → Table (rows & columns).
3-D+ → Multi-layer tables.
Operations on Arrays
Traversal – Visit each element (forward or reverse).
Insertion – Add element at start, middle, or end (may shift elements).
Deletion – Remove element and shift remaining elements.
 Arrays cont…

Searching
Linear Search – Check each element (works on any array).
Binary Search – Fast search on sorted arrays (divide &
conquer).
Applications of Array Data Structure
Storing & Accessing Data – Stores elements in a specific order;
allows constant-time O(1) access.
Searching – If sorted, supports efficient searching (O(log n))
and finding floor, ceiling, kth smallest/largest, etc.
Matrices – Used for 2D array operations in graph algorithms, image
processing, etc.
Implementing Other Data Structures – Basis for stacks, queues, etc.
Dynamic Programming – Stores intermediate results of subproblems.
Data Buffers – Temporarily stores incoming data like packets, file
streams, database results.
Advantages
•Fast Access – Direct O(1) element access via index.
•Memory Efficiency – Contiguous allocation reduces fragmentation.
•Versatility – Can store many data types (int, float, char, objects,
pointers).
•Hardware Friendly – Works well with most architectures

Disadvantages
Fixed Size – Cannot resize easily; resizing requires creating & copying to
a new array.
Memory Allocation Issues – Large arrays may cause exhaustion or
crashes.
Insertion & Deletion Costly – Requires shifting elements.
Homogeneous Data Only – All elements must be of same type.
Less Flexible – Compared to linked lists, trees, etc.
 STACK
Type: Linear data structure.
Access style: Resembles serial access memory.
Elements: Collection of similar data items (same data type).
Implementation:
Array → Static stack.
Linked list → Dynamic stack
Order: LIFO — Last In, First Out.
Operations:
Push → Insert element.
Pop → Delete element.
Access point: Insertion & deletion occur only at one end → top.
Top pointer: Keeps track of the top element for push/pop operations.
 STACK cont..

• Push operation
• Top=Max---stack is full
• If Stack is full—Can’t insert new element -----Overflow condition
• Before inserting new element -----top=top+1
• Pop operation
• Top=0-----stack is empty
• If stack is empty----Can’t delete------Underflow condition
• After deleting an element----top=top-1
Stack can be represented by
(a) array only
(b) linked list only
(c) both (a) and (b)
(d) Neither (a) or (b)
Stack can be represented by
(a) array only
(b) linked list only
(c) both (a) and (b)
(d) Neither (a) or (b)
In a stack, the data item placed on the stack first
is,
(a).The first data item to be removed
(b).The last data item to be removed
(c).Not given as index number
(d).None of these
In a stack, the data item placed on the stack first
is,
(a).The first data item to be removed
(b).The last data item to be removed
(c).Not given as index number
(d).None of these
• Example for LIFO structure
(a).Queue
(b).Linked List
(c).Graph
(d).Stack
Which of the following is useful in traversing a given
graph by depth wise?
(a).List
(b).Queue
(c).Set
(d).Stack
Which of the following is useful in traversing a given
graph by depth wise?
(a).List
(b).Queue
(c).Set
(d).Stack
 Applications OF STACK
• Recursion
• Reverse a string
• Check balance of
parenthesis
• Infix to postfix conversion
• Infix to prefix conversion
• Postfix evaluation
• Store local variables
• Graph traversal ---DFS
• Tree traversals
• Topological sorting
• Implementing quick sort
STACK APPLICATIONS Contd…
Notations for Arithmetic Expressions

Arithmetic expressions can be represented in three different notations

depending on the placement of the operator relative to the operands:
● Three notations are −
a) InfixNotation
b) Prefix (Polish) Notation
c) Postfix (Reverse-Polish) Notation
● These notations are named as how they use operator in
expression.
Infix Notation
● In infix notation, operators are used in-between
operands.
● Requires parentheses to specify precedence.
● E.g.
A-(B +C)
A+B
Prefix Notation - also known as Polish Notation.
• The operator is placed before the operands.
• No need for parentheses (order is unambiguous).
• Evaluated from right to left.
• Useful for stack-based evaluation without precedence rules.
E.g.
+A B
*+A B C
Postfix Notation- Also known as Reverse Polish Notation(RPN or
Suffix Notation)
● Inthis notation style, the operator is postfixed to the operands i.e., the operator
is written after the operands.
● Parenthesis are not used.
● For example AB+.This is equivalent to its infix notation A +B.
Precedence and associativity of operators
● Operator Precedence → Decides which operator executes first in an
expression.
● Operator Associativity → Decides order when operators have the
same precedence.
Left Associative → Left to Right
● Right Associative → Right to Left
● Highest precedence → Parentheses (evaluated first, Left
Associative).
Precedence and associativity of operators
Priority Operator Description Assiciativity

1 :: Scope Left

2 (), [], ->, sizeof Left

++, --, !, &, *, (type),
3 Unary operators Right
+, -
4 *, /, % Arithmetic Left
5 +, - Arithmetic Left
6 <, <=, >=, > Relational Left
7 ==, != Relational Left
8 &&, ` `
9 ?: Conditional Right
10 =, +=, -=, *=, /=, %= Assignment Right
11 , Comma Left
Commonly used operators with precedence

1. ^,$
2. *,/
3. %
4. +,-
Infix to Postfix Conversion (Using Stack)
•Stack stores operators during conversion.
•Steps:
• Read infix expression left → right.
• Operand → Add to output.
• ‘(’ → Push to stack.
• Operator Θ → Pop from stack to output until top has
same/higher precedence, then push Θ.
• ‘)’ → Pop stack to output until ‘(’ is found, then discard
‘(’.
• Repeat until expression ends.
• Pop remaining operators to output.
Example 1

5*(6+2)-(12/4)

=> 5 6 2 +*12 4 /-
Example 2

(A+B)/(C-D)

=> AB+ CD- /

A*B/C+D-E*F

=>AB*C/D+EF*-
Postfix Evaluation (Using Stack)
1.Start.
2.For each character in the postfix expression:
1. Operand → Push to stack.
2.Operator → Pop OP2, then OP1.
3.Compute: Result = OP1 operator OP2.
4.Push result back to stack.
5.Repeat until expression ends.
6.Final result = Top of stack.
Example: 4 5 6 *+

Ans: 34
Example: 7 4 - 3 * 1 5 + / *

Ans: -14
Postfix to Infix Conversion – Algorithm
1.Read the postfix expression from left to right.
2.If the symbol is an operand, push it onto the stack.
3.If the symbol is an operator:
a. Pop OP2 from the stack.
b. Pop OP1 from the stack.
c. Form the string "(OP1 operator OP2)".
d. Push this string back onto the stack.
4.Repeat steps 2 and 3 until the end of the postfix expression is reached.
5.The only element left in the stack is the required infix expression.
Find the postfix evaluation of 33 1 *+8 -

Answer: -2
Example : Find the infix expression of abc- +de–fg- h+/*

=>( a+(b-c))*((d-e)/((f-g)+h))
In short:
•Postfix Evaluation → produces a
number.
•Postfix to Infix Conversion → produces
an algebraic expression.
Infix → Prefix Conversion (Using Stack)
Steps:
1.Scan the infix expression right → left.
2.If operand → add to output.
3.If ')' → push to stack.
4.If operator (Θ):
1. Pop and add to output all operators with
higher precedence.
2. For '^' (right-associative), pop operators with
same or higher precedence.
3. Push Θ to stack.
5.If '(' → pop and add to output until ')' is found.
Discard parentheses.
6.Repeat until input ends.
7.Reverse output → final prefix expression.
Example : ((A+B)*(C+D)/(E-F))+G
Reverse the output expression to get the prefix notation.

Answer: +/*+AB+CD-EFG
Example 2:(A+B^C)*D+E^5
Reverse the output expression to get the prefix notation.

Ans: +*+A^BCD^E5
HOME TASK

(A+B)/C*D-E

=>- */+ABCDE
Prefix Evaluation (Using Stack)

Steps:
1. Start
2. Scan the expression from right to left
3. If operand → push to stack
4. If operator:
a. Pop 2 elements → OP1, OP2
b. result = OP1 operator OP2
c. Push result back to stack
5. Repeat until all characters are processed
6. Pop final result from stack
7. Stop
Example 1 :Evaluate the prefix expression +9*26.

Prefix Evaluation:21
Example 2 :Evaluate the prefix expression
--+2*3 4/16 ^ 2 3.

Prefix Evaluation:12
Example 3 :Find the infix expression of -+8/63 2
and evaluate the same.
Example 5 : Find the infix expression of +- *AB/CDE

=>((A*B)-(C/D))+E
Which of the following is the postfix equivalentof
A+(B*C-(D/E^F)*G)*H.

(a) ABC*DEF^/G*-H*+
(b) ABC*DEF^/G*H*+
(c) ABC*DEF/^G*-H*+
(d).ABC*DEF/^G-*H*+
Which of the following is the postfix equivalentof
A+(B*C-(D/E^F)*G)*H.

(a) ABC*DEF^/G*-H*+
(b) ABC*DEF^/G*H*+
(c) ABC*DEF/^G*-H*+
(d).ABC*DEF/^G-*H*+
Expression in which Operator is written after Operand is called as
(a).Infix
(b).Postfix
(c).Prefix
(d).Polish
Expression in which Operator is written after Operand is called as
(a).Infix
(b).Postfix
(c).Prefix
(d).Polish
While evaluating a prefix expression, the string is read from?

a) left to right
b) right to left
c) center to right
d) center to left to right
While evaluating a prefix expression, the string is read from?

a) left to right
b) right to left
c) center to right
d) center to left to right
The prefix form of an infix expression p +q - r *t is?

[ISRO ]
a) +pq - *rt

b)- +pqr *t

c) - +pq *rt

d)- +*pqrt
The prefix form of an infix expression p +q - r *t is?

[ISRO ]
a) +pq - *rt

b)- +pqr *t

c) - +pq *rt

d)- +*pqrt
Which data structure is used when converting an
infix notation to prefix notation?

a) Linked List

b) Queue

c) Stack

d) Tree
Which data structure is used when converting an
infix notation to prefix notation?

a) Linked List

b) Queue

c) Stack

d) Tree
When an operand is read, which of the following is done
in case of postfix evaluation?

(a).Itis placed on the stack

(b).Itis placed on the output expression
(c).It is ignored

(d).Nothing is done
When an operand is read, which of the following is done
in case of postfix evaluation?

(a).Itis placed on the stack

(b).Itis placed on the output expression
(c).It is ignored

(d).Nothing is done
 QUEUE
Linear Data Structure – FIFO (First In, First Out)

Pointers:
- Front
- Rear

Operations:
- Insertion (Enqueue) – Add an element at the Rear
- Deletion (Dequeue) – Remove an element from the
Front

CRACK CS IT WITH DIVYA 62

 QUEUE
● One element:
Deletion (Through Front):
- Update: front = front + 1 front==rear
● Overflow:
Insertion (Through Rear):
- Update: rear = rear + 1 (rear=maxsize-1) OR (rear=maxsize)
● Underflow:
front=-1 OR (front=0)

CRACK CS IT WITH DIVYA 63

Queue Applications:
- BFS in graphs
- Resource sharing among consumers
- CPU & Disk scheduling
- Printer spooling
- Asynchronous I/O (buffers)
- Mail queues

CRACK CS IT WITH DIVYA 64

Queue can be represented in two ways:
- Array Representation – Static
- Linked List Representation (using pointers) – Dynamic

CRACK CS IT WITH DIVYA 65

Algorithm – Insertion in Queue (Array Implementation)

Step 1:
If REAR = N - 1 Then
Print "Overflow"
Exit
Step 2:
If FRONT = NULL Then
FRONT = 0
REAR = 0
Else
REAR = REAR + 1
Step 3:
QUEUE[REAR] = ITEM
Step 4:
Return

CRACK CS IT WITH DIVYA 66

Algorithm – Deletion in Queue (Array
Implementation)

Step 1:
If FRONT = NULL Then
Print "Underflow"
Exit

Step 2:
ITEM = QUEUE[FRONT]

Step 3:
If FRONT = REAR Then
FRONT = NULL
REAR = NULL
Else
FRONT = FRONT + 1

Step 4:
Return
CRACK CS IT WITH DIVYA 67
 TYPES OF QUEUE

❖ Normal (Linear) Queue

❖ Circular Queue
❖ Deque (Double Ended Queue)
❖ Priority Queue

CRACK CS IT WITH DIVYA 68

CIRCULAR QUEUE
❖ It is a linear data structure in which the operations are
performed based on FIFO (First In First Out) principle and
the last position is connected back to the first position
to make a circle.
❖ It is also called 'Ring Buffer’.
● Two pointers FRONT and REAR (head and tail)

● FRONT track the first element of the queue ---DEQUEUE

● REAR track the last element of the queue ----ENQUEUE

● Initially, set value of FRONT and REAR to -1

CRACK CS IT WITH DIVYA 69

Applications of Circular Queue

● CPU scheduling

● Memory management

● Traffic Management

CRACK CS IT WITH DIVYA 70

Circular Increment:
A Circular Queue works using the process of circular
increment.
Circular increment is done using modulo division with the
queue size.

Example:
SIZE = 5, REAR = 4, FRONT = 2
REAR is at the last position, so:
REAR = (REAR + 1) % SIZE
= (4 + 1) % 5
=5%5
= 0 (start of queue)

CRACK CS IT WITH DIVYA 71

 EnqueueOperation
● Check if the queue is full
● Case 1:FRONT =0 && REAR ==SIZE - 1

● Case 2: FRONT =(REAR +1) mod n

● Circularly increase the REAR index by 1 (i.e. if the rear reaches the end,
nextitwould be at the start of the queue)

• REAR=(REAR+1)%SIZE

CRACK CS IT WITH DIVYA 72

 Dequeue Operation
● Check if the queue is empty FRONT =-1

● Circularly increase the FRONT index by 1

• FRONT=(FRONT+1)%SIZE

● For the last element, reset the values of FRONT and REAR to -1

The time complexity of the enqueue and dequeue operations of a

circular queue is O(1) .

CRACK CS IT WITH DIVYA 73

Example for FIFO structure
(a).Linked list
(b).Queue
(c).Graph
(d).Stack

CRACK CS IT WITH DIVYA 74

Example for FIFO structure
(a).Linked list
(b).Queue
(c).Graph
(d).Stack

CRACK CS IT WITH DIVYA 75

A linear list of elements in which deletion can be done from one end and
insertion can take place only at the other end is known as?

a) Queue
b) Stack
c) Tree
d) Linked list

CRACK CS IT WITH DIVYA 76

A linear list of elements in which deletion can be done from one end and
insertion can take place only at the other end is known as?

a) Queue
b) Stack
c) Tree
d) Linked list

CRACK CS IT WITH DIVYA 77

Ifthe elements '5', '2', '3' and '4' are inserted in a queue, what would be
the order for removal?

a. 5234

b. 432 5

c. 324 5

d. None of the above

CRACK CS IT WITH DIVYA 78

Ifthe elements '5', '2', '3' and '4' are inserted in a queue, what would be
the order for removal?

a. 5234

b. 432 5

c. 324 5

d. None of the above

CRACK CS IT WITH DIVYA 79

A normal queue, if implemented using an array of size MAX_SIZE,
gets full when

a) Rear=MAX_SIZE-1

b) Front=(rear+1)mod MAX_SIZE

c) Front=rear+1

d) Rear=front

CRACK CS IT WITH DIVYA 80

A normal queue, if implemented using an array of size MAX_SIZE,
gets full when

a) Rear=MAX_SIZE-1

b) Front=(rear+1)mod MAX_SIZE

c) Front=rear+1

d) Rear=front

CRACK CS IT WITH DIVYA 81

 A circular queue is implemented using an array of size 10. The array index
starts with 0, front is 6, and rear is 9. The insertion of next element
takes place at the array index.

a) 0
b) 7
c) 9
d) 10

CRACK CS IT WITH DIVYA 82

 A circular queue is implemented using an array of size 10. The array index
starts with 0, front is 6, and rear is 9. The insertion of next element
takes place at the array index.

a) 0
b) 7
c) 9
d) 10

CRACK CS IT WITH DIVYA 83

2. If the MAX_SIZE is the size of the array used in the implementation of
circular queue, array index start with 0, front point to the first element in the
queue, and rear point to the last element in the queue. Which of the
following condition specify that circular queue is EMPTY?

a) Front=rear=0
b) Front= rear=-1
c) Front=rear+1
d) Front=(rear+1)%MAX_SIZE

CRACK CS IT WITH DIVYA 84

2. If the MAX_SIZE is the size of the array used in the implementation of
circular queue, array index start with 0, front point to the first element in the
queue, and rear point to the last element in the queue. Which of the
following condition specify that circular queue is EMPTY?

a) Front=rear=0
b) Front= rear=-1
c) Front=rear+1
d) Front=(rear+1)%MAX_SIZE

CRACK CS IT WITH DIVYA 85

 DEQUE
● Stands for Double Ended Queue
● Itis a linear list in which elements can be added or removed at either end but
not in the middle.
● Itdoes not follow FIFO rule
● DEQUE is maintained by a circular array with
Pic courtesy:
LEFT(FRONT) and RIGHT(REAR) pointers. Geeksforgeeks

CRACK CS IT WITH DIVYA 86

 TYPES OF DEQUE

1. Input Restricted Deque

In Input-restricted deque deletion can be performed at both
the end of the deque, but insertion can be performed at one
end only.
2.OutputRestrictedDeque
In this deque, deletion is restricted at a single end but allows
insertion at both the ends.
Applicationsofdeque
● Palindrome checker.
● A-steal job scheduling algorithm (multiprocessor scheduling).
● Undo-redo operations in software applications.

CRACK CS IT WITH DIVYA 87

Priority Queue – Introduction
A priority queue stores elements with an associated priority. Elements
with higher priority are served before lower-priority ones.
•Implementation: Commonly via Binary Heap (min-heap or max-heap)
using arrays.
•Uses: Dijkstra’s algorithm, Prim’s algorithm, Huffman coding.
● The element can be inserted or deleted not only at the
ends but atanypositionon the queue.
● The priority of element is decided by its value known as implicit
priority and priority number is assigned with each element is known as
explicit priority.

CRACK CS IT WITH DIVYA 88

Two types of priority queue:
Ascending order priority queue
In ascending order priority queue, a lower number is given a higher
priority. In this elements can be inserted in any order.
But, while deleting elements from the queue always a smallest priority
element to be deleted first.
Descending order priority queue
● Indescending order priority queue, a higher number is given a higher
priority.
● Inthis elements can be inserted in any order.
● But, whiledeletingelements from thequeue always a larges priority element to
be deleted first.

CRACK CS IT WITH DIVYA 89

Priority Queue cont..
Operations:
•Insert: Place element according to priority.
•Delete: Remove highest priority element.
•Peek: View highest priority element without
removing it.
Difference from Normal Queue:
•Normal Queue → FIFO order.
•Priority Queue → Order decided by priority,
not arrival time

CRACK CS IT WITH DIVYA 90

 Applications of Priority Queue

● Prim's algorithm
● Dijkstra's shortest path algorithm
● A* Search algorithm
● Priority queues are used to sort heaps.
● Used in operating system for load balancing and
interrupt handling.
● Priority queues are used in huffman codes for data
compression.
● In traffic light, depending upon the traffic, the colors will
be given priority.

CRACK CS IT WITH DIVYA 91

Which of the following is not an application of priority
queue?
a) Huffman codes
b) Interrupt handling in operating system
c) Undo operation in text editors
d) Bayesian spam filter

CRACK CS IT WITH DIVYA 92

Which of the following is not an application of priority
queue?
a) Huffman codes
b) Interrupt handling in operating system
c) Undo operation in text editors
d) Bayesian spam filter

CRACK CS IT WITH DIVYA 93

Which of the following data structure allows you to delete the
elements from both the ends while insertion in only one end?

a. Input-restricted deque

b. Output-restricted deque

c.Priority queue

d. None of the above

CRACK CS IT WITH DIVYA 94

Which of the following data structure allows you to delete the
elements from both the ends while insertion in only one end?

a. Input-restricted deque

b. Output-restricted deque

c.Priority queue

d. None of the above

CRACK CS IT WITH DIVYA 95

A singly linked list is a type of linked list in which each node contains two parts:
Data: The value or data that the node stores.
Next: A pointer/reference to the next node in the list.
The last node in a singly linked list has its next pointer set to null, indicating the end of
the list.

A doubly linked list is a type of linked list where each node contains
three parts:
Data: The value stored in the node.
Next: A pointer to the next node in the list.
Previous: A pointer to the previous node in the list.

CRACK CS IT WITH DIVYA 96

A circular linked list is a type of linked list where the last node
points back to the first node, forming a circle.
Can be singly or doubly circular: In singly circular linked lists, each
node points to the next node, and the last node points to the head.
In doubly circular linked lists, each node has pointers to both the
next and the previous nodes.No NULL at the end: Unlike other
linked lists, the last node does not point to NULL.

Circular linked lists are especially helpful for tasks like scheduling and
managing playlists , this allowing for smooth navigation.

CRACK CS IT WITH DIVYA 97

 Comparison LINKED LIST
ARRAY ➢ Linear Data Structure
➢ Dynamic
➢ Linear Data Structure
➢ Memory allocated at run time.
➢ Static
➢ Size not fixed...Variable
➢ Memory allocated at compile time.
➢ Not Stored in contiguous memory
➢ Size fixed… Can’t change
locations
➢ Stored in contiguous memory locations
➢ Sequential Access
➢ Random Access using index ➢ Memory overhead for pointers
➢ No memory overhead ➢ No wastage of memory
➢ Wastage of memory ➢ Insertion and deletion are easier
➢ Insertion and deletion are difficult ➢ Programming is difficult
➢ Programming is easy

CRACK CS IT WITH DIVYA 98

Each node in a singly linked list contain minimum two fields one
field called data field to store data. Another field is of type -------
------.

(a).pointer to next node

(b).pointer to integer
c).pointer to character
(d).pointer to class

CRACK CS IT WITH DIVYA 99

Each node in a singly linked list contain minimum two fields one
field called data field to store data. Another field is of type -------
------.

(a).pointer to next node

(b).pointer to integer
c).pointer to character
(d).pointer to class

CRACK CS IT WITH DIVYA 100

Generally, collection of Nodes is called as
.

(a) Stack
(b) Linked List
(c) Pointer
(d) Heap

CRACK CS IT WITH DIVYA 101

Generally, collection of Nodes is called as
.

(a) Stack
(b) Linked List
(c) Pointer
(d) Heap

CRACK CS IT WITH DIVYA 102

 Memory Reuse in Linked Lists
● Garbage collection is a technique in which the OS collects the deleted
space time to time onto the availability list(AVAIL LIST).
● The heap is handled as a linked list of unused blocks of memory, so called
free- list (or Avail list).
Overflow
● Inlinked list overflow occurs during insertion operation when AVAIL=NULL.
● That is there is no available space in the avail list.
Underflow
● Inlinked list underflow occurs during deletion operation when START=NULL.

CRACK CS IT WITH DIVYA 103

Applications of linked list
1. Implementation of stacks and queues
2. Implementation of graphs
3. Dynamic memory allocation : We use linked list of free blocks.
4. Manipulation of polynomials
5. Representing sparse matrices

CRACK CS IT WITH DIVYA 104

What is the time complexity to count the
number of elements in the linked list?

a) O(1)

b) O(n)

c) O(log n)

d) O(n2)

CRACK CS IT WITH DIVYA 105

What is the time complexity to count the
number of elements in the linked list?

a) O(1)

b) O(n)

c) O(log n)

d) O(n2)

CRACK CS IT WITH DIVYA 106

Linked list is also known as .

(a) One way list

(b) Two way list
(c) Static list
(d) None

CRACK CS IT WITH DIVYA 107

Linked list is also known as .

(a) One way list

(b) Two way list
(c) Static list
(d) None

CRACK CS IT WITH DIVYA 108

To maintain a linked list in memory , how many
parallel arrays of equal size are used?

a. One

b. Two
c. Three
d. Four

CRACK CS IT WITH DIVYA 109

To maintain a linked list in memory , how many
parallel arrays of equal size are used?

a. One

b. Two
c. Three
d. Four

CRACK CS IT WITH DIVYA 110

Doubly Linked list is also known as
.

(a) One way list

(b) Two way list
(c) Static list
(d) None

CRACK CS IT WITH DIVYA 111

Doubly Linked list is also known as
.

(a) One way list

(b) Two way list
(c) Static list
(d) None

CRACK CS IT WITH DIVYA 112

TREE DATA STRUCTURE

CRACK CS IT WITH DIVYA 113

 TREES
Trees – Non-Linear Data Structure
A tree organizes data hierarchically using nodes connected by edges
(branches).
Basic Terms
Node: Each element in the tree (represented by a circle).
Root Node: First node in the tree; no parent; only one root per tree.
Leaf Node / Terminal Node / External Node: Node with no children (degree
= 0).
Parent Node: Immediate predecessor of a node (has one or more children).
Child Node: Immediate successor of a node.

CRACK CS IT WITH DIVYA 114

Siblings: Nodes sharing the same parent.
Degree of a Node: Number of children of the node.
Degree of a Tree: Maximum degree among all nodes.
Internal Node / Non-Terminal Node: Node with at least one child (root included
if tree has >1 node).

CRACK CS IT WITH DIVYA 115

Properties
•A tree with n vertices has n – 1 edges.
•Path: Sequence of nodes connected by edges.
• Path length: Number of edges in the path.
• Branch: Path ending in a leaf node.
•Level of a Node: Distance from root (root = level 0).
•Height of a Node: Edges in the longest path from that node to a
leaf.
•Height of a Tree: Height of the root = maximum level in the tree.
•Depth of a Node: Length of path from root to the node (same as
level).

CRACK CS IT WITH DIVYA 116

Relations
•Subtree: Tree formed by any node and its
descendants.
•Ancestors: All nodes on the path from root to
the node (excluding itself).
•Descendants: All nodes in the path from the
node down to leaf nodes (excluding itself).

CRACK CS IT WITH DIVYA 117

Predecessor & Successor
•(General tree)
• Predecessor of a node: its immediate
parent (one level above).
• Successor of a node: its immediate child
(one level below).

CRACK CS IT WITH DIVYA 118

Types of Trees

CRACK CS IT WITH DIVYA 119

 Binary Tree

● A tree in which each node has a degree of at

most 2.
● ie. it can have either 0,1 or 2 children.
● The possible children of a binary tree are
usually referred to as left child and right child.

CRACK CS IT WITH DIVYA 120

 Representation of binary tree

1. Array representation
● The root is always stored at index 1 in the array.
● If any node is stored at K position then the left child of that
node is stored at index 2k and the right child is stored at
index 2K +1 and the parent is stored at floor(K/2) index.

2. Linked List Representation of Binary Tree

We use a doubly linked list to represent a binary tree.
In a doubly linked list, every node consists of three fields.
First field for storing left child address, second for storing
actual data and third for storing right child address.

CRACK CS IT WITH DIVYA 121

Properties of a Binary Tree

✓ Max nodes at level L: 2^L (root at level 0) or 2^(L-1) (root at level 1).
✓ Max nodes in height h: 2^(h+1) - 1 (or 2^h - 1 if root at height 1).
✓ Min nodes in height h: h + 1.
✓ Max height with n nodes: n - 1.
✓ Min height with n nodes: ⌈log₂(n+1)⌉ - 1.
✓ Nodes & edges relation: n = e + 1 (or e = n - 1).
✓ The total number of trees possible with n nodes is: 2n-n

CRACK CS IT WITH DIVYA 122

In a binary tree , the parent node of a node in
position 10 will be in the position ……
A: 5
B: 6
C: 20
D: 21

CRACK CS IT WITH DIVYA 123

In a binary tree , the parent node of a node in
position 10 will be in the position ……
A: 5
B: 6
C: 20
D: 21

CRACK CS IT WITH DIVYA 124

A binary tree with 20 nodes has-----null
branches.

A: 21
B: 19
C: 17
D: 10

CRACK CS IT WITH DIVYA 125

A binary tree with 20 nodes has-----null
branches.

A: 21
B: 19 In any binary tree, the number of null
C: 17 branches (or NULL pointers) is always:
Null branches=Number of nodes+1
D: 10

CRACK CS IT WITH DIVYA 126

Types of Binary Tree based on the number of
children:
Following are the types of Binary Tree based on
the number of children:
1.Full Binary Tree
2.Degenerate Binary Tree
3.Skewed Binary Trees

CRACK CS IT WITH DIVYA 127

1. Full Binary Tree

A full Binary tree is a special type of binary tree in

which every parent node/internal node has either two
or no children. It is also known as a proper binary tree.

PIC COURTESY:
Geeksforgeeks

Number of Leaf nodes =Number

of Internal nodes +1
A strictly binary tree with n leaf
nodes always has 2n-1 nodes

CRACK CS IT WITH DIVYA 128

2. Degenerate (or pathological) tree

A Tree where every internal node has one child. Such trees are
performance-wise same as linked list. A degenerate or pathological
tree is a tree having a single child either left or right.

PIC COURTESY:
Geeksforgeeks

CRACK CS IT WITH DIVYA 129

3. Skewed Binary Tree
A skewed binary tree is a pathological/degenerate tree in which
the tree is either dominated by the left nodes or the right nodes.
Thus, there are two types of skewed binary tree: left-skewed
binary tree and right-skewed binary tree.
PIC COURTESY:
Geeksforgeeks

CRACK CS IT WITH DIVYA 130

Types of Binary Tree On the basis of the
completion of levels:
1.Complete Binary Tree

2.Perfect Binary Tree

3.Balanced Binary Tree

CRACK CS IT WITH DIVYA 131

1. Complete Binary Tree
A Binary Tree is a Complete Binary Tree if all the levels
are completely filled except possibly the last level and
the last level has all keys as left as possible.
Eg: BinaryHeap

PIC COURTESY:
Geeksforgeeks

CRACK CS IT WITH DIVYA 132

2. Perfect Binary Tree
A Binary tree is a Perfect Binary Tree in which all
the internal nodes have two children and all leaf
nodes are at the same level.
PIC COURTESY:
Geeksforgeeks

In a Perfect Binary Tree, the

number of leaf nodes is the
number of internal nodes plus 1

L = I + 1 Where L = Number of
leaf nodes, I = Number of
internal nodes.

CRACK CS IT WITH DIVYA 133

CRACK CS IT WITH DIVYA 134
 3.Balanced Binary Tree

● Binarytree is calledBalanced Binary Tree, if difference of left

and right subtree height is maximum one for all the nodes.

● Eg; B tree, B+tree, AVLTreeandRed-Black Tree

● Search,insertanddeleteoperationscost O(logn)time.

CRACK CS IT WITH DIVYA 135

Extended Binary Tree
● All the null sub tree of the original tree are replaced withspecial nodes called
external nodes whereas other nodes are called internal nodes .

31
Expression Tree
● Each internal node corresponds to the operator and each leaf node
corresponds to the operand
Eg: 3 +((5+9)*2)

32
BINARY SEARCH TREE (BST)
it is also called as “Ordered Binary Tree”. Ithas the following properties:

● The left subtree of a node has nodes which are only lesser thanthat node’s key.
● The right subtree of a node has nodes which are only greaterthan that
node’s key.
● Each node has distinct keys and duplicates are not allowed inBinary Search
Tree.
● The left and right subtree must also be a binary search tree.
● These are sorted binary trees, they are used for fast and efficientbinary
search, insertion and deletion.

3
 PIC COURTESY:
Geeksforgeeks

CRACK CS IT WITH DIVYA 139

A complete binary tree with 12 leaf nodes:
(A) cannot have more than 23 nodes
(B) has exactly 23 nodes
(C) cannot have more than 21 nodes
(D) has exactly 21 nodes

CRACK CS IT WITH DIVYA 140

A complete binary tree with 12 leaf nodes:
(A) cannot have more than 23 nodes
(B) has exactly 23 nodes
(C) cannot have more than 21 nodes
(D) has exactly 21 nodes

2n-1(even)/2n(odd)]

CRACK CS IT WITH DIVYA 141

Ina full binary tree if there are L leaves, then
total number of nodes N are?
a) N =2*L
b) N =L +1
c) N =L – 1
d) N =2*L – 1

CRACK CS IT WITH DIVYA 142

Ina full binary tree if there are L leaves, then
total number of nodes N are?
a) N =2*L
b) N =L +1
c) N =L – 1
d) N =2*L – 1

CRACK CS IT WITH DIVYA 143

A strictly binary tree with 10 leaves……

a. Cannot have more than 19 nodes

b. Has exactly 19 nodes
c. has exactly 17 nodes
d. Cannot have more than 19 nodes

CRACK CS IT WITH DIVYA 144

A strictly binary tree with 10 leaves……

a. Cannot have more than 19 nodes

b. Has exactly 19 nodes
c. has exactly 17 nodes
d. Cannot have more than 19 nodes

Ans: option b [hint: 2n-1]

CRACK CS IT WITH DIVYA 145

 Tree Traversal
Tree Traversal refers to the process of visiting or accessing
each node of the tree exactly once in a certain order.

Types of Binary Tree Traversals

1. Depth first Traversals
❖ Preorder
❖ Inorder
❖ Postorder
2. Breadth first Traversal

CRACK CS IT WITH DIVYA 146

CRACK CS IT WITH DIVYA 147
 DEPTH FIRST TRAVERSAL
•In post-order traversal, the steps are:
• Traverse the left subtree.
• Traverse the right subtree.
• Visit the root.
Application: to get postfix expression of an expression tree
•In pre-order traversal, the steps are:
• Visit the root.
• Traverse the left subtree.
• Traverse the right subtree.
Application: to get prefix expression of an expression tree

•In in-order traversal, the steps are:

• Traverse the left subtree.
• Visit the root.
• Traverse the right subtree.
Application: to get infix expression of an expression tree

148
CRACK CS IT WITH DIVYA 149
The inorder successor of node 25 in the given
tree is

a. 31
b. 44
c. 50
d. 25
The inorder successor of node 25 in the given
tree is

a. 31
b. 44
c. 50
d. 25
What is common in three different types of traversals
(Inorder,Preorder and Postorder)?

A. root is visited after left subtree

B. root is visited before right subtree

C.left subtree is always visited before right subtree

D.none

CRACK CS IT WITH DIVYA 152

What is common in three different types of traversals
(Inorder,Preorder and Postorder)?

A. root is visited after left subtree

B. root is visited before right subtree

C.left subtree is always visited before right subtree

D.none

CRACK CS IT WITH DIVYA 153

Binary Search Tree (BST)
BSTs are binary trees specially organized for efficient searching.
Properties of BST:
1.Each node contains one key (data).
2.Keys in the left subtree are less than the key in its parent node —
L < P.
3.Keys in the right subtree are greater than the key in its parent
node — P < R.
4.Left and right subtrees of the root are also BSTs.
5.Duplicate keys are not allowed.
Also called Ordered Binary Tree or Sorted Binary Tree.

CRACK CS IT WITH DIVYA 154

CRACK CS IT WITH DIVYA 155
 Insertion in BST

● While doing insertion in BST, the new key is

always inserted in leaf.
● We start searching a key from root till we
hit a leaf node.
● Once a leaf node is found, the new node is
added as a child of the leaf node.

CRACK CS IT WITH DIVYA 156

Construction of BST

● Create the binary search tree using the following data elements.

43, 10, 79, 90, 12, 54, 11, 9, 50

eg:43, 10, 79, 90, 12, 54, 11, 9, 50
Eg: 43, 10, 79, 90, 12, 54, 11, 9, 50
The pre-order traversal of a binary search tree is
given by:

11, 7, 5, 1, 6, 8, 9, 15, 14, 18, 16, 19

Then the post-order traversal of this tree is:

A)1, 5, 6, 7, 8, 9, 11, 14, 15, 16, 18, 19

B) 1, 6, 5, 9, 8, 7, 14, 16, 19, 18, 15, 11
C) 6, 3, 5, 7, 8, 9, 19, 16, 18, 14, 15, 11
D) 6, 5, 1, 9, 8, 7, 14, 15, 16, 19, 18, 11

CRACK CS IT WITH DIVYA 160

11, 7, 5, 1, 6, 8, 9, 15, 14, 18, 16, 19

CRACK CS IT WITH DIVYA 161

Suppose we have to insert following sequence of keys into an
empty BST. 5,7,45 ,60,50,23,15,24
What would be the height of BST?

a. 3
b. 4
c. 5
d. 6

CRACK CS IT WITH DIVYA 162

Suppose we have to insert following sequence of keys into an
empty BST. 5,7,45 ,60,50,23,15,24
What would be the height of BST?

a. 3
b. 4
c. 5
d. 6

CRACK CS IT WITH DIVYA 163

What is the worst case time complexity for search, insert and
delete operations in a Binary Search Tree?

(A) O(n)for all

(B) O(Logn) for all
(C) O(Logn) for search and insert, and O(n)for delete
(D) O(Logn) for search, and O(n)for insert and delete

CRACK CS IT WITH DIVYA 164

What is the worst case time complexity for search, insert and
delete operations in a Binary Search Tree?

(A) O(n)for all

(B) O(Logn) for all
(C) O(Logn) for search and insert, and O(n)for delete
(D) O(Logn) for search, and O(n)for insert and delete

CRACK CS IT WITH DIVYA 165

● Threaded Binary Tree (TBT)
○ Single threaded
■ Left threaded
■ Right threaded
○ Fully (Double) threaded

CRACK CS IT WITH DIVYA 166

WhyThreaded Binary trees ?
● A binary tree can be represented by using array or linked list.
● Ina linked list representation, left child of a node is pointed by
left pointer and right child of a node is pointed by right pointer.
● A node with no child uses NULL pointers.
● There is a lot of memory space wastage by this NULL pointers

● Ingeneral,for anybinarytreewithnnodes, therewil be n+1 null

pointersand2ntotal pointers.

CRACK CS IT WITH DIVYA 167

● The NULL entries in a binary trees are
replaced by special pointers ,called
threads, and the binary tree having such
pointers is called a threaded binary tree.

● Threads in a binary tree are represented by

a dotted line.

CRACK CS IT WITH DIVYA 168

Binary tree and its linked list representation
What is a threaded binary tree traversal?

a) a binary tree traversal using stacks

b) a binary tree traversal using queues
c) a binary tree traversal using stacks and
queues
d) a binary tree traversal without using
stacks and queues

CRACK CS IT WITH DIVYA 170

What is a threaded binary tree traversal?

a) a binary tree traversal using stacks

b) a binary tree traversal using queues
c) a binary tree traversal using stacks and
queues
d) a binary tree traversal without using
stacks and queues

CRACK CS IT WITH DIVYA 171

AVL Tree
•A height-balanced binary search tree.
•Balance Factor = height(left subtree) − height(right
subtree).
•Tree is balanced if balance factor of every node is
-1, 0, or 1; otherwise, it is unbalanced.

CRACK CS IT WITH DIVYA 172

AVL Rotations
● We perform rotation in AVL tree only in case if Balance Factor is other
than -1, 0, and 1.
● There are basically four types of rotations which are as follows:
1. R R case (Left Rotation)
2. L L case (Right Rotation)
3. L R case (Left Right rotation)
4. R L case (Right Left rotation)

● Rotation is the process of moving nodes either to left or to right to

make the tree balanced.
Time complexity of searching, insertion and
deletion operation in an AVL tree is………….
A: O(n)
B: O(n log n)
C: O(log n)
D: O(1)

CRACK CS IT WITH DIVYA 174

Time complexity of searching, insertion and
deletion operation in an AVL tree is………….
A: O(n)
B: O(n log n)
C: O(log n)
D: O(1)

CRACK CS IT WITH DIVYA 175

Which of the following is not a self
balancing binary search tree?

a. AVL tree

b. Red Black tree

c. Splay tree

d. 2-3-4 tree

CRACK CS IT WITH DIVYA 176

Which of the following is not a self
balancing binary search tree?

a. AVL tree

b. Red Black tree

c. Splay tree

d. 2-3-4 tree

CRACK CS IT WITH DIVYA 177

 FOREST

➢ A "Forest" refers to a collection of one or more disjoint trees.

➢ In graph theory, a forest is a set of trees that do not have
any edges connecting them. Each tree within the forest is a separate,
connected, acyclic graph.

CRACK CS IT WITH DIVYA 178

 FOREST DEFINITION:

The collection of zero or more trees is called Forest.

A forest is a set of n ≥ 0 disjoint trees.
The concept of a forest is very close to that of a tree because
if we remove the root of a tree, we obtain a forest.
For example, removing the root of any binary tree produces a forest of
two trees.

CRACK CS IT WITH DIVYA 179

Key characteristics of a Forest are −
Disjoint Trees: Each tree in a forest is separate from the
others; there are no edges connecting vertices in different
trees.
Acyclic: Like trees, each tree in a forest does not contain
any cycles, meaning there is no closed loop of edges.
Collection of Trees: A forest can have one or more trees. A
single tree can be considered a forest by itself.

CRACK CS IT WITH DIVYA 180

GRAPH
● A Graph is a non-linear data structure.
● “A graph is a data structure (V,E) that consists of
➢ a collection of vertices V and
➢ a collection of edges E, represented as ordered pairs of
vertices (u,v).”

CRACK CS IT WITH DIVYA 181

GRAPH cont..
Adjacent, neighbors

● Two vertices are adjacent and are neighbors if they are

the endpoints of an edge
Degree(size):
Number of edges incident on a node
Order of the graph =The number of vertices in the graph.

Size of the graph =The number of edges in the graph.

CRACK CS IT WITH DIVYA 182

CRACK CS IT WITH DIVYA 183
Degree (Directed Graphs)
● Indegree: Number of edges entering a node

● Out degree: Number of edges leaving a node

● Degree =Indegree+ Outdegree

Pic courtesy:
geeksforgeeks

CRACK CS IT WITH DIVYA 184

•Successor & Predecessor (Digraph):
If node u is adjacent to node v, then u is the predecessor of v,
and v is the successor of u.

•Source node and sink node(digraph)

In a Directed acyclic graph, a source node is a node (also known as a
vertex) with no incoming connections from other nodes, while a sink
node is a node without outgoing connections.

CRACK CS IT WITH DIVYA 185

● Pendant Vertex- pendant vertices are the vertices that have degree 1,
also called pendant vertex.
● Isolated node—In graph, when a node is not connected with any other node
then it is called isolated node.

CRACK CS IT WITH DIVYA 186

Path −Path represents a sequence of edges between two
vertices.
Cycle-A path from a vertex to itself is called a cycle.
A graph is called cyclic if it contains a cycle; otherwise it is
called acyclic.

CRACK CS IT WITH DIVYA 187

Multiple edges/ Parallel Edges:
● Iftwo vertices are connected with
more than one edge then such edges are
called parallel edges
● Eg: e1,e4 Loop:
● An edge of a graph which join a
vertex to itself is called loop or a self-loop.
● A loop at a vertex gives degree 2 to
that vertex.
● Eg: e7

CRACK CS IT WITH DIVYA 188

Types of graph
Simple Graph
● A graph G=(V, E) is said to be a simple graph if there is
one and only one edge between each pair of vertices.
● Ie, there is no multiple edges and no loops.

CRACK CS IT WITH DIVYA 189

Types of graph
Multi Graph
● A graph g=(V,E)is said to be a multigraph if there are multipleedges
between a pair of vertices in the graph.
● A Multigraph does not contain any self-loop.

CRACK CS IT WITH DIVYA 190

Types of graph
Pseudo Graph
● A graph G with a self loop and some multiple edges is
called pseudo graph.

CRACK CS IT WITH DIVYA 191

Types of graph
Null graph, TrivialGraph
● A graph G=(V,E)where E=0is said to be Null or Empty graph.
● A graph withOne vertex and no edge is called as a trivial graph.

Null
graph
Trivial
graph

CRACK CS IT WITH DIVYA 192

Types of graph
Digraph (Directed Graph)
● For each edge e between (Vi, Vj), an arrow exists to denote
its direction.
● (Vi, Vj)is a pair of vertices which is different from (Vj,Vi) in
case of digraph.
● e1=(V2, V1)
● e2 =(V3, V2)
● e4 =(V2,V4)

CRACK CS IT WITH DIVYA 193

 Types of graph
Undirected Graph

● A graph in which all the edges are undirected is called as a

undirected graph.

CRACK CS IT WITH DIVYA 194

 Types of graph
Connected Graph-
● In connected graph, at least one path exists between every
pair of vertices.

CRACK CS IT WITH DIVYA 195

 Types of graph
Disconnected Graph-

● A graph in which there does not exist any path between at

least one pair of vertices is called as a disconnected
graph.

CRACK CS IT WITH DIVYA 196

 Types of graph
Cyclic Graph
● A directed graph with cycle is said to be a cyclic graph.
● i.e. if V1, V2, and V3 are vertices in the graph then, there
always exist edges connecting (V1, V2) and (V2, V3) and (V3,
V1).
● Eg:{B,C,E,D,B} is a cycle

CRACK CS IT WITH DIVYA 197

 Types of graph
Directed Acyclic Graph
● It’s also known as DAG, these are the graphs with directed
edges, but they do not contain any cycle.

CRACK CS IT WITH DIVYA 198

Difference Between Graph and Tree
Feature Graph Tree
Collection of Hierarchical
vertices and edges structure with a
Definition
(can connect in any root node and
way). edges.
No cycles; always
Can have cycles
connected with one
Structure and be
unique path
disconnected.
between nodes.
Has one root node
Root Node No root node.
(no parent).
Any number of For n nodes →
Edges
edges. exactly n–1 edges.
Social networks, File systems, org
Applications
maps, networks. charts, XML, DOM.

CRACK CS IT WITH DIVYA 199

 Star graph
• Complete bipartite graph
• N-1 vertices have degree 1 and one vertex have degree n-1
A set of n ≥ 0 disjoint trees:
(A) Tree
(B) Forest
(C) B Tree
(D) All of the above

CRACK CS IT WITH DIVYA 201

A set of n ≥ 0 disjoint trees:
(A) Tree
(B) Forest
(C) B Tree
(D) All of the above

CRACK CS IT WITH DIVYA 202

Eulerian Path
•Passes through every edge of a connected
graph exactly once.
•May start and end at different vertices.
Eulerian Circuit Eulerian path ≠
•Eulerian path that starts and ends at the necessarily an Eulerian
same vertex. circuit.
•Passes through every edge exactly once,
visiting every vertex at least once. An undirected graph is Euilerian iff
Eulerian Graph degrees of all nodes is twice the no:
•A graph that contains an Eulerian circuit. of edges, and all vertices are even
degree.

CRACK CS IT WITH DIVYA 203

Complete Graph
•Simple graph where each vertex has
degree n−1.
•Exactly one edge between every pair of
vertices.
•Also called a full graph.
•Edges: n(n-1)/2 edges.

CRACK CS IT WITH DIVYA 204

Regular Graph
•Simple graph where all vertices have the
same degree (d).
•All complete graphs are regular, but not all
regular graphs are complete.
•Edges: (N*d)/2

CRACK CS IT WITH DIVYA 205

Bipartite Graph
•Vertices divided into two disjoint sets XXX and
YYY.
•Edges connect only between XXX and YYY.
•No edges between vertices of the same set.

PIC Courtesy:
Geekforgeeks

CRACK CS IT WITH DIVYA 206

Planar Graph
A graph is said to be planar if it can be
drawn in a plane so that no edge cross.

PIC Courtesy:
A complete graph Kn is a planar if and only if n<5. Geekforgeeks

Euler's Formula: For any

connected planar graph, the
relationship between the number
of:
Vertices (V)
Edges (E)
Faces (F) is given by :
V−E+F=2

CRACK CS IT WITH DIVYA 207

A connected planar graph having 6 vertices,
7 edges contains regions.
A: 15
B: 11
C:3
D:1

CRACK CS IT WITH DIVYA 208

A connected planar graph having 6 vertices,
7 edges contains regions.
A: 15
B: 11
C:3
D:1

CRACK CS IT WITH DIVYA 209

In cyclomatic complexity, if E is the number
of edges and N is the number of nodes, V(G)
for a flow graph is defined as:
(A) E – N + 2
(B) E – N – 1
(C) E + N – 2
(D) E + N – 1

CRACK CS IT WITH DIVYA 210

In cyclomatic complexity, if E is the number
of edges and N is the number of nodes, V(G)
for a flow graph is defined as:
(A) E – N + 2
(B) E – N – 1
(C) E + N – 2
(D) E + N – 1

CRACK CS IT WITH DIVYA 211

 ● 3 ways for representing graphs:
1. –Adjacency matrix
2. –Adjacency list
3. --Incidence matrix

Adjacency list Adjacency metrtx

Space saved for sparse No space saved
graph
DFS and BFS in O(v+E) DFS and BFS in O(V²)
Adding vertex is easy Not

CRACK CS IT WITH DIVYA 212

Sparse matrices have
A. Many non zero entries
B. Many Zero entries
C. Higher dimension
D. None of the above

CRACK CS IT WITH DIVYA 213

Sparse matrices have
A. Many non zero entries
B. Many Zero entries
C. Higher dimension
D. None of the above

CRACK CS IT WITH DIVYA 214

Which of the following ways can be used to
represent a graph?

A. Adjacency List and Adjacency

Matrix
B. Incidence Matrix
C.Adjacency List, Adjacency Matrix
as well as Incidence Matrix
D. None

CRACK CS IT WITH DIVYA 215

Which of the following ways can be used to
represent a graph?

A. Adjacency List and Adjacency

Matrix
B. Incidence Matrix
C.Adjacency List, Adjacency Matrix
as well as Incidence Matrix
D. None

CRACK CS IT WITH DIVYA 216

 ● Two traversals of a graph are
a. Breadth-first search (BFS)
b. Depth-first search (DFS)

BFS (Breadth First Search):

•Traverses graph level by level from the first node, visiting all
neighbors.
•Ensures each node is processed only once.
•Time Complexity: O(V + E) where V = vertices, E = edges.
● After BFS/DFS we get a spanning tree.
● A spanning tree is a connected subgraph of a graph G which
contains all the
vertices of G.

CRACK CS IT WITH DIVYA 217

DFS (Depth First Search):
•Explores as deep as possible from the start node before
backtracking.
•Backtracks to explore unvisited nodes after hitting a dead end.
•Time Complexity: O(V + E) where V = vertices, E = edges.

CRACK CS IT WITH DIVYA 218

The Breadth First Search algorithm has been implemented using the
queue data structure. One possible order of visiting the nodes of the
following graph is

A. MNOPQR
B. NQMPOR
C. QMNPOR
D. QMNPRO

CRACK CS IT WITH DIVYA 219

The Breadth First Search algorithm has been implemented using the
queue data structure. One possible order of visiting the nodes of the
following graph is

A. MNOPQR
B. NQMPOR
C. QMNPOR
D. QMNPRO

CRACK CS IT WITH DIVYA 220

Among the following sequences:
P: a b e g h f
Q: a b f g h e
R: a b f h g e
S: a f g h b e
Which are depth first traversals of the above
graph?
A) P, Q, R and S
B) P and R only
C) Q, R and S only
D) P, R and S only

CRACK CS IT WITH DIVYA 221

Among the following sequences:
P: a b e g h f
Q: a b f g h e
R: a b f h g e
S: a f g h b e
Which are depth first traversals of the above
graph?
A) P, Q, R and S
B) P and R only
C) Q, R and S only
D) P, R and S only

CRACK CS IT WITH DIVYA 222

Sorting Algorithms

CRACK CS IT WITH DIVYA 223

1. Comparison-Based Sorting 2. Non-Comparison-Based
Algorithms Sorting Algorithms
•Simple: Counting Sort
• Selection Sort Radix Sort
• Bubble Sort Bucket Sort
• Insertion Sort TimSort (hybrid – also uses
•Efficient / Advanced: comparison internally)
• Merge Sort Comb Sort
• Quick Sort Pigeonhole Sort
• Heap Sort
• Cycle Sort 3. Hybrid Sorting
• 3-way Merge Sort Algorithms
IntroSort (Quick Sort +
Heap Sort + Insertion Sort)
TimSort (Merge Sort +
Insertion Sort)

CRACK CS IT WITH DIVYA 224

A Sorting Algorithm is used to rearrange a given array or list of elements in an order. It
can be categorized based on their memory usage (in-place vs. out-of-place) and their
preservation of relative order for equal elements (stable vs. unstable).

Memory usage:
In-place – rearranges elements within the same memory space.
Eg: Bubble sort, Selection Sort, Insertion Sort, Heapsort.
Not in -place – uses extra memory to store the sorted data.
Eg: Merge Sort
Note that merge sort requires O(n) extra space.

CRACK CS IT WITH DIVYA 225

Stable Algorithm

• Stable – preserves the relative order of equal elements.

• Example: Bubble Sort, Insertion Sort, Merge Sort, Count Sort

• Unstable – may change the relative order of equal elements.

• Quick Sort, Heap Sort ,selection sort

CRACK CS IT WITH DIVYA 226

Bubble Sort
•Idea: Repeatedly swap adjacent elements if they are in the wrong order.
•Working:
1.Traverse the array from left, compare adjacent elements.
2.Swap if needed; largest element moves to the end in each pass.
3.Repeat for remaining elements.
Passes: n – 1
Comparisons: n*(n - 1)/2
Time Complexity: O(n²)
(avg & worst)Space Complexity: O(1)
Type: Stable, in-place, comparison-based

CRACK CS IT WITH DIVYA 227

CRACK CS IT WITH DIVYA 228
Bubble sort cont..
Advantages:
•No extra memory required
•Stable sorting
Disadvantages:
•Very slow for large datasets (O(n²))

CRACK CS IT WITH DIVYA 229

INSERTION SORT
•Idea: Works like sorting playing cards in your hand.
•Working:
1.Split array into sorted and unsorted parts.
2.Pick elements from unsorted part (key) and insert into correct
position in sorted part.
3.Shift larger elements right to make space.
•Time Complexity:
•Best: O(n) (already sorted)
•Average/Worst: O(n²)
•Space Complexity: O(1)
•Type: In-place, stable, adaptive
CRACK CS IT WITH DIVYA 230
CRACK CS IT WITH DIVYA 231
INSERTION SORT cont..

Characteristics:
Simple to implement
Efficient for small datasets
Performs well on partially sorted data

CRACK CS IT WITH DIVYA 232

Selection Sort
•Idea: Repeatedly select the smallest (or largest) element from the
unsorted part and move it to the sorted part.
•Working:
1.Divide array into sorted and unsorted parts.
2.Find the smallest element in unsorted part.
3.Swap it with the first element of the unsorted part.
4.Repeat until array is sorted.
•Passes: n - 1
•Comparisons: n*(n - 1)/2
•Time Complexity: O(n²) (best, average, worst)
•Space Complexity: O(1) (in-place)
CRACK CS IT WITH DIVYA 233
SELECTION SORT cont..
•Type: Unstable, comparison-based
•Swaps:<=O(n)->good when writes are costly

•Advantages:
•Simple, works well for small datasets
•Disadvantages:
•Very slow for large datasets (O(n²))
•Not stable (may change relative order of equal elements)

CRACK CS IT WITH DIVYA 234

SELECTION SORT WORKING..

x: 4 12 -5 6 151 21 -18 45
x: -18 -5 4 6 12 21 151 45
x: -18 12 -5 6 151 21 4 45
x: -18 -5 4 6 12 21 151 45
x: -18 -5 12 6 151 21 4 45
x: -18 -5 4 6 12 21 45 151
x: -18 -5 4 6 151 21 12 45
x: -18 -5 4 6 12 21 45 151
x: -18 -5 4 6 151 21 12 45
QUICK SORT
Approach: Divide-and-conquer
Idea:
Choose a pivot (commonly first, last, or median-of-three
element).
Partition array:
Elements ≤ pivot → left
Elements > pivot → right
Recursively apply Quick Sort to left and right subarrays.
Key Process: Partition() — places pivot in correct position
and rearranges elements accordingly.

CRACK CS IT WITH DIVYA 236

 QUICK SORT cont..
Time Complexity:
Best: Ω(n log n) → pivot divides array into equal halves
Average: Θ(n log n) → generally fast in practice
Worst: O(n²) → occurs when pivot choice causes highly unbalanced
partitions (e.g., already sorted array with poor pivot choice)
Space Complexity:O(1) auxiliary (excluding recursion stack)
Recursion stack worst-case: O(n)

CRACK CS IT WITH DIVYA 237

QUICK SORT cont..
Advantages:
Very efficient for large datasets
Low memory overhead (in-place sorting)
Divide-and-conquer structure is simple to implement
Disadvantages:
Worst-case O(n²) if pivot is poorly chosen
Not stable (equal elements may lose original order)
Less efficient for small datasets

CRACK CS IT WITH DIVYA 238

MERGE SORT
Approach: Divide-and-conquer
Idea:
Divide the array into two halves.
Recursively sort each half.
Merge the sorted halves into a single sorted array.
Key Process: Merge() — combines two sorted subarrays into
one sorted array.

CRACK CS IT WITH DIVYA 239

MERGE SORT cont..
Time Complexity:
Best: Ω(n log n)
Average: Θ(n log n)
Worst: O(n log n) → always balanced splits
Space Complexity:
O(n) auxiliary → needs extra space for merging
Advantages:
Guaranteed O(n log n) performance
Stable (preserves order of equal elements)
Works well for large datasets and linked lists
Disadvantages:
Requires extra memory (O(n))
Slower for small datasets compared to algorithms like Insertion Sort

CRACK CS IT WITH DIVYA 240

MERGE SORT cont..
Initial array Acontains 14 elements:
• 67, 33, 40, 22, 55, 88, 60, 11, 80, 20, 50, 44, 77, 30
Pass 1 :: Mergeeachpair of elements
• (33, 67) (22, 40) (55, 88) (11, 60) (20, 80) (44, 50) (30, 70)
Pass 2 :: Mergeeachpair of pairs
• (22, 33, 40, 67) (11, 55, 60, 88) (20, 44, 50, 80) (30, 77)
Pass 3 :: Mergeeachpair of sorted quadruplets
• (11, 22, 33, 40, 55, 60, 67, 88) (20, 30, 44, 50, 77, 80)
Pass 4 :: Mergethe twosortedsubarrays to get the final list
• (11, 20, 22, 30, 33, 40, 44, 50, 55, 60, 67, 77, 80, 88)

CRACK CS IT WITH DIVYA 241

Sorting Algorithms at a Glance
Insertion Sort
Best for already sorted or partially sorted arrays.
Most suited when first part is sorted, rest random.
Best case: O(n) (sorted), Worst: O(n²) (reverse sorted).
Basis for Shell Sort.
Quick Sort
Worst case: O(n²) when array is already sorted or reverse
sorted.
Very fast for large datasets in average cases.

CRACK CS IT WITH DIVYA 242

Sorting Algorithms at a Glance
Bubble Sort
Best case: O(n) (sorted), Worst: O(n²) (reverse sorted).
Good for partially sorted arrays.
Merge Sort
Performance independent of initial order.
Not adaptive, O(n log n) always.
Used in external sorting.
Better than Quick Sort for linked lists (no extra space).
Extras
Binary Insertion Sort is used in Binary Search-based insertion.
Stack is best to implement Quick Sort and Tower of Hanoi.

CRACK CS IT WITH DIVYA 243

Sorting algorithms at a glance
Fewer Comparisons
Insertion Sort
Merge-Insertion Sort
Fewer Assignments (Swaps)
Selection Sort
Large Number of Comparisons
Selection Sort
Bubble Sort

CRACK CS IT WITH DIVYA 244

A sorting technique is called stable if:
(A) It takes O(n log n) time
(B) It maintains the relative order of occurrence
of non-distinct elements
(C) It uses divide and conquer paradigm
(D) It takes O(n) space

CRACK CS IT WITH DIVYA 245

A sorting technique is called stable if:
(A) It takes O(n log n) time
(B) It maintains the relative order of occurrence
of non-distinct elements
(C) It uses divide and conquer paradigm
(D) It takes O(n) space

CRACK CS IT WITH DIVYA 246

Which sorting algorithm is best when list is
already sorted?
A: Insertion Sort
B: Selection Sort
C: Merge Sort
D: Quick Sort

CRACK CS IT WITH DIVYA 247

Which sorting algorithm is best when list is
already sorted?
A: Insertion Sort
B: Selection Sort
C: Merge Sort
D: Quick Sort

CRACK CS IT WITH DIVYA 248

Sorting is :

a) a process of re-arranging a given set of

objects in a specific order

b) to facilitate the later search for

members of the sorted set

c) is a relevant and essential activity,

particularly in data processing

d) All of these

CRACK CS IT WITH DIVYA 249

Sorting is :

a) a process of re-arranging a given set of

objects in a specific order

b) to facilitate the later search for

members of the sorted set

c) is a relevant and essential activity,

particularly in data processing

d) All of these

CRACK CS IT WITH DIVYA 250

The average number of comparisons in selection
sort and insertion sort are respectively
a) n(n-1)/2 and n(n-1)/4
b) n(n-1)/4 and n(n-1)/2
c) n(n-1)/2 and n(n-1)/2
d) n(n-1)/4 and n(n-1)/4

CRACK CS IT WITH DIVYA 251

The average number of comparisons in selection
sort and insertion sort are respectively
a) n(n-1)/2 and n(n-1)/4 Algorithm Average No: of
comparisons
b) n(n-1)/4 and n(n-1)/2 Insertion n(n-1)/4
c) n(n-1)/2 and n(n-1)/2 sort
Bubble sort n(n-1)/2
d) n(n-1)/4 and n(n-1)/4 Selection n(n-1)/2
sort
Merge sort m+n-1

CRACK CS IT WITH DIVYA 252

The complexity of Binary search algorithm is :

a) O(n)

b) O(log n)

c) O(n/2)

d) O(n log n)

CRACK CS IT WITH DIVYA 253

The complexity of Binary search algorithm is :

a) O(n)

b) O(log n)

c) O(n/2)

d) O(n log n)
• Binary Search
• Search on sorted tree
• Uses divide and conquer concept

CRACK CS IT WITH DIVYA 254

Binary search algorithm cannot be applied
to :

a) Sorted linked list

b) Sorted binary trees

c) Sorted linear array

d) Pointer array

CRACK CS IT WITH DIVYA 255

Binary search algorithm cannot be applied
to :

a) Sorted linked list

b) Sorted binary trees

c) Sorted linear array

d) Pointer array

CRACK CS IT WITH DIVYA 256

Searching ALGORITHMS

CRACK CS IT WITH DIVYA 257

• Searching
• Linear search:If the array elements are unsorted.

• Binary search:If the array elements are sorted.

CRACK CS IT WITH DIVYA 258

Linear Search
Basic Idea
Start at the beginning of the array.
Inspect elements one by one to see if they match the key.
Time Complexity (n = number of elements in the array)
Best Case: Match found in the first element → 1 operation → O(1)
Worst Case: No match found, or match found in the last element → n
operations → O(n)
Average Case: (n + 1) / 2 operations → O(n)

CRACK CS IT WITH DIVYA 259

Binary Search
Basic Idea
❖ Works on a sorted array.
▪ Compare the key with the middle element.
▪ If the key matches the middle element → search ends.
▪ If the key is smaller → search in the left half.
▪ If the key is larger → search in the right half.
Repeat until the key is found or the subarray size becomes zero.
Time Complexity (n = number of elements in the array)
Best Case: Match found in the first comparison → 1 operation → O(1)
Worst Case & Average cse: Search space reduces by half each time → log₂n
operations → O(log n)
CRACK CS IT WITH DIVYA 260
Algorithm Best case Average Case Worst Case

Selection Sort O(n²) O(n²) O(n²)

Bubble Sort O(n) O(n²) O(n²)
Heap Sort O(n log n) O(n log n) O(n log n)
Quick Sort O(n log n) O(n log n) O(n²)
Merge Sort O(n log n) O(n log n) O(n log n)
Bucket Sort O(n + k) O(n + k) O(n²)
Count Sort O(n + k) O(n + k) O(n + k)
Radix Sort O(nk) O(nk) O(nk)
Insertion Sort O(n) O(n2) O(n2)

CRACK CS IT WITH DIVYA 261

 Algorithm
A finite sequence of clear, unambiguous steps to solve a
problem in finite time.
Properties of a Good Algorithm
Input: Zero or more externally supplied quantities.
Output: At least one result produced.
Definiteness: Instructions must be clear and precise.
Finiteness: Must terminate after a finite number of steps.
Effectiveness: Steps should be simple, feasible, and
executable by hand.

CRACK CS IT WITH DIVYA 262

Pseudocode
A way to represent an algorithm using a mix of programming language
constructs and informal English statements.
Complexity of Algorithms
The function f(n) that expresses an algorithm’s running time or storage
needs in terms of input size n.
The time complexity of a program is the amount of computer time it needs to
run to completion.
The space complexity of a program is the amount of memory it needs to run
to completion.

CRACK CS IT WITH DIVYA 263

Cases of Complexity Function f(n)
•Best Case: Minimum possible value of f(n).
•Average Case: Expected value of f(n).
•Worst Case: Maximum possible value of f(n).

•ASYMPTOTIC NOTATIONS
•Big-O (O): Upper bound on growth rate.
•Big-Omega (Ω): Lower bound on growth rate.
•Big-Theta (Θ): Tight bound (both upper and lower).
•Little-o (o): Strictly less than an upper bound.
•Little-omega (ω): Strictly greater than a lower bound.

CRACK CS IT WITH DIVYA 264

f(n): is the exact function that describes your algorithm’s running
time or memory usage.
g(n): is a simpler “comparison function” that represents the growth
rate
•Analogy between comparisons of functions a=f(n) and b=g(n)
and comparison of real numbers a and b:

f(n) = O(g(n)) is like a ≤b

f(n) = Ω(g(n)) is like a ≥b
f(n) = Θ(g(n)) is like a =b
f(n) =o(g(n)) is like a <b
f(n) = ω(g(n)) is like a >b

CRACK CS IT WITH DIVYA 265

CRACK CS IT WITH DIVYA 266
Property
Symmetric Reflexive Transitive Transpose
Notation
O(≤) ✗ O→Ω
Ω (≥) × ✓ ✓ Ω→0
θ(=) θ→θ
o(<) ✗ ✗ O→ω
ω(>) ✗ ✗ ω→O

CRACK CS IT WITH DIVYA 267

Assume that f(n) and g(n) are asymptotically positive.
Which of the following is correct?

1.f(n) = O(g(n)) and g(n) = O(h(n)) ⇒ f(n) = ω(h(n))

2.f(n) = Ω(g(n)) and g(n) = Ω(h(n)) ⇒ f(n) = O(h(n))
3.f(n) = o(g(n)) and g(n) = o(h(n)) ⇒ f(n) = o(h(n))
4.f(n) = ω(g(n)) and g(n) = ω(h(n)) ⇒ f(n) = Ω(h(n))

CRACK CS IT WITH DIVYA 268

1.f(n) = O(g(n)) and g(n) = O(h(n)) ⇒ f(n) = ω(h(n))

2.f(n) = Ω(g(n)) and g(n) = Ω(h(n)) ⇒ f(n) = O(h(n))

3.f(n) = o(g(n)) and g(n) = o(h(n)) ⇒ f(n) = o(h(n))

4.f(n) = ω(g(n)) and g(n) = ω(h(n)) ⇒ f(n) = Ω(h(n))

CRACK CS IT WITH DIVYA 269

Assume that f(n) and g(n) are asymptotically positive.
Which of the following is correct?

1.f(n) = O(g(n)) and g(n) = O(h(n)) ⇒ f(n) = ω(h(n))

2.f(n) = Ω(g(n)) and g(n) = Ω(h(n)) ⇒ f(n) = O(h(n))
3.f(n) = o(g(n)) and g(n) = o(h(n)) ⇒ f(n) = o(h(n))
4.f(n) = ω(g(n)) and g(n) = ω(h(n)) ⇒ f(n) = Ω(h(n))

CRACK CS IT WITH DIVYA 270

Which of the following asymptotic notations
is used to provide lower bound constraint?
1.×
2.Ω
3.Θ
4.O

CRACK CS IT WITH DIVYA 271

Which of the following asymptotic notations
is used to provide lower bound constraint?
1.×
2.Ω
3.Θ
4.O

CRACK CS IT WITH DIVYA 272

Analyzing Algorithms
● The most common computing times in increasing order are:

O(1)<O(log2 n)<O(√n)<O(n)< O(n.log2 n)<O(n2)< O(n3)<O(2n)<O(n! )

O(2n)>O(n10)> O(nroot(n))

CRACK CS IT WITH DIVYA 273

•Constant-time function – O(1) – Order 1
•Linear-time function – O(n) – Order n
•Logarithmic function – O(log n)
•Quadratic-time function – O(n²) – Order n squared
•Cubic-time function – O(n³)
•Exponential-time function – O(2ⁿ)
•Factorial-time function – O(n!)

CRACK CS IT WITH DIVYA 274

What is the time, and space complexity of the following code:

int a = 0, b = 0;
for (i = 0; i < N; i++) {
a = a + rand();
}
for (j = 0; j < M; j++) {
b = b + rand();
}
Options:

A: O(N * M) time, O(1) space

B: O(N + M) time, O(N + M) space
C: O(N + M) time, O(1) space
D: O(N * M) time, O(N + M) space
What is the time, and space complexity of the following code:

int a = 0, b = 0;
for (i = 0; i < N; i++) {
a = a + rand();
}
for (j = 0; j < M; j++) {
b = b + rand();
}
Options:

A: O(N * M) time, O(1) space

B: O(N + M) time, O(N + M) space
C: O(N + M) time, O(1) space
D: O(N * M) time, O(N + M) space
What is the time complexity of the
following code?

1.O(N)
2.O(N*log(N))
3.O(N * Sqrt(N))
4.O(N*N)
What is the time complexity of the
following code?

1.O(N)
2.O(N*log(N))
3.O(N * Sqrt(N))
4.O(N*N)
Recursive Function Statements
● Uses recurrence relation to find the time complexity.
● A recursive relation, T(n), is a recursive function of integer n. Every
recursive function consists of both recursive and base cases.
● The model that uses mathematical concepts to calculate the
time complexity of an algorithm is known as the recurrence
relational model.

279
RECURRENCE RELATION
● In an Analysis of Algorithm, recurrence relations are used to analyze the
running time of a recursive function.
● The running time of a recursive function can be written as a mathematical
recurrence relation which is denoted by T(n) where n is the size of the input.
● Running Time T(n) – Two Cases
1. Base Case: Time taken when n is small enough to solve directly.
2. Recursive Case: Time expressed as a recurrence relation for large n.

280
FIBONACCI SERIES- How to write a
recurrence relation //base condition T(n)=O(1)

public static int fib(int n) {

if (n <= 1) {
return 1;
}
else {
return fib(n - 1) + fib(n - 2); //T(n)=T(n−1)+T(n-2)+O(1)
}
}

281
 Time
Algorithm Case Recurrence Relation
complexity
Fibonacci
------ T(n) = T(n − 1) + T(n − 2) + O(1) O(2ⁿ)
Series
Factorial ---- T(n) = T(n − 1) + O(1) O(n)
Tower of
------ T(n) = 2T(n − 1) + O(1) O(2ⁿ)
Hanoi
Merge Sort Best/Worst T(n) = 2T(n / 2) + O(n) O(n logn)
Bubble Sort Best T(n) = T(n−1) + O(1) O(n)
Bubble Sort worst T(n) = T(n − 1) + O(n) O(n²)
T(n) = 2T(n / 2) + O(n) O(n logn)
Quick Sort Best

Quick Sort Worst T(n) = T(n −1) + O(n) O(n²)

Binary Search Average/worst T(n) = T(n / 2) + O(1) O(logn)
Binary Search Best T(n)=O(1) O(1)

282
Solving recurrence relation
• The following are the ways to solve a
recurrence relation :
● Recursion Tree method
● Substitution method
● Master method

283
The master theorem
A. Assumes the subproblems are unequal sizes
B. can be used if the subproblems are of equal size
C. cannot be used for divide and conquer algorithms
B. cannot be used for asymptotic complexity analysis
The master theorem
A. Assumes the subproblems are unequal sizes
B. can be used if the subproblems are of equal size
C. cannot be used for divide and conquer algorithms
B. cannot be used for asymptotic complexity analysis
The Master Theorem is used to determine the
asymptotic time complexity of divide and conquer
algorithms when the subproblems are of equal size.
It solves recurrences of the form:

Where:
•a≥1: number of subproblems
𝑛
•b>1: each subproblem is of size (equal size)
𝑏
•f(n): cost of dividing and combining
287
Given the recurrence relation

determine the asymptotic upper bound of

288
15.Solve T(n)=4T(n/2)+n2

A. T(n)=O(n)

B. T(n)=O(n2log n)

C. T(n)=O(n2)

D. T(n)=O(log n)
Solve T(n)=4T(n/2)+n2

A. T(n)=O(n)

B. T(n)=O(n2log n)

C. T(n)=O(n2)

D. T(n)=O(log n)
16.Solve the recurrence of binary search algorithm
T(n)=T(n/2)+1 using master method.
A. Ө(n)
B. Ө(log n)
C. Ө(n2)
D. Ө(n log n)
Solve the recurrence of binary search algorithm T(n)=T(n/2)+1
using master method.
A. Ө(n)
B. Ө(log n)
C. Ө(n2)
D. Ө(n log n)
Solve the following recurrence using Master Method
T(n)=0.7T(n/2)+1/n

A. T(n)=O(n)
B. T(n)=O(logn)
C. T(n)=O(n2 logn)
D. It cannot be solved using Master theoremB. T(n) =O(log n)
17. Solve the following recurrence using Master Method
T(n)=0.7T(n/2)+1/n
The master theorem cannot
be used if:
A. T(n)=O(n) T(n) is not monotone.
B. T(n)=O(logn) eg. T(n) = sin n
f(n) is not a polynomial.
C. T(n)=O(n2 logn)
eg. f(n) = 2n
D. It cannot be solved using Master theorem a is not a constant.
eg. a = 2n
a<1
a is a fraction
f(n) is negative
 Solve the recurrence T(n)=2T(n/2)+n4
using master method.

A. Ө(n)
B. Ө(n4)
C. Ө(n log n)
D. Ө(n2)

297
 Solve the recurrence T(n)=2T(n/2)+n4
using master method.

A. Ө(n)
B. Ө(n4)
C. Ө(n log n)
D. Ө(n2)

298
Amortised analysis
Key point: The time required to perform a sequence of data
structure operations is averaged over all operations
performed.
Amortized analysis can be used to show that:
❖ The average cost of an operation is small
❖ Amortized analysis does not use any probabilistic
reasoning
❖ Amortized analysis guarantees the average performance of
each operation in the worst case

299
Amortised analysis-cont..
The most common three techniques
•The aggregate method
•The accounting method
•The potential method
If there are several types of operations in a sequence:
•The aggregate method assigns:
— The same amortized cost to each operation
•The accounting method and the potential method may assign:
— Different amortized costs to different types of operations

300
Which of the following is NOT a method for
performing amortized analysis of
algorithms?
(A) Aggregate method
(B) Accounting method
(C) Potential method
(D) None of the above

301
Which of the following is NOT a method for
performing amortized analysis of
algorithms?
(A) Aggregate method
(B) Accounting method
(C) Potential method
(D) None of the above

302
Explanation: The first loop is O(N) and the second loop is
O(M). Since N and M are independent variables, so we can't
say which one is the leading term. Therefore Time
complexity of the given problem will be O(N+M).
Since variables size does not depend on the size of the
input, therefore Space Complexity will be constant or O(1)
Design strategies

• Divide-and-conquer
• Greedy method
• Dynamic programming
• Branch and bound

CRACK CS IT WITH DIVYA 304

Divide and Conquer Method

● Quick sort
● Merge sort
● Strassen’s matrix Multiplication

CRACK CS IT WITH DIVYA 305

Divide And Conquer Technique
General Method:
Divide: Divide the problem into smaller sub-problems.
Conquer: Solve the sub-problems recursively until they are solved.
Combine: Combine the solutions of the sub-problems to get the final
solution for the whole problem.
Note:
Divide and Conquer should be used when the same sub-problems are
not evaluated many times.
(If sub-problems repeat, use Dynamic Programming instead.)

CRACK CS IT WITH DIVYA 306

QuickSort
Itpicks an element as pivot and partitions the given array around
the picked pivot.

CRACK CS IT WITH DIVYA 307

Which of the following methods is the most
effective for picking the pivot element?

a) first element
b) last element
c) median-of-three partitioning
d) random element

CRACK CS IT WITH DIVYA 308

Which of the following methods is the most
effective for picking the pivot element?

a) first element
b) last element
c) median-of-three partitioning
d) random element

CRACK CS IT WITH DIVYA 309

STRASSEN MULTIPLICATION
Strassen’s Matrix Multiplication uses divide and conquer.
Naive Matrix multiplocation takes o(n3), Strassen
multiplication reduces 8 multiplications to 7 using special
formulas.
Addition/Subtraction → Θ(n2) time.
Time complexity:
T(n)=7T(n/2)+Θ(n2) ⟹ O(n2.8074)

CRACK CS IT WITH DIVYA 310

Strassen’s algorithm is a/an algorithm.
A. Non recursive
B. Recursive
C. Approximation
D. Accurate

CRACK CS IT WITH DIVYA 311

Strassen’s algorithm is a/an algorithm.
A. Non recursive
B. Recursive
C. Approximation
D. Accurate

CRACK CS IT WITH DIVYA 312

What is the running time of Naive matrix multiplication algorithm?

a.O(n 2.81)

b.O(n 1.81)

c.O(n 3)

d.O(n2)

CRACK CS IT WITH DIVYA 313

What is the running time of Naive matrix
multiplication algorithm?

a.O(n 2.81)
b.O(n 1.81)
c.O(n 3)
d.O(n2)

CRACK CS IT WITH DIVYA 314

○ Greedy Method
■ General Method
■ Eg: Fractional Knapsack Problem
■ Treevertex splitting

CRACK CS IT WITH DIVYA 315

GREEDY METHOD

➢ Used for optimization problems (find max or min).

➢ Works in stages, picking the best choice at each
step.
➢ Never backtracks or changes past decisions.
➢ Follows a top-down approach.

CRACK CS IT WITH DIVYA 316

Greedy Method – Solutions
Feasible solution: Subset of inputs satisfying all constraints.
Optimal solution: Feasible solution that maximizes or minimizes the
objective function.
Greedy algorithms may not always give the optimal solution for every
problem.
● Examples: Fractional Knapsack Problem ,Tree vertex splitting
Minimum Cost Spanning Tree -Kruskal’s and Prim’s Algorithm

CRACK CS IT WITH DIVYA 317

Knapsack Problem
Knapsack Problems
Fractional Knapsack: Items are divisible to maximize profit.
Solved using Greedy method.
0/1 Knapsack: Items are indivisible — take whole or none.
Solved using Dynamic Programming.

CRACK CS IT WITH DIVYA 318

Fractional Knapsack – Greedy Algorithm

1. Calculate value/weight ratio for each item.

2. Sort items in decreasing order of this ratio.
3. Add items to knapsack starting from highest ratio.
4. If the next item can’t fit fully, take the fraction that fits.
Always gives optimal solution.

CRACK CS IT WITH DIVYA 319

Consider the capacity of the knapsack W=60 and the list of provided items are
shown in the following table

ITEM A B C D
Profit (Value) 280 100 120 120
Weight 40 10 20 24
Ratio 7 10 6 5
(Profit/Weight)

CRACK CS IT WITH DIVYA 320

After sorting (withrespect to ratio), the items are as
shown in the following table.

Item B A C D
Profit 100 280 120 120
Weight 10 40 20 24
Ratio 10 7 6 5

CRACK CS IT WITH DIVYA 321

B is chosen first (weight 10 < knapsack capacity 60). Next, A
(weight 40) is added (remaining capacity 50). C (weight 20)
cannot fit entirely, so a fraction (60−50)/20=0.5 is taken.
The knapsack is now full, so no more items can be added

• The total weight of the selected items is 10 +40 +20 *(10/20)=60

• And the total profit is 100 +280 +120 *(10/20)=380 +60 =440
• This is the optimal solution. We cannot gain more profit
selecting any different combination of items.

CRACK CS IT WITH DIVYA 322

Time complexity of fractional knapsack
problem is
a. O( n log n)
b. O(n)
c. O(n2)
d. O(nw)

CRACK CS IT WITH DIVYA 323

Time complexity of fractional knapsack
problem is
a. O( n log n)
b. O(n)
c. O(n2)
d. O(nw)

CRACK CS IT WITH DIVYA 324

○ Greedy Method
■ Eg: Minimum Cost Spanning Tree (MST)
● Kruskal’s Algorithm
● Prim’ Algorithm

CRACK CS IT WITH DIVYA 325

Spanning Tree
Spanning Tree: For an undirected, connected graph
G=(V,E), a spanning tree is a subgraph that is a tree
including all vertices of G

CRACK CS IT WITH DIVYA 326

Minimum Spanning Tree

Cost of a spanning tree: Sum of its edge weights.

Minimum Spanning Tree (MST): Spanning tree with the
smallest possible cost.
Multiple spanning trees and multiple MSTs can exist.

CRACK CS IT WITH DIVYA 327

Kruskal and prim’s algorithms
Kruskal’s Algorithm:
Sort all edges in non-decreasing order of weight.
Pick the smallest edge; include it if it doesn’t form a cycle, else discard.
Repeat until the spanning tree has V−1 edges.

Prim’s Algorithm:
Initialize all vertices’ key values as ∞, except the starting vertex (key = 0).
Maintain a set of vertices included in the MST.
Pick the vertex with minimum key not in the set, include it.
Update the key of adjacent vertices if the edge weight is smaller than their
current key.
Repeat until all vertices are included.

CRACK CS IT WITH DIVYA 328

KRUSKAL ALGORITHM EXAMPLE

CRACK CS IT WITH DIVYA 329

CRACK CS IT WITH DIVYA 330
CRACK CS IT WITH DIVYA 331
PRIMS AND KRUSKAL COMPARISO
• Complexity
• ElogV or ElogE (best case-using binary heap)
• O(V²) (worst case-using adjacency list)
▪ Total cost of MST is the same, but tree structure may differ.
▪ Prim’s is generally more complex than Kruskal’s.
▪ Kruskal’s can handle disconnected graphs; Prim’s requires a
starting vertex.
▪ Prim’s can start from any vertex; Kruskal’s starts from the
minimum-weight edge.
▪ Min Priority queue used by both algorithm

CRACK CS IT WITH DIVYA 332

333
334
■ Dynamic Programming
● Examples
○ All Pairs Shortest Path
Problem
○ Multistage Graph
○ Single source shortest path
problem
○ Dijkstra’s algorithm
○ Bellman ford algorithm
○ Travelling salesman problem

CRACK CS IT WITH DIVYA 335

Dynamic Programming (DP)
Dynamic Programming is a problem-solving technique that:
Breaks a complex problem into smaller subproblems
Solves each subproblem only once
Stores the solutions (memorization) to avoid recomputation
Key Properties
Overlapping Subproblems – Same subproblems occur multiple times.
Optimal Substructure – The optimal solution of the main problem can
be formed from the optimal solutions of its subproblems.

CRACK CS IT WITH DIVYA 336

Steps in Dynamic Programming
1. Break the problem into simpler subproblems
2. Solve each subproblem optimally
3. Store results (memoization)
4. Reuse stored results instead of recalculating
5. Combine subproblem results to get the final answer
Use Case
Mainly used for optimization problems (finding minimum or maximum
values)
Guarantees optimal solution if it exists
Example: Fibonacci series, shortest path algorithms (e.g., Dijkstra, Floyd-
Warshall), knapsack problem.

CRACK CS IT WITH DIVYA 337

 Floyd–Warshall Algorithm (All-Pairs Shortest Path)
▪ Finds the shortest paths between every pair of vertices in a weighted graph.
▪ Works for both directed and undirected graphs.
▪ Based on the transitive closure concept.
Time Complexity:
O(V3) - (where V = number of vertices)
Applications:
Routing problems
Network analysis
Finding reachabilityI

CRACK CS IT WITH DIVYA 338

Dijkstra’s Algorithm – Single Source Shortest Path
Input: Weighted graph (no negative edges), source vertex s
Goal: Find shortest distance d(s,v) to all vertices v
Data Structure: Min Priority Queue
Type: Greedy (also solvable via DP)
Works for: Directed & undirected graphs
Doesn’t work for: Negative weight edges
● Time complexity :
● O(E.log(V))—bestcase
● O(v²)---worstcase(completegraph)

CRACK CS IT WITH DIVYA 339

TRAVELING SALES MAN PROBLEM

Time Complexity: O(n!)

CRACK CS IT WITH DIVYA 340

Single-Source Shortest Path Problem –Bellman–Ford Algorithm

● Allows negative-weight edges;

● Returns True (anda solution embedded in the graph)if no negative-weight cycles
are reachable from s, and False otherwise.
● Time Complexity:O(VE)----->O(n2)
● Worst case—--->O(n3)--------> Complete GrapH

Dijkstra’s algorithm
O(E.log(V))—bestcase
O(v²)---worstcase(completegraph)

CRACK CS IT WITH DIVYA 341

BELL MAN FORD ALGORITHM cont..
• Allows negative-weight edges;
• Ifa graph contains a “negative cycle”,No shortest path
• Proposed by Alphonso shimbe
• Basic principle: Relaxation
• Relaxation operation on all edges (n-1 times). But in Dijkstra’s
only adjacent vertices are relaxed.
• Algorithm returns Boolean(T or F)
• Algorithm works for V-1 passes or E passes.
● Time Complexity:
● Best case-- O(VE) ORO(n2) OR O(E|V|-1)
● Worst case—--->O(n3)--------> Complete Graph

CRACK CS IT WITH DIVYA 342

Backtracking Algorithm
Idea: Brute-force method that explores all possible
solutions; backtracks when a path is unsuitable.
Approach: Uses recursion; explores solution space tree from
root (start) to leaves (end).
Use Cases: Combinatorial & optimization problems.
Language Support: Prolog (supports backtracking), Fortran
(no backtracking).
Key Point: Works well for problems with complex
constraints.

CRACK CS IT WITH DIVYA 343

Applications of Backtracking

● N-queen problem -Time Complexity: O(N!)

● Sum of subset problem
● Graph coloring
● Hamiltonian cycle
● Knight tour problem

CRACK CS IT WITH DIVYA 344

Branch and Bound
Purpose: Solves combinatorial optimization problems using a
state space tree.
Traversal: Similar to backtracking but explores nodes like BFS.
Types:
FIFO: Uses queue.
LIFO: Uses stack.
Least Cost: Explores nodes by minimum cost.
Best First: Uses priority queue.
Key Point: Combines ideas from DFS (backtracking) and BFS
(branch & bound).

CRACK CS IT WITH DIVYA 345

Chromatic Number:

The minimum number of colors needed to color a graph is

called its chromatic number

CRACK CS IT WITH DIVYA 346

 RECALL THE CONCEPTS
DP examples DAC examples
• 0/1 knapsack problem • Quick sort
• All pairs shortest path (Bottom • Merge sort
up) • Strassen’s matrix multiplication
• Single source shortest path Greedy examples
• Dijkstra’s algorithm
• Bellman ford algorithm
• Fractional knapsack problems
• Tree vertex splitting
• Tower of Hanoi- O(2^n)
• Minimum spanning tree
• Fibonacci series- O(2^n)
• Kruskal’s
• Matrix chain multiplication
• Prim’s
• Longest common sequence • Dijkstra’s algorithm
• Project scheduling
• DAC- TD
• Multistage graph
• Greedy- TD
• Travelling salesman (O(n!) tree vertex-BU
• DP-TD,BU
347
THANK YOU

CRACK CS IT WITH DIVYA 348