[Link] the following recurrence relations using Master 2.

[Link] asymptotic notations Big O, Big Ω and Big Θ with [Link] Merge Sort algorithm with example. Derive its
Method suitable examples. recurrence relation and time complexity.
(a) Asymptotic notations are used to represent the growth rate Merge Sort is a Divide and Conquer algorithm. It divides the
𝑛 of algorithms and analyze time complexity for large input size array into two halves, recursively sorts them and then merges
𝑇(𝑛) = 2𝑇 ( ) + 𝑛
2 𝑛. the sorted halves.
Given: [Link] O Notation 𝑶
𝑎 = 2, 𝑏 = 2, 𝑓(𝑛) = 𝑛 Big O notation represents the upper bound of an algorithm. It Algorithm
𝑛log⁡𝑏 𝑎 = 𝑛log⁡2 2 = 𝑛 gives the maximum running time. [Link] the array into two halves.
Definition [Link] each half recursively.
Since, A function 𝑓(𝑛)is 𝑂(𝑔(𝑛))if there exist positive constants [Link] the sorted halves.
𝑓(𝑛) = Θ(𝑛log⁡𝑏 𝑎 ) 𝑐and 𝑛0 such that
𝑓(𝑛) ≤ 𝑐𝑔(𝑛), ∀𝑛 ≥ 𝑛0 Pseudocode
By Master Theorem Case 2, Example MERGE-SORT(A,low,high)
𝑇(𝑛) = Θ(𝑛log⁡ 𝑛) 𝑓(𝑛) = 3𝑛2 + 5𝑛 + 2 {
𝑇(𝑛) = Θ(𝑛log⁡ 𝑛) if(low<high)
Here, {
𝑓(𝑛) = 𝑂(𝑛2 ) mid=(low+high)/2;
(b) MERGE-SORT(A,low,mid);
𝑛 2
because 𝑛 is the highest growing term.
𝑇(𝑛) = 4𝑇 ( ) + 𝑛2 MERGE-SORT(A,mid+1,high);
2 Example Algorithms MERGE(A,low,mid,high);
Given:
𝑎 = 4, 𝑏 = 2, 𝑓(𝑛) = 𝑛2 • Bubble Sort : 𝑂(𝑛2 )
}
}
𝑛log⁡𝑏 𝑎 = 𝑛log⁡2 4 = 𝑛2
• Binary Search : 𝑂(log⁡ 𝑛)
Since, • Merge Sort : 𝑂(𝑛log⁡ 𝑛)
Example
Given array:
𝑓(𝑛) = Θ(𝑛log⁡𝑏 𝑎 ) [Link] Omega Notation 𝛀 38, 27, 43, 3, 9, 82, 10
Big Omega notation represents the lower bound of an
By Master Theorem Case 2, algorithm. It gives the minimum running time. Step 1: Divide
𝑇(𝑛) = Θ(𝑛2 log⁡ 𝑛) Definition [38,27,43,3] [9,82,10]
𝑇(𝑛) = Θ(𝑛2 log⁡ 𝑛) A function 𝑓(𝑛)is Ω(𝑔(𝑛))if there exist positive constants
𝑐and 𝑛0 such that Further division:
𝑓(𝑛) ≥ 𝑐𝑔(𝑛), ∀𝑛 ≥ 𝑛0 [38,27] [43,3] [9,82] [10]
(c) Example
𝑛 𝑓(𝑛) = 3𝑛2 + 5𝑛 + 2
𝑇(𝑛) = 5𝑇 ( ) + √𝑛 Further:
5 [38] [27] [43] [3] [9] [82] [10]
Given: Here,
𝑎 = 5, 𝑏 = 5, 𝑓(𝑛) = √𝑛 𝑓(𝑛) = Ω(𝑛2 )
𝑛log⁡𝑏 𝑎 = 𝑛log⁡5 5 = 𝑛 Step 2: Merge
Example Algorithms [38] + [27] → [27,38]
Since,
𝑓(𝑛) = 𝑂(𝑛1−𝜖 ) • Linear Search Best Case : Ω(1) [43] + [3] → [3,43]
[9] + [82] → [9,82]
• Binary Search : Ω(log⁡ 𝑛)
By Master Theorem Case 1, [Link] Theta Notation 𝚯 Now,
𝑇(𝑛) = Θ(𝑛) Big Theta notation represents both upper and lower bounds. [27,38] + [3,43] → [3,27,38,43]
𝑇(𝑛) = Θ(𝑛) It gives exact asymptotic growth. [9,82] + [10] → [9,10,82]
Definition
A function 𝑓(𝑛)is Θ(𝑔(𝑛))if there exist positive constants Final merge:
(d) 𝑐1 , 𝑐2 and 𝑛0 such that [3,27,38,43] + [9,10,82]
𝑛 𝑐1 𝑔(𝑛) ≤ 𝑓(𝑛) ≤ 𝑐2 𝑔(𝑛), ∀𝑛 ≥ 𝑛0
𝑇(𝑛) = 𝑇 ( ) + 𝑛
2 Example Sorted array:
Given: 𝑓(𝑛) = 3𝑛2 + 5𝑛 + 2 [3, 9, 10, 27, 38, 43, 82]
𝑎 = 1, 𝑏 = 2, 𝑓(𝑛) = 𝑛
𝑛log⁡𝑏 𝑎 = 𝑛log⁡2 1 = 1 Here,
𝑓(𝑛) = Θ(𝑛2 ) Recurrence Relation
Since, For Merge Sort,
𝑓(𝑛) = Ω(𝑛0+1 ) Example Algorithms 𝑛
𝑇(𝑛) = 2𝑇 ( ) + 𝑛
2
By Master Theorem Case 3, • Merge Sort : Θ(𝑛log⁡ 𝑛) Where:
𝑇(𝑛) = Θ(𝑛)
𝑇(𝑛) = Θ(𝑛)
• Heap Sort : Θ(𝑛log⁡ 𝑛) • 2𝑇(𝑛/2)for dividing into two subproblems
Difference Between 𝑶, 𝛀and 𝚯
Notation Meaning
• 𝑛for merging process
Using Master Theorem:
𝑂 Upper Bound 𝑎 = 2, 𝑏 = 2, 𝑓(𝑛) = 𝑛
𝑛log⁡𝑏 𝑎 = 𝑛log⁡2 2 = 𝑛
Ω Lower Bound
Θ Exact Bound Since,
𝑓(𝑛) = Θ(𝑛log⁡𝑏 𝑎 )
Conclusion
Asymptotic notations help in analyzing and comparing By Master Theorem Case 2,
algorithms based on efficiency and performance for large 𝑇(𝑛) = Θ(𝑛log⁡ 𝑛)
input sizes.

Time Complexity
Case Complexity
Best Case 𝑂(𝑛log⁡ 𝑛)
Average Case 𝑂(𝑛log⁡ 𝑛)
Worst Case 𝑂(𝑛log⁡ 𝑛)

Space Complexity
𝑂(𝑛)

Advantages
[Link] sorting algorithm.
[Link] for large datasets.
[Link] 𝑂(𝑛log⁡ 𝑛)complexity.

Disadvantages
[Link] extra memory.
[Link] suitable for small arrays.

Conclusion
Merge Sort is an efficient Divide and Conquer sorting
algorithm with time complexity 𝑂(𝑛log⁡ 𝑛). It is widely used
for sorting large datasets.
[Link] Quick Sort algorithm with suitable example. [Link] Randomized Quick Sort and compare it with Quick [Link] Max Heap using heapify procedure for the given
Analyze best, average and worst case complexities. Sort. elements and explain Heap Sort.
Quick Sort is a Divide and Conquer sorting algorithm. It Randomized Quick Sort is an improved version of Quick Sort Heap Sort is a comparison-based sorting algorithm based on
selects a pivot element and partitions the array into two parts in which the pivot element is selected randomly instead of Binary Heap data structure. In Max Heap, parent node is
such that: choosing a fixed position pivot. always greater than its child nodes.
• Elements smaller than pivot are placed on left
Random selection of pivot reduces the probability of worst
case occurrence. Algorithm of Heap Sort
side. Algorithm [Link] Max Heap from given array.
• Elements greater than pivot are placed on [Link] a random pivot element. [Link] root element with last element.
right side. [Link] pivot with last element. [Link] heap size by 1.
Then the same process is applied recursively. [Link] the array. [Link] heapify on root.
Algorithm [Link] Randomized Quick Sort recursively on left and right [Link] until heap becomes sorted.
[Link] a pivot element. subarrays.
[Link] the array. Heapify Procedure
[Link] Quick Sort recursively on left subarray. Pseudocode HEAPIFY(A,n,i)
[Link] Quick Sort recursively on right subarray. RANDOMIZED-QUICKSORT(A,low,high) {
{ largest=i;
Pseudocode if(low<high) left=2*i+1;
QUICKSORT(A,low,high) { right=2*i+2;
{ p=RANDOMIZED-PARTITION(A,low,high);
if(low<high) if(left<n && A[left]>A[largest])
{ RANDOMIZED-QUICKSORT(A,low,p-1); largest=left;
p=PARTITION(A,low,high);
QUICKSORT(A,low,p-1); RANDOMIZED-QUICKSORT(A,p+1,high); if(right<n && A[right]>A[largest])
QUICKSORT(A,p+1,high); } largest=right;
} }
} if(largest!=i)
Randomized Partition {
Partition Algorithm RANDOMIZED-PARTITION(A,low,high) swap(A[i],A[largest]);
PARTITION(A,low,high) { HEAPIFY(A,n,largest);
{ i=random(low,high); }
pivot=A[high]; }
i=low-1; swap(A[i],A[high]);
Heap Sort Algorithm
for(j=low;j<high;j++) return PARTITION(A,low,high); HEAPSORT(A,n)
{ } {
if(A[j]<pivot) for(i=n/2-1;i>=0;i--)
{ Example HEAPIFY(A,n,i);
i++; Given array:
swap(A[i],A[j]); [ for(i=n-1;i>=0;i--)
} 40,\ 20,\ 60,\ 10,\ 50,\ 30 {
} ] swap(A[0],A[i]);
Suppose randomly selected pivot = 30 HEAPIFY(A,i,0);
swap(A[i+1],A[high]); After partition: }
return i+1; [ }
} 20,\ 10,\ 30,\ 40,\ 50,\ 60
] Example
Example Now recursively sort left and right subarrays. Given elements:
Given array: Final sorted array: 4, 10, 3, 5, 1
[ [
10,\ 80,\ 30,\ 90,\ 40,\ 50,\ 70 10,\ 20,\ 30,\ 40,\ 50,\ 60
] ] Step 1: Construct Max Heap
Take pivot = 70 Initial array:
After partition: Recurrence Relation 4, 10, 3, 5, 1
[ Average Case:
10,\ 30,\ 40,\ 50,\ 70,\ 90,\ 80 T(n)=2T\left(\frac{n}{2}\right)+n Heapify process:
] Using Master Theorem: 10, 5, 3, 4, 1
Now apply Quick Sort recursively. [
Left subarray: a=2,\ b=2,\ f(n)=n Max Heap formed:
[ ] 10
10,\ 30,\ 40,\ 50 [ / \
] n^{\log_b a}=n 5 3
Right subarray: ] /\
[ Therefore, 4 1
90,\ 80 [
] T(n)=\Theta(n\log n) Step 2: Heap Sort
Final sorted array: ] Swap root with last element:
[ 1, 5, 3, 4, 10
10,\ 30,\ 40,\ 50,\ 70,\ 80,\ 90 Time Complexity
] Heapify:
Case Complexity
5, 4, 3, 1, 10
Best Case (O(n\log n))
Recurrence Relation
Best/Average Case: Average Case (O(n\log n)) Again swap:
T(n)=2T\left(\frac{n}{2}\right)+n 1, 4, 3, 5, 10
Worst Case (O(n^2))
Using Master Theorem:
Worst case probability becomes very small because pivot is Heapify:
[
selected randomly. 4, 1, 3, 5, 10
a=2,\ b=2,\ f(n)=n
] Space Complexity
[ Again swap:
[
O(\log n) 3, 1, 4, 5, 10
n^{\log_b a}=n
] ]
Again swap:
Therefore,
Comparison Between Quick Sort and Randomized Quick Sort 1, 3, 4, 5, 10
[
T(n)=\Theta(n\log n) Randomized Quick
Feature Quick Sort
] Sort
Final Sorted Array
Pivot Selection Fixed Random 1, 3, 4, 5, 10
Time Complexity
Worst Case Time Complexity
Case Complexity High Very Low
Probability Case Complexity
Best Case (O(n\log n))
Average Complexity (O(n\log n)) (O(n\log n)) Best Case 𝑂(𝑛log⁡ 𝑛)
Average Case (O(n\log n))
Worst Complexity (O(n^2)) (O(n^2)) Average Case 𝑂(𝑛log⁡ 𝑛)
Worst Case (O(n^2))
Depends on Worst Case 𝑂(𝑛log⁡ 𝑛)
Worst case occurs when pivot is always smallest or largest Performance More balanced
input Space Complexity
element.
Efficiency Good Better in practice 𝑂(1)
Example:
• Already sorted array Advantages of Randomized Quick Sort
Advantages
[Link]-place sorting algorithm.
• Reverse sorted array [Link] chance of worst case.
[Link] 𝑂(𝑛log⁡ 𝑛)complexity.
Space Complexity [Link] better for sorted inputs.
[ [Link] efficient in practical applications.
Disadvantages
O(\log n) Disadvantages
[Link] stable.
] [Link] number generation required.
[Link] than Quick Sort in practice.
[Link] case still possible.
[Link] Breadth First Search (BFS) algorithm with example [Link] Depth First Search (DFS) algorithm with example [Link] BFS and DFS algorithms.
graph and complexity analysis. graph and complexity analysis. Breadth First Search (BFS) and Depth First Search (DFS) are
Breadth First Search (BFS) is a graph traversal algorithm that Depth First Search (DFS) is a graph traversal algorithm that graph traversal algorithms used to visit all vertices of a graph.
visits vertices level by level. It first visits all adjacent vertices explores vertices deeply before backtracking. It visits one
of a node before moving to the next level. adjacent vertex completely before visiting another vertex. Difference Between BFS and DFS
BFS uses Queue data structure. DFS uses Stack data structure or recursion. Feature BFS DFS
Algorithm Algorithm
[Link] from source vertex. [Link] from source vertex. Breadth First
Full Form Depth First Search
[Link] source vertex as visited. [Link] source vertex as visited. Search
[Link] source vertex into queue. [Link] an adjacent unvisited vertex recursively. Traversal
[Link] a vertex from queue. [Link] until all vertices are visited. Level by level Depth wise
Method
[Link] all unvisited adjacent vertices. [Link] when no unvisited adjacent vertex exists.
Data Structure
[Link] adjacent vertices into queue. Queue Stack/Recursion
Used
[Link] until queue becomes empty. Pseudocode
Pseudocode DFS(G,u) Visits nearest Visits deepest node
Traversal Order
BFS(G,s) { node first first
{ visited[u]=true; Finds shortest
for each vertex v in G Does not guarantee
Shortest Path path in
visited[v]=false; for each adjacent vertex v of u shortest path
unweighted graph
{
visited[s]=true; if(visited[v]==false) Memory
More Less
enqueue(Q,s); DFS(G,v); Requirement
} Backtracking Not required Required
while(Q not empty) }
Implementation Iterative Recursive/Iterative
{
u=dequeue(Q); Example Graph Time Complexity 𝑂(𝑉 + 𝐸) 𝑂(𝑉 + 𝐸)
A Space
for each adjacent vertex v of u /\ 𝑂(𝑉) 𝑂(𝑉)
Complexity
{ B C
if(visited[v]==false) /\ \ Shortest path, Cycle detection,
Applications
{ D E F broadcasting topological sorting
visited[v]=true; Start vertex = A
enqueue(Q,v); BFS Traversal Example
} DFS Traversal A
} Step 1: /\
} Visit A B C
} Traversal: /\ \
𝐴 D E F
Example Graph Step 2: BFS Traversal:
A Go to B 𝐴→𝐵→𝐶→𝐷→𝐸→𝐹
/\ Traversal:
B C 𝐴, 𝐵
/\ \ Step 3: DFS Traversal Example
D E F Go to D A
Start vertex = A Traversal: /\
𝐴, 𝐵, 𝐷 B C
BFS Traversal /\ \
Step 1: No adjacent vertex left, so backtrack to B. D E F
Visit A Step 4: DFS Traversal:
Queue: Visit E 𝐴→𝐵→𝐷→𝐸→𝐶→𝐹
𝐴 Traversal:
Step 2: 𝐴, 𝐵, 𝐷, 𝐸
Remove A and visit adjacent vertices B and C Advantages of BFS
Queue: Backtrack to A. [Link] shortest path in unweighted graph.
𝐵, 𝐶 Step 5: [Link] traversal.
Visit C [Link] in networking applications.
Traversal: Traversal:
𝐴, 𝐵, 𝐶 𝐴, 𝐵, 𝐷, 𝐸, 𝐶 Advantages of DFS
Step 6: [Link] less memory.
Step 3: Visit F [Link] recursive implementation.
Remove B and visit D and E Traversal: [Link] for backtracking problems.
Queue: 𝐴, 𝐵, 𝐷, 𝐸, 𝐶, 𝐹
𝐶, 𝐷, 𝐸 Final DFS Traversal Disadvantages of BFS
𝐴→𝐵→𝐷→𝐸→𝐶→𝐹 [Link] more memory.
Traversal: [Link] maintenance needed.
𝐴, 𝐵, 𝐶, 𝐷, 𝐸
Time Complexity Disadvantages of DFS
Step 4: For graph with: [Link] not guarantee shortest path.
Remove C and visit F
Queue:
• 𝑉vertices [Link] traverse unnecessary deep paths.

𝐷, 𝐸, 𝐹 • 𝐸edges Conclusion
Time Complexity: BFS traverses graph level by level using queue, whereas DFS
Traversal: 𝑂(𝑉 + 𝐸) traverses graph depth wise using stack or recursion. Both
𝐴, 𝐵, 𝐶, 𝐷, 𝐸, 𝐹 algorithms have time complexity 𝑂(𝑉 + 𝐸)and are widely
used in graph applications.
Final BFS Traversal Space Complexity
𝐴→𝐵→𝐶→𝐷→𝐸→𝐹 𝑂(𝑉)
Time Complexity
For graph with: due to recursion stack.
• 𝑉vertices
Applications
• 𝐸edges [Link] sorting.
Time Complexity: [Link] detection.
𝑂(𝑉 + 𝐸) [Link] finding.
[Link] components.
Space Complexity [Link] solving.
𝑂(𝑉)
Advantages
due to queue storage. [Link] less memory compared to BFS.
[Link] recursive implementation.
Applications [Link] for deep graphs.
[Link] path in unweighted graph.
[Link] crawling. Disadvantages
[Link] broadcasting. [Link] not guarantee shortest path.
[Link] networking applications. [Link] go deep unnecessarily.
[Link] collection.
Advantages Conclusion
[Link] and efficient. Depth First Search is an important graph traversal algorithm
[Link] shortest path in unweighted graph. that explores vertices deeply using recursion or stack with
[Link] nodes systematically. time complexity 𝑂(𝑉 + 𝐸).

Disadvantages
[Link] more memory.
[Link] suitable for deep graphs.
[Link] AVL Tree insertion and perform LL, RR, LR and RL [Link] Red Black Tree properties and compare Red Black [Link] disjoint set operations using Union by Rank and
rotations with examples. Tree with AVL Tree. Path Compression.
AVL Tree is a self-balancing Binary Search Tree in which the Red Black Tree is a self-balancing Binary Search Tree in which Disjoint Set is a data structure used to maintain a collection of
difference between heights of left subtree and right subtree is each node contains an extra bit called color. The color may be non-overlapping sets. It is also called Union-Find data
at most 1. RED or BLACK. structure.
This difference is called Balance Factor. The balancing is maintained using coloring rules and It supports two operations:
𝐵𝑎𝑙𝑎𝑛𝑐𝑒 𝐹𝑎𝑐𝑡𝑜𝑟 = 𝐻𝑒𝑖𝑔ℎ𝑡(𝐿𝑒𝑓𝑡 𝑆𝑢𝑏𝑡𝑟𝑒𝑒) rotations. [Link]
− 𝐻𝑒𝑖𝑔ℎ𝑡(𝑅𝑖𝑔ℎ𝑡 𝑆𝑢𝑏𝑡𝑟𝑒𝑒) [Link]
Properties of Red Black Tree Disjoint set is mainly used in Kruskal’s algorithm, network
For AVL Tree: [Link] node is either RED or BLACK. connectivity and graph problems.
−1 ≤ 𝐵𝐹 ≤ 1 [Link] node is always BLACK. Basic Operations
[Link] leaf nodes (NULL nodes) are BLACK. [Link] Set
If balance factor becomes greater than 1 or less than -1, [Link] a node is RED, then both its children must be BLACK. Creates a separate set for each element.
rotations are performed. [Link] path from a node to its descendant NULL nodes Example:
AVL Tree Insertion Algorithm contains same number of BLACK nodes. {1}, {2}, {3}, {4}
[Link] node as Binary Search Tree. These properties maintain balance in the tree. [Link] Operation
[Link] balance factor. Finds representative(parent/root) of a set.
[Link] tree becomes unbalanced, perform suitable rotation. Example of Red Black Tree Example:
Types of Rotations 20(B) 1→2→3
[Link] Rotation / \ Find(1)=3
[Link] Rotation 10(R) 30(R) [Link] Operation
[Link] Rotation / \ / \ Combines two disjoint sets into a single set.
[Link] Rotation 5(B)15(B)25(B)35(B) Example:
[Link] Rotation Here: Before Union:

•
Occurs when insertion is made in left subtree of left child. {1,2}, {3,4}
Example Root is BLACK.
Insert: • RED nodes have BLACK children. After Union:
30, 20, 10 {1, 2, 3, 4}
• All root-to-leaf paths have same number of Union by Rank
Before rotation: BLACK nodes. Union by Rank attaches smaller height tree under larger
30 height tree to reduce tree height.
/ Insertion in Red Black Tree Rules
20 [Link] node as RED node. [Link] ranks of roots.
/ [Link] properties are violated, perform: [Link] smaller rank tree below larger rank tree.
10
Balance factor of 30 becomes +2.
• Recoloring
[Link] ranks are equal, choose one as root and increase its rank
by 1.
Perform Right Rotation. • Rotations Example
After rotation: Rotations used: Set 1: Set 2:

•
20
/ \ Left Rotation 1 3
10 30 • Right Rotation | |
[Link] Rotation 2 4
Occurs when insertion is made in right subtree of right child. Advantages of Red Black Tree Ranks are equal.
Example [Link]-balancing tree. After Union:
Insert: [Link], insertion and deletion take 𝑂(log⁡ 𝑛)time. 1
10, 20, 30 [Link] fewer rotations compared to AVL Tree. /\
2 3
Before rotation: Disadvantages \
10 [Link] complex implementation. 4
\ [Link] perfectly balanced like AVL Tree. Rank of root increases.
20 Path Compression
\ Comparison Between AVL Tree and Red Black Tree Path Compression reduces tree height during Find operation
30 by making every node point directly to root.
Balance factor of 10 becomes -2. Feature AVL Tree Red Black Tree
Example
Perform Left Rotation. Balance Condition Strictly balanced Loosely balanced Before Path Compression:
After rotation: 1→2→3→4
Balancing Method Balance Factor Node Coloring
20 Find(1)=4
/ \ Height Smaller Slightly larger After Path Compression:
10 30 Search Operation Faster Slightly slower 4
[Link] Rotation /|\
Occurs when insertion is made in right subtree of left child. Insertion/Deletion More rotations Fewer rotations 1 2 3
Example Complexity Complex Less complex All nodes directly point to root.
Insert: Algorithm
Search Time 𝑂(log⁡ 𝑛) 𝑂(log⁡ 𝑛)
30, 10, 20 Find with Path Compression
Insertion Time 𝑂(log⁡ 𝑛) 𝑂(log⁡ 𝑛) FIND(x)
Before rotation: Deletion Time 𝑂(log⁡ 𝑛) 𝑂(log⁡ 𝑛) {
30 if(parent[x]!=x)
/ Database Linux kernel, STL parent[x]=FIND(parent[x]);
Applications
10 searching map
\ return parent[x];
20 Time Complexity }
Perform: Union by Rank
Operation Complexity
[Link] Rotation on 10 UNION(x,y)
[Link] Rotation on 30 Search 𝑂(log⁡ 𝑛) {
After rotation: Insertion 𝑂(log⁡ 𝑛) xroot=FIND(x);
20 yroot=FIND(y);
/ \ Deletion 𝑂(log⁡ 𝑛)
10 30 if(rank[xroot]<rank[yroot])
[Link] Rotation Applications parent[xroot]=yroot;
Occurs when insertion is made in left subtree of right child. 1.C++ STL map and set.
Example [Link] TreeMap and TreeSet. else if(rank[xroot]>rank[yroot])
Insert: [Link] process scheduling. parent[yroot]=xroot;
10, 30, 20 [Link] indexing.
else
Before rotation: Conclusion {
10 Red Black Tree is a self-balancing Binary Search Tree that parent[yroot]=xroot;
\ maintains balance using coloring properties and rotations. It rank[xroot]++;
30 provides efficient searching, insertion and deletion operations }
/ in 𝑂(log⁡ 𝑛)time and performs fewer rotations compared to }
20 AVL Tree. Time Complexity
Perform:
Operation Complexity
[Link] Rotation on 30
[Link] Rotation on 10 Find 𝑂(𝛼(𝑛))
After rotation: Union 𝑂(𝛼(𝑛))
20
/ \ Where:
10 30 𝛼(𝑛)
Time Complexity
is inverse Ackermann function, nearly constant time.
Operation Complexity
Insertion 𝑂(log⁡ 𝑛)
Deletion 𝑂(log⁡ 𝑛)
Searching 𝑂(log⁡ 𝑛)
[Link] Divide and Conquer paradigm with suitable [Link] Prim’s algorithm and construct Minimum [Link] Kruskal’s algorithm and construct Minimum
examples. Spanning Tree for a weighted graph. Spanning Tree for a weighted graph.
Divide and Conquer is an algorithm design technique in which Prim’s Algorithm is a Greedy method used to find Minimum Kruskal’s Algorithm is a Greedy method used to find
a problem is divided into smaller subproblems, solved Spanning Tree (MST) of a connected weighted graph. Minimum Spanning Tree (MST) of a weighted connected
recursively and then combined to obtain the final solution. A Minimum Spanning Tree is a spanning tree having minimum graph.
total edge weight. It repeatedly selects minimum weight edges without forming
Steps of Divide and Conquer Prim’s algorithm starts from any vertex and repeatedly selects cycles.
[Link] the minimum weight edge connecting visited and unvisited Algorithm
Break the problem into smaller subproblems. vertices. [Link] all edges in increasing order of weight.
[Link] Algorithm [Link] smallest edge.
Solve subproblems recursively. [Link] from any vertex. [Link] cycle is not formed, include the edge in MST.
[Link] [Link] minimum weight edge connected to visited vertex. [Link] until (V-1) edges are selected.
Combine solutions of subproblems to get final solution. [Link] selected edge and vertex to MST. Pseudocode
[Link] until all vertices are included. KRUSKAL(G)
General Form Pseudocode {
𝑛 PRIM(G,V) Sort edges in increasing order;
𝑇(𝑛) = 𝑎𝑇 ( ) + 𝑓(𝑛)
𝑏 {
Where: Select starting vertex; for each edge(u,v)
• 𝑎=number of subproblems {
while(all vertices not visited) if(u and v are in different sets)
• 𝑛/𝑏=size of each subproblem { {
• 𝑓(𝑛)=cost of dividing and combining
Find minimum edge connecting
visited and unvisited vertex;
Add edge(u,v) to MST;
Union(u,v);
}
Example 1: Merge Sort
Add edge to MST; }
Divide
} }
Split array into two halves.
} Example Graph
[38, 27, 43, 3]
Example 2
Consider the weighted graph: A-------B
↓
[38,27] [43,3] 2 |\ |
A-------B 6| \3 |5
|\ | | \ |
Conquer 6| \3 |5 | \ |
Recursively sort subarrays. | \ | C----D--E
[27,38] [3,43] | \ | 1 4
C----D--E Edges:
1 4
Edges: • CD=1
Combine
Merge sorted subarrays. • AB=2 • AB=2
[3, 27, 38, 43]
• AC=6 • AD=3

• AD=3 • DE=4
Recurrence Relation
𝑛 • CD=1 • BE=5
𝑇(𝑛) = 2𝑇 ( ) + 𝑛
Time Complexity:
2
• DE=4 • AC=6
Construction of MST
𝑂(𝑛log⁡ 𝑛)
• BE=5 Select edges in increasing order.
Step 1 Step 1
Example 2: Quick Sort Start from vertex A. Select CD=1
Divide Visited:𝐴 C------D
Choose pivot and partition array. Possible edges: 1
10, 80, 30, 90, 40, 50, 70 𝐴𝐵 = 2, 𝐴𝐶 = 6, 𝐴𝐷 = 3 Step 2
Choose minimum edge:𝐴𝐵 = 2 Select AB=2
Pivot = 70 MST:𝐴𝐵 A------B
After partition: Cost:2
10, 30, 40, 50, 70, 90, 80 C------D
Step 2 Step 3
Visited:𝐴, 𝐵 Select AD=3
Conquer Possible edges: A------B
Recursively sort left and right subarrays. 𝐴𝐷 = 3, 𝐴𝐶 = 6, 𝐵𝐸 = 5 \
Choose minimum edge:𝐴𝐷 = 3 \3
Combine MST:𝐴𝐵, 𝐴𝐷 \
No extra combine step needed. Cost:2 + 3 = 5 D
Step 3 /
Recurrence Relation Visited:𝐴, 𝐵, 𝐷 /
𝑛 Possible edges: C
𝑇(𝑛) = 2𝑇 ( ) + 𝑛 𝐷𝐶 = 1, 𝐷𝐸 = 4, 𝐵𝐸 = 5, 𝐴𝐶 = 6 Step 4
2
Average Complexity: Select DE=4
𝑂(𝑛log⁡ 𝑛) Choose minimum edge:𝐷𝐶 = 1 A------B
MST:𝐴𝐵, 𝐴𝐷, 𝐷𝐶 \
Worst Case: Cost:5 + 1 = 6 \3
𝑂(𝑛2 ) \
Step 4 D------E
Visited:𝐴, 𝐵, 𝐶, 𝐷 /
Example 3: Binary Search Possible edges:𝐷𝐸 = 4, 𝐵𝐸 = 5 /
Divide Choose minimum edge:𝐷𝐸 = 4 C
Find middle element. MST:𝐴𝐵, 𝐴𝐷, 𝐷𝐶, 𝐷𝐸 Now MST is completed.
Cost:6 + 4 = 10 Minimum Spanning Tree
Conquer 2
If key is smaller search left half. Minimum Spanning Tree A-------B
If key is larger search right half. 2 \
A-------B \3
Combine \ \
Not required. \3 D------E
\ /
Recurrence Relation D 1/
𝑛 /\ C
𝑇(𝑛) = 𝑇 ( ) + 1
2 1/ \4
Time Complexity: C E Total Minimum Cost
𝑂(log⁡ 𝑛) Total Minimum Cost [
2 + 3 + 1 + 4 = 10 1+2+3+4=10
Time Complexity ]
Implementation Complexity
Time Complexity
Adjacency Matrix 𝑂(𝑉 2 )
Operation Complexity
Priority Queue 𝑂(𝐸log⁡ 𝑉)
Sorting edges (O(E\log E))
Union-Find operations (O(E\log V))
Overall Complexity:
[
O(E\log E)
]
[Link] Prim’s and Kruskal’s algorithms. [Link] shortest path using Dijkstra’s algorithm for a [Link] Bellman Ford algorithm with suitable example
Prim’s Algorithm and Kruskal’s Algorithm are Greedy methods weighted graph. Show all steps. and compare it with Dijkstra’s algorithm.
used to find Minimum Spanning Tree (MST) of a weighted Dijkstra’s Algorithm is a Greedy algorithm used to find Bellman Ford Algorithm is used to find shortest path from a
connected graph. shortest path from a source vertex to all other vertices in a source vertex to all other vertices in a weighted graph. It
weighted graph with non-negative edge weights. works for graphs containing negative edge weights.
Prim’s Algorithm Algorithm It repeatedly relaxes all edges.
Prim’s algorithm starts from a vertex and repeatedly selects [Link] distance 0 to source vertex and infinity to all other Algorithm
the minimum weight edge connecting visited and unvisited vertices. [Link] source distance as 0 and all others as infinity.
vertices. [Link] vertex with minimum distance. [Link] all edges 𝑉 − 1times.
[Link] distances of adjacent vertices. [Link] for negative weight cycle.
Kruskal’s Algorithm [Link] selected vertex as visited. Relaxation Condition
Kruskal’s algorithm selects edges in increasing order of weight [Link] until all vertices are visited. If
without forming cycles. 𝑑𝑖𝑠𝑡[𝑢] + 𝑤(𝑢, 𝑣) < 𝑑𝑖𝑠𝑡[𝑣]
Pseudocode
Comparison Between Prim’s and Kruskal’s Algorithm DIJKSTRA(G,source) then update:
Kruskal’s { 𝑑𝑖𝑠𝑡[𝑣] = 𝑑𝑖𝑠𝑡[𝑢] + 𝑤(𝑢, 𝑣)
Feature Prim’s Algorithm Initialize distance[source]=0;
Algorithm
while(vertices remain) Pseudocode
Approach Vertex based Edge based { BELLMAN-FORD(G,source)
Starts from Select vertex u with minimum distance; {
Starting Point Starts from a vertex Mark u as visited; Initialize dist[source]=0;
smallest edge
for each adjacent vertex v for(i=1 to V-1)
Chooses minimum {
Chooses globally {
Selection edge connected to for each edge(u,v,w)
minimum edge if(dist[u]+weight(u,v)<dist[v])
visited vertex {
dist[v]=dist[u]+weight(u,v);
Cycle Checking Not required explicitly Required }}} if(dist[u]+w<dist[v])
Example Graph dist[v]=dist[u]+w;
Priority Queue/Min Disjoint Set
Data Structure 10 }}
Heap (Union-Find)
A--------B for each edge(u,v,w)
Suitable For Dense graphs Sparse graphs |\ | {
Connected or 5| \3 |1 if(dist[u]+w<dist[v])
Graph | \ | print("Negative cycle exists");
Connected graph disconnected
Requirement | \ | }}
graph
C----D---E Example Graph
Edge Sorting Not necessary Necessary 4
2 4
(O(V^2)) or (O(E\log Edges:AB=10,AC=5,AD=3,CD=2,BE=1,DE=4 A-----B
Time Complexity (O(E\log E))
V)) Source Vertex = A | |
Stepwise Solution 5| -2
Single tree grows Different trees
Tree Growth Step 1 Step 2 | |
continuously merge together
Start from A. Visit A. C-----D
Implementation Simpler Slightly complex Update adjacent vertices: 3
Vertex Distance
[B=10, C=5, D=3] Edges:
•
Example A 0
Vertex Distance AB=4
Prim’s Algorithm B ∞
Starts from a vertex and expands MST gradually.
C ∞
A 0 • AC=5
A------B
\ D ∞
B 10
• BD=-2
•
C 5
\ E ∞ CD=3
D---C D 3 Source Vertex = A
E ∞ Step 1: Initialization
Kruskal’s Algorithm
Vertex Distance
Chooses edges globally in increasing order.
[Link] smallest edge Step 3 Step 4 A 0
[Link] cycle Choose minimum Choose vertex C.
B ∞
[Link] until MST formed distance vertex D. No shorter path found.
Update E through D: Vertex Distance C ∞
Advantages of Prim’s Algorithm [E=3+4=7] D ∞
Update C through D: A 0
[Link] implementation.
[3+2=5] Step 2: First Relaxation
[Link] for dense graphs. B 10
From A:
[Link] explicit cycle detection. Vertex Distance C 5 𝐵 = 4, 𝐶 = 5
A 0 D 3
Advantages of Kruskal’s Algorithm From B:
[Link] for sparse graphs. B 10 E 7 𝐷 = 4 + (−2) = 2
[Link] edge-based approach. C 5
[Link] well with disjoint sets. Vertex Distance
D 3 A 0
Disadvantages of Prim’s Algorithm E 7 B 4
[Link] efficient for sparse graphs.
[Link] connected graph. C 5
Step 5
Choose vertex E. D 2
Disadvantages of Kruskal’s Algorithm
Update B through E: Step 3: Second Relaxation
[Link] sorting required.
[ No shorter distance found.
[Link] detection needed.
7+1=8 Final distances remain same.
] Final Shortest Distances
Applications
[Link] design. Vertex Distance Vertex Shortest Distance from A
[Link] and railway systems. A 0 A 0
[Link] networks.
[Link] wiring systems. B 8 B 4
C 5 C 5
Conclusion
D 3 D 2
Prim’s algorithm grows MST from a starting vertex, whereas
Kruskal’s algorithm builds MST by selecting minimum weight E 7 Time Complexity𝑂(𝑉𝐸)
edges without forming cycles. Both algorithms are Greedy Where:
Final Shortest Distances
methods used for constructing Minimum Spanning Tree
efficiently. Vertex Shortest Distance from A • 𝑉=number of vertices
A 0 • 𝐸=number of edges
B 8 Comparison Between Bellman Ford and Dijkstra Algorithm
Feature Bellman Ford Dijkstra
C 5
Negative Edge
D 3 Supported Not supported
Weights
E 7
Negative Cycle
Possible Not possible
Detection
Shortest Paths
Dynamic
• A→D=3
Approach
Programming
Greedy

• A→C=5 Time Complexity 𝑂(𝑉𝐸) 𝑂(𝑉 2 )or 𝑂(𝐸log⁡ 𝑉)

• A→D→E=7 Efficiency Slower Faster

• A→D→E→B=8 Applications
Graphs with
negative weights
Graphs with non-
negative weights
[Link] Huffman Tree for given character frequencies [Link] Fractional Knapsack problem using Greedy [Link] Matrix Chain Multiplication problem using Dynamic
and generate Huffman codes. method with suitable example. Programming and obtain optimal parenthesization.
Huffman Coding is a Greedy algorithm used for lossless data Fractional Knapsack is a Greedy method used to maximize Matrix Chain Multiplication (MCM) is a Dynamic
compression. It assigns variable length binary codes to total profit in a knapsack of limited capacity. In this method, Programming technique used to find the minimum number of
characters based on frequency. fractions of items can be included. scalar multiplications needed to multiply a chain of matrices.
Characters with smaller frequency get longer codes and Items are selected according to maximum Profit/Weight ratio. The order of multiplication affects computation cost.
characters with higher frequency get shorter codes. Algorithm Problem Statement
Algorithm [Link] Profit/Weight ratio for each item. Given matrices:
[Link] a leaf node for each character. [Link] items in decreasing order of ratio. 𝐴1 , 𝐴2 , 𝐴3 , … , 𝐴𝑛
[Link] all nodes into priority queue. [Link] item completely if capacity allows.
[Link] two nodes with minimum frequency. [Link] capacity is insufficient, select fractional part of item. Find optimal parenthesization with minimum multiplication
[Link] new internal node with sum of frequencies. [Link] until knapsack becomes full. cost.
[Link] new node again into queue. Pseudocode Algorithm
[Link] until one node remains. FRACTIONAL-KNAPSACK(W,items,n) [Link] minimum multiplication cost in DP table.
[Link] binary codes from Huffman Tree. { [Link] all possible positions of parenthesis.
Pseudocode Sort items by profit/weight ratio; [Link] minimum cost.
HUFFMAN(C) for(i=1 to n) [Link] optimal parenthesization.
{ { Recurrence Relation
Create leaf nodes for all characters; if(item weight <= W) 𝑚[𝑖, 𝑗] = min⁡{𝑚[𝑖, 𝑘] + 𝑚[𝑘 + 1, 𝑗] + 𝑝𝑖−1 𝑝𝑘 𝑝𝑗 }
Insert nodes into priority queue; { Where:
while(queue size > 1)
{
Select complete item;
W=W-item weight; • 𝑚[𝑖, 𝑗]=minimum multiplication cost
x=Extract-Min(); } • 𝑝=matrix dimensions
y=Extract-Min(); else Pseudocode
z=New Node(); { MATRIX-CHAIN(p,n)
[Link]=x; Select fractional part; {
[Link]=y; break; for(i=1 to n)
[Link]=[Link]+[Link]; }}} m[i,i]=0;
Insert(z); Example
} Knapsack Capacity: for(L=2 to n)
return root; 𝑊 = 50 {
} Given items: for(i=1 to n-L+1)
Item Profit Weight P/W Ratio {
Example j=i+L-1;
Given characters and frequencies: 1 60 10 6
m[i,j]=∞;
Character Frequency 2 100 20 5
3 120 30 4 for(k=i to j-1)
A 5
{
B 9 Step 1: Sort by Profit/Weight Ratio q=m[i,k]+m[k+1,j]
Order: +p[i-1]*p[k]*p[j];
C 12 𝐼𝑡𝑒𝑚1, 𝐼𝑡𝑒𝑚2, 𝐼𝑡𝑒𝑚3
D 13 if(q<m[i,j])
Step 2: Fill Knapsack
E 16 m[i,j]=q;
Select Item 1
}
F 45 Weight:
}
10
}
Step 1 Step 2 }
Profit:
Select two minimum Select: Example
60
frequencies: 12(𝐶),13(𝐷) Given matrices:
5(𝐴),9(𝐵) Matrix Order
Remaining Capacity:
Combine:
50 − 10 = 40 A₁ 10×30
Combine: 25
14 A₂ 30×5
Select Item 2 A₃ 5×60
Weight: Dimension array:
20 𝑝 = [10,30,5,60]
Step 3 Step 4
Select: Select: Profit: Step 1: Compute Cost
14,16(𝐸) 25,30 100 Parenthesization 1
Combine: Combine: (𝐴1 𝐴2 )𝐴3
Remaining Capacity:
30 55 40 − 20 = 20 Cost:
(10 × 30 × 5) + (10 × 5 × 60)
Step 5 1500 + 3000 = 4500
Select Fraction of Item 3
Select: Available capacity:
45(𝐹),55 Parenthesization 2
20 𝐴1 (𝐴2 𝐴3 )
Combine: Item weight:
100 Cost:
30 (30 × 5 × 60) + (10 × 30 × 60)
Root node obtained. 9000 + 18000 = 27000
Fraction selected:
Huffman Tree 20 2
100 = Minimum Cost
30 3 4500
/ \
F45 55 Profit obtained:
/ \ Optimal Parenthesization
2
25 30 120 × = 80 (𝐴1 𝐴2 )𝐴3
3
/\ /\
DP Table
C12 D13 14 E16
/\ Total Profit i/j 1 2 3
A5 B9 60 + 100 + 80 = 240 1 0 1500 4500
Huffman Codes
Assign: 2 0 9000

• Left edge = 0
Final Selection 3 0
Item Selected Portion
• Right edge = 1
1 Complete Time Complexity
Character Code 𝑂(𝑛3 )
2 Complete
F 0
2
C 100 3
3 Space Complexity
D 101 𝑂(𝑛2 )
Time Complexity
A 1100
Operation Complexity
B 1101
Sorting 𝑂(𝑛log⁡ 𝑛)
E 111
Selection 𝑂(𝑛)
Time Complexity Overall Complexity:
𝑂(𝑛log⁡ 𝑛) 𝑂(𝑛log⁡ 𝑛)
__________________________________________________
where 𝑛is number of characters.
[Link] Longest Common Subsequence (LCS) for two given [Link] 0/1 Knapsack problem using Dynamic [Link] Floyd Warshall algorithm for all-pairs shortest
strings using Dynamic Programming. Programming. path problem with example.
Longest Common Subsequence (LCS) is the longest sequence 0/1 Knapsack is a Dynamic Programming problem used to Floyd Warshall Algorithm is a Dynamic Programming
that appears in the same order in two strings but not maximize total profit without exceeding knapsack capacity. algorithm used to find shortest paths between all pairs of
necessarily consecutively. In this problem: vertices in a weighted graph.
Dynamic Programming is used to avoid repeated
• An item is either selected completely or not
It works for:
computations.
selected. • Positive edge weights
Algorithm • Fractional selection is not allowed. • Negative edge weights
[Link] DP table. but does not work for negative cycles.
[Link] characters of both strings. Algorithm Algorithm
[Link] characters match: [Link] DP table. [Link] distance matrix from graph.
𝐿[𝑖][𝑗] = 𝐿[𝑖 − 1][𝑗 − 1] + 1 [Link] item weight is less than capacity: [Link] each vertex as intermediate vertex.

[Link] characters do not match: • Include item

[Link] shortest distances using:
𝐷[𝑖][𝑗] = min⁡(𝐷[𝑖][𝑗], 𝐷[𝑖][𝑘] + 𝐷[𝑘][𝑗])
𝐿[𝑖][𝑗] = max⁡(𝐿[𝑖 − 1][𝑗], 𝐿[𝑖][𝑗 − 1]) • Exclude item
[Link] for all vertices.
[Link] until table is completed. • Select maximum profit Recurrence Relation
[Link] item weight is greater than capacity: 𝐷[𝑖][𝑗] = min⁡(𝐷[𝑖][𝑗], 𝐷[𝑖][𝑘] + 𝐷[𝑘][𝑗])
Recurrence Relation
0 𝑖 = 0 𝑜𝑟 𝑗 = 0 • Exclude item
Pseudocode
FLOYD-WARSHALL(W,n)
𝐿[𝑖 − 1, 𝑗 − 1] + 1 𝑥𝑖 = 𝑦𝑗 [Link] until table is completed.
𝐿[𝑖, 𝑗] = { {
max⁡(𝐿[𝑖 − 1, 𝑗], 𝐿[𝑖, 𝑗 − 1]) 𝑥𝑖 ≠ 𝑦𝑗 D=W;
Recurrence Relation
𝐾[𝑖, 𝑤]
Pseudocode 0 𝑖 = 0 𝑜𝑟 𝑤 = 0 for(k=1 to n)
LCS(X,Y,m,n) = {max⁡(𝑝𝑖 + 𝐾[𝑖 − 1, 𝑤 − 𝑤𝑖 ], 𝐾[𝑖 − 1, 𝑤]) 𝑤𝑖 ≤ 𝑤 {
{ 𝐾[𝑖 − 1, 𝑤] 𝑤𝑖 > 𝑤 for(i=1 to n)
for(i=0 to m) Where: {
L[i][0]=0; for(j=1 to n)
• 𝐾[𝑖, 𝑤]=maximum profit {
for(j=0 to n)
L[0][j]=0;
• 𝑝𝑖 =profit of item
D[i][j]=min(D[i][j],
D[i][k]+D[k][j]);
• 𝑤𝑖 =weight of item }}}}
for(i=1 to m) Example
{ Pseudocode Initial weighted graph:
for(j=1 to n) KNAPSACK(W,wt,p,n) 3
{ { A-----B
if(X[i]==Y[j]) for(i=0 to n) | |
L[i][j]=L[i-1][j-1]+1; { 8| |2
for(w=0 to W) | |
else { C-----D
L[i][j]=max(L[i-1][j],L[i][j-1]); if(i==0 || w==0) 1
} K[i][w]=0; Edges:
}
} else if(wt[i]<=w)
• AB=3
K[i][w]=max(p[i]+K[i-1][w-wt[i]], • AC=8
Example K[i-1][w]);
String 1: • BD=2
𝑋 = 𝐴𝐵𝐶𝐵𝐷𝐴𝐵 else
K[i][w]=K[i-1][w];
• CD=1
Initial Distance Matrix
String 2: }
𝑌 = 𝐵𝐷𝐶𝐴𝐵𝐴 } A B C D
} A 0 3 8 ∞

DP Table B ∞ 0 ∞ 2
Example
0 B D C A B A Knapsack Capacity: C ∞ ∞ 0 1
𝑊=5 D ∞ ∞ ∞ 0
0 0 0 0 0 0 0 0
A 0 0 0 0 1 1 1 Given items: Using Vertex B as Intermediate
Update:
B 0 1 1 1 1 2 2 Item Weight Profit 𝐴→𝐵→𝐷
C 0 1 1 2 2 2 2 1 1 6 3+2=5

B 0 1 1 2 2 3 3 2 2 10
So,
D 0 1 2 2 2 3 3 3 3 12 𝐷[𝐴][𝐷] = 5
A 0 1 2 2 3 3 4
DP Table Updated matrix:
B 0 1 2 2 3 4 4 A B C D
Item/Weight 0 1 2 3 4 5
0 0 0 0 0 0 0 A 0 3 8 5
Longest Common Subsequence
𝐵𝐶𝐵𝐴 1 0 6 6 6 6 6 B ∞ 0 ∞ 2

2 0 6 10 16 16 16 C ∞ ∞ 0 1
Length:
4 3 0 6 10 16 18 22 D ∞ ∞ ∞ 0
Using Vertex D as Intermediate
Maximum Profit Update:
Time Complexity 22 𝐴→𝐷→𝐶
𝑂(𝑚𝑛) 5+1= 6

Where: Selected Items So,

• 𝑚=length of first string • Item 2 Final matrix:
𝐷[𝐴][𝐶] = 6

• 𝑛=length of second string • Item 3 A B C D

Total Weight: A 0 3 6 5
Space Complexity 2+3=5
𝑂(𝑚𝑛) B ∞ 0 ∞ 2
Total Profit: C ∞ ∞ 0 1
10 + 12 = 22 D ∞ ∞ ∞ 0
Final Shortest Distances
Time Complexity
𝑂(𝑛𝑊)
• A→B=3
• A→C=6
Where:
• A→D=5
• 𝑛=number of items
• B→D=2
• 𝑊=knapsack capacity
• C→D=1
Time Complexity
Space Complexity
𝑂(𝑛3 )
𝑂(𝑛𝑊)
Space Complexity
𝑂(𝑛2 )
[Link] Optimal Binary Search Tree using Dynamic [Link] Maximum Flow problem and Max-flow Min-cut [Link] Naive String Matching algorithm with suitable
Programming. theorem. example.
Optimal Binary Search Tree (OBST) is a Binary Search Tree Maximum Flow problem is used to find the maximum Naive String Matching algorithm is the simplest method used
constructed in such a way that the expected search cost is possible flow from a source vertex to a sink vertex in a flow to find occurrence of a pattern in a given text.
minimum. network. The pattern is compared with the text character by character
It is used when probabilities of searching keys are known. A flow network is a directed graph where each edge has a at every possible position.
Dynamic Programming is used to minimize total search cost. capacity.
Algorithm Terminology Algorithm
[Link] search frequencies of keys.
[Link] each key as root one by one. • Source(𝑆) → starting vertex
[Link] pattern with beginning of text.
[Link] characters one by one.
[Link] cost of left and right subtrees recursively. • Sink(𝑇) → destination vertex [Link] mismatch occurs, shift pattern by one position.
[Link] root with minimum total cost. [Link] until pattern is found or text ends.
Recurrence Relation • Capacity → maximum flow allowed through
𝑗
𝐶𝑜𝑠𝑡(𝑖, 𝑗) = min⁡𝑟=𝑖 [𝐶𝑜𝑠𝑡(𝑖, 𝑟 − 1) + 𝐶𝑜𝑠𝑡(𝑟 + 1, 𝑗)] edge Pseudocode

+∑
𝑗
𝑓𝑘 • Flow → actual amount passing through edge NAIVE-STRING-MATCH(T,P)
{
𝑘=𝑖 Max Flow Condition
Where: For every edge: n=length(T);

• 0 ≤ 𝑓(𝑢, 𝑣) ≤ 𝑐(𝑢, 𝑣) m=length(P);

𝑓𝑘 =frequency of key
• 𝑟=selected root Where: for(i=0;i<=n-m;i++)
{
Pseudocode
OBST(keys,freq,n)
• 𝑓(𝑢, 𝑣)=flow j=0;
{ • 𝑐(𝑢, 𝑣)=capacity
while(j<m && T[i+j]==P[j])
for(i=1 to n) Flow Conservation
cost[i][i]=freq[i]; j++;
For every intermediate vertex:
for(L=2 to n) 𝐼𝑛𝑐𝑜𝑚𝑖𝑛𝑔 𝐹𝑙𝑜𝑤 = 𝑂𝑢𝑡𝑔𝑜𝑖𝑛𝑔 𝐹𝑙𝑜𝑤
{ if(j==m)
Ford-Fulkerson Algorithm
for(i=1 to n-L+1) print("Pattern found");
Ford-Fulkerson method is used to find maximum flow.
{ }
It repeatedly finds augmenting paths from source to sink and
j=i+L-1; }
increases flow.
cost[i][j]=∞; Algorithm
for(r=i to j) Example
[Link] flow as 0.
{ Text:
[Link] augmenting path from source to sink.
c=cost[i][r-1] 𝑇 = 𝐴𝐵𝐴𝐵𝐷𝐴𝐵𝐴𝐶𝐷𝐴𝐵𝐴𝐵𝐶𝐴𝐵𝐴𝐵
[Link] minimum residual capacity in path.
+cost[r+1][j] [Link] flow to all edges in path.
+sum(freq,i,j); Pattern:
[Link] until no augmenting path exists.
if(c<cost[i][j]) 𝑃 = 𝐴𝐵𝐴𝐵𝐶𝐴𝐵𝐴𝐵
Pseudocode
cost[i][j]=c; FORD-FULKERSON(G,S,T)
}}}} {
Matching Process
Example maxflow=0;
Shift 1
Given keys and frequencies: while(augmenting path exists)
ABABDABACDABABCABAB
Key Frequency {
ABABCABAB
pathflow=minimum residual capacity;
10 4 Mismatch occurs.
for each edge in path
20 2 update residual capacities;
Shift 2
30 6 maxflow=maxflow+pathflow;
ABABDABACDABABCABAB
}
Step 1 ABABCABAB
return maxflow;
Single key costs: Mismatch occurs.
}
Key Cost Example
Continue Shifting
10
10 4 Pattern is shifted one position each time.
S--------A
20 2 | \
Final Match
30 6 5| \10
ABABDABACDABABCABAB
| \
Step 2 ABABCABAB
B------------T
Two key combinations: Pattern found at position:
15
Keys(10,20) 10
Capacities:
If 10 is root:
0 + 2 + (4 + 2) = 8 • S→A = 10
Time Complexity
If 20 is root:
4 + 0 + (4 + 2) = 10 • S→B = 5
Case Complexity
Minimum cost: • A→T = 10 Best Case 𝑂(𝑛)
8
Keys(20,30) • B→T = 15 Worst Case 𝑂(𝑛𝑚)
If 20 is root: Step 1
Where:
0 + 6 + (2 + 6) = 14 Augmenting path:
If 30 is root: 𝑆→𝐴→𝑇 • 𝑛=length of text
•
2 + 0 + (2 + 6) = 10 Minimum capacity:
Minimum cost: min⁡(10,10) = 1 𝑚=length of pattern
10 Flow added:
Step 3 10 Space Complexity
All keys(10,20,30) Step 2 𝑂(1)
If 10 is root: Augmenting path:
0 + 10 + 12 = 22 𝑆→𝐵→𝑇
Minimum capacity: Advantages
If 20 is root: min⁡(5,15) = 5 [Link] and easy to implement.
4 + 6 + 12 = 22 Flow added: [Link] preprocessing required.
5 [Link] less memory.
If 30 is root: Maximum Flow
8 + 0 + 12 = 20 10 + 5 = 15 Disadvantages
Final Flow Network [Link] for large texts.
Minimum cost: 10/10 [Link] comparisons increase complexity.
20 S----------A
| \ Applications
Optimal Binary Search Tree 5/5| \10/10 [Link] text searching.
30 | \ [Link] matching.
/ B----------------T [Link] editors.
10 5/15
\ Max-Flow Min-Cut Theorem Conclusion
20 The maximum value of flow from source to sink is equal to Naive String Matching algorithm searches a pattern by
Minimum Cost minimum capacity that, when removed, disconnects source comparing characters at every possible position in the text
20 and sink. and is simple but inefficient for large inputs.
𝑀𝑎𝑥𝑖𝑚𝑢𝑚 𝐹𝑙𝑜𝑤 = 𝑀𝑖𝑛𝑖𝑚𝑢𝑚 𝐶𝑢𝑡
Time Complexity Time Complexity
𝑂(𝑛3 ) Algorithm Complexity

Space Complexity Ford-Fulkerson 𝑂(𝐸 × 𝑀𝑎𝑥𝐹𝑙𝑜𝑤)

𝑂(𝑛2 )
[Link] Rabin-Karp string matching algorithm with [Link] Knuth-Morris-Pratt (KMP) algorithm with [Link] String Matching using Finite Automata method.
suitable example. construction of LPS table. Finite Automata String Matching is a pattern matching
Rabin-Karp Algorithm is a string matching algorithm that uses Knuth-Morris-Pratt (KMP) Algorithm is an efficient string technique that uses Finite Automaton to search a pattern in a
hashing technique to find a pattern in a text. matching algorithm used to find a pattern in a text. text efficiently.
Instead of comparing all characters repeatedly, it compares It avoids unnecessary comparisons using LPS (Longest Prefix The automaton changes states according to input characters
hash values of pattern and text substring. Suffix) table. and detects pattern occurrence.

Algorithm LPS (Longest Prefix Suffix) Finite Automaton

[Link] hash value of pattern. LPS value indicates the length of longest proper prefix which Finite Automaton consists of:
[Link] hash value of first text window.
[Link] hash values.
is also suffix.
It helps to skip already matched characters. • States
[Link] hash values match, compare characters. • Input symbols
[Link] pattern by one position and calculate new hash using Algorithm
rolling hash. [Link] LPS table for pattern. • Transition function
[Link] until end of text. [Link] pattern with text.
[Link] characters match, continue.
• Initial state

Hash Function [Link] mismatch occurs: • Final state

Where:
𝐻 = (𝑑(𝐻 − 𝑐 × ℎ) + 𝑛𝑒𝑥𝑡) 𝑚𝑜𝑑 𝑞
• Use LPS value
When final state is reached, pattern is found.

• 𝑑=number system base • Shift pattern efficiently Algorithm

[Link] until pattern is found. [Link] Finite Automaton for the pattern.
• 𝑞=prime number [Link] from initial state.
[Link] text character one by one.
• ℎ=highest power value
Pseudocode
KMP(T,P) [Link] state using transition function.
{ [Link] final state is reached, pattern occurs.
Pseudocode
Compute LPS array;
RABIN-KARP(T,P,d,q) Transition Function
{ Transition function determines next state based on:
i=0;
Calculate hash of pattern and text;
j=0; • Current state
for(i=0 to n-m)
{
while(i<n) • Input character
{
if(pattern hash == text hash)
if(T[i]==P[j]) Pseudocode
{
{ FINITE-AUTOMATA-MATCH(T,δ,m)
Compare characters;
i++; {
}
j++; q=0;
}
Calculate next hash value; for(i=1 to n)
}
if(j==m) {
}
print("Pattern found"); q=δ(q,T[i]);
Example
else if(i<n && T[i]!=P[j]) if(q==m)
Text:
{ print("Pattern found");
𝑇 = 𝐴𝐵𝐶𝐶𝐷𝐷𝐴𝐸𝐹𝐺
if(j!=0) }
j=LPS[j-1]; }
Pattern:
Where:
𝑃 = 𝐶𝐷𝐷
else
i++;
• 𝛿=transition function

Step 1
} • 𝑞=current state
•
}
Calculate hash value of pattern: 𝑚=pattern length
}
𝐻𝑎𝑠ℎ(𝐶𝐷𝐷)
Example Example
Calculate hash of first text window: Text:
Text:
𝐴𝐵𝐶 𝑇 = 𝐴𝐴𝐵𝐴𝐴𝐶𝐴𝐴𝐷𝐴𝐴𝐵𝐴𝐴𝐵𝐴
𝑇 = 𝐴𝐵𝐴𝐵𝐷𝐴𝐵𝐴𝐶𝐷𝐴𝐵𝐴𝐵𝐶𝐴𝐵𝐴𝐵
Hash mismatch. Pattern:
Pattern:
𝑃 = 𝐴𝐵𝐴𝐵𝐶𝐴𝐵𝐴𝐵 𝑃 = 𝐴𝐴𝐵𝐴
Step 2
Shift window:
𝐵𝐶𝐶 States
Construction of LPS Table
Pattern: 𝑞0 , 𝑞1 , 𝑞2 , 𝑞3 , 𝑞4
Hash mismatch.
𝐴𝐵𝐴𝐵𝐶𝐴𝐵𝐴𝐵
Where:
Step 3
Shift window: Index 0 1 2 3 4 5 6 7 8 • 𝑞0 =initial state
𝐶𝐶𝐷 Character A B A B C A B A B • 𝑞4 =final state
Hash mismatch. LPS 0 0 1 2 0 1 2 3 4
Transition Diagram
q0 --A--> q1
Step 4 Matching Process
q1 --A--> q2
Shift window: Compare pattern with text.
q2 --B--> q3
𝐶𝐷𝐷 Mismatch occurs after partial matching.
q3 --A--> q4
Instead of restarting from beginning, KMP uses LPS table to
Hash matches. skip unnecessary comparisons.
Matching Process
Now compare characters. Pattern found at position:
Read text characters one by one.
Pattern found successfully. 10
When automaton reaches final state 𝑞4 , pattern is found.
Pattern found at positions:
Pattern Occurrence
0, 9, 12
Pattern found at position: Time Complexity
4 Operation Complexity
LPS Construction 𝑂(𝑚) Time Complexity
Rolling Hash Pattern Matching 𝑂(𝑛) Operation Complexity
New hash value is calculated efficiently without recomputing Automaton Construction (O(m^3
Overall Complexity:
all characters.
𝑂(𝑛 + 𝑚) Pattern Matching 𝑂(𝑛)
Time Complexity Where:
Where:
Case Complexity
• 𝑛=length of text
• 𝑛=text length
Best/Average Case 𝑂(𝑛 + 𝑚)
• 𝑚=length of pattern
• 𝑚=pattern length
Worst Case 𝑂(𝑛𝑚)
• ∣ Σ ∣=alphabet size
Where: Space Complexity
• 𝑛=length of text 𝑂(𝑚) Space Complexity
𝑂(𝑚 ∣ Σ ∣)
• 𝑚=length of pattern

Space Complexity
𝑂(1)
[Link] Naive, Rabin-Karp and KMP string matching [Link] 4-Queen problem using Backtracking and draw the [Link] Hamiltonian Circuit problem using Backtracking.
algorithms. state space tree. Hamiltonian Circuit is a cycle in a graph that visits every
Naive, Rabin-Karp and KMP are important string matching N-Queen problem is a Backtracking problem in which vertex exactly once and returns to the starting vertex.
algorithms used to find occurrence of a pattern in a text. 𝑁queens are placed on an 𝑁 × 𝑁chessboard such that no Backtracking is used to explore all possible paths and reject
two queens attack each other. invalid paths.
Naive String Matching Conditions:
In Naive algorithm, pattern is compared with text at every
possible position character by character. • No two queens in same row
Algorithm
[Link] from any vertex.
• No two queens in same column [Link] next unvisited adjacent vertex.
Rabin-Karp Algorithm [Link] whether vertex is safe.
Rabin-Karp algorithm uses hashing technique and compares • No two queens in same diagonal [Link] all vertices are visited and last vertex connects to first
hash values instead of comparing all characters repeatedly. vertex, solution exists.
Algorithm [Link] no valid vertex exists, backtrack.
KMP Algorithm [Link] queen row by row.
KMP algorithm uses LPS(Longest Prefix Suffix) table to avoid [Link] whether current position is safe. Conditions for Safe Vertex
unnecessary comparisons. [Link] safe, place queen. A vertex is safe if:
[Link] conflict occurs, backtrack and try another position. [Link] is adjacent to previous vertex.
Comparison Between Naive, Rabin-Karp and KMP [Link] until all queens are placed. [Link] is not already included in path.
Algorithms
Pseudocode Pseudocode
Naive Rabin-Karp KMP
Feature NQUEEN(k,n) HAM-CYCLE(pos)
Algorithm Algorithm Algorithm
{ {
Direct for(i=1 to n) if(pos==n)
Technique Used Hashing LPS table
comparison { {
Not Hash LPS if(SAFE(k,i)) if(graph[path[pos-1]][path[0]]==1)
Preprocessing { return true;
required computation construction
x[k]=i;
One
Using rolling Using LPS else
Pattern Shift position at a if(k==n)
hash values return false;
time print(x); }
Repeated
More Less Very less else
Comparisons for(v=1 to n-1)
NQUEEN(k+1,n); {
Best Case 𝑂(𝑛) 𝑂(𝑛 + 𝑚) 𝑂(𝑛 + 𝑚) } if(ISSAFE(v,pos))
Worst Case 𝑂(𝑛𝑚) 𝑂(𝑛𝑚) 𝑂(𝑛 + 𝑚) } {
Space } path[pos]=v;
𝑂(1) 𝑂(1) 𝑂(𝑚)
Complexity
Example : 4-Queen Problem if(HAM-CYCLE(pos+1)==true)
Efficiency Low Moderate High Place 4 queens on 4 × 4chessboard. return true;
Not
Hash Collision Possible Not possible Solution
applicable path[pos]=-1;
One valid arrangement: }
Complexity of
Simple Moderate Complex Row Column }
Implementation
return false;
Multiple 1 2
}
Suitable For Small texts pattern Large texts 2 4
search Example Graph
3 1
Where: A------B
4 3
•
|\ |
𝑛=length of text | \ |
• 𝑚=length of pattern Chessboard Representation | \ |
_Q__ D------C
Example ___Q Edges:
Text: Q___
__Q_
• A-B
𝑇 = 𝐴𝐵𝐴𝐵𝐷𝐴𝐵𝐴𝐶𝐷𝐴𝐵𝐴𝐵𝐶𝐴𝐵𝐴𝐵
Where: • B-C
Pattern:
𝑃 = 𝐴𝐵𝐴𝐵𝐶𝐴𝐵𝐴𝐵
• Q = Queen • C-D
• _ = Empty position • D-A
•
All algorithms search the same pattern but differ in efficiency.
State Space Tree A-C
Advantages of Naive Algorithm Start
[Link] and easy to implement. / | | \ Hamiltonian Circuit
[Link] preprocessing required. Q1 Q2 Q3 Q4 One valid Hamiltonian Circuit is:
| 𝐴→𝐵→𝐶→𝐷→𝐴
Advantages of Rabin-Karp Algorithm Q4
[Link] hashing technique. |
[Link] for multiple pattern matching. Q1 Path Representation
| Position Vertex
Advantages of KMP Algorithm Q3
1 A
[Link] repeated comparisons. Solution obtained:
[Link] among these algorithms. (2, 4, 1, 3) 2 B
[Link] time complexity. 3 C

Disadvantages Working of Backtracking 4 D

Naive Algorithm [Link] queen in first row. 5 A
[Link] time complexity. [Link] safe positions in next row.
[Link] comparisons. [Link] no safe position exists, backtrack. State Space Tree
Rabin-Karp Algorithm [Link] another column. A
[Link] collision possible. [Link] until solution is found. / | \
[Link] case complexity high. B C D
KMP Algorithm Time Complexity |
[Link] construction required. 𝑂(𝑁!)
C
[Link] complex implementation. |
D
Applications Space Complexity
|
[Link] editors. 𝑂(𝑁)
A
[Link] engines. Solution Path:
[Link] sequence matching. 𝐴→𝐵→𝐶→𝐷→𝐴
[Link] searching systems.

Conclusion Working of Backtracking

Naive algorithm is simple but inefficient, Rabin-Karp improves [Link] starting vertex.
searching using hashing, and KMP provides the most efficient [Link] adjacent unvisited vertices.
string matching using LPS table with linear time complexity. [Link] dead end occurs, backtrack.
[Link] another vertex.
[Link] until Hamiltonian Circuit is found.

Time Complexity
𝑂(𝑁!)
Space Complexity
𝑂(𝑁)
[Link] Subset Sum problem using Backtracking and draw [Link] state space tree for Backtracking problems. [Link] Travelling Salesman Problem using Branch and
state space tree. State Space Tree is a tree representation of all possible Bound technique.
Subset Sum problem is a Backtracking problem in which a solutions in a Backtracking problem. Travelling Salesman Problem (TSP) is a problem in which a
subset of given numbers is selected such that the sum of Each node represents a state of the solution, and branches salesman visits every city exactly once and returns to the
selected elements becomes equal to a given target sum. represent choices. starting city with minimum travelling cost.
Backtracking explores the tree systematically and rejects Branch and Bound technique is used to reduce unnecessary
Problem Statement invalid states. paths and find optimal solution efficiently.
Given a set of positive integers and a target sum 𝑀,
determine whether a subset exists whose sum is equal to 𝑀. Components of State Space Tree Algorithm
[Link] Node [Link] from initial city.
Algorithm Represents initial state. [Link] possible paths(branching).
[Link] with empty subset. [Link] Node [Link] lower bound cost for each path.
[Link] or exclude each element. Represents partial solution. [Link] path with minimum bound.
[Link] current sum. [Link] Node [Link] paths with higher cost.
[Link] current sum equals target sum, solution found. Represents complete solution. [Link] until optimal tour is obtained.
[Link] current sum exceeds target sum, backtrack. [Link] Node
[Link] until all possibilities are explored. Represents invalid solution. Cost Matrix
[Link] Node A B C D
Pseudocode Represents node that can generate further children.
SUBSET(k,sum) A ∞ 10 15 20
{ Working of Backtracking using State Space Tree B 5 ∞ 9 10
if(sum==M) [Link] from root node.
C 6 13 ∞ 12
print(solution); [Link] child nodes.
[Link] whether node is valid. D 8 8 9 ∞
else [Link] node is invalid, backtrack.
{ [Link] node is valid, continue exploration. Step 1: Start from City A
for(i=k+1;i<=n;i++) [Link] until solution is found. Possible paths:
{ 𝐴→𝐵
if(sum+w[i]<=M) Example : 4-Queen Problem 𝐴→𝐶
{ Start 𝐴→𝐷
x[i]=1; / | | \
SUBSET(i,sum+w[i]); Q1 Q2 Q3 Q4 Choose minimum cost edge:
x[i]=0; | 𝐴 → 𝐵 = 10
} Q4
} |
} Q1 Step 2
} | From B select minimum unvisited city:
Where: Q3 𝐵 → 𝐷 = 10
• 𝑤[𝑖]=elements of set
Solution:
(2, 4, 1, 3) Path:
• 𝑀=target sum 𝐴→𝐵→𝐷

• 𝑥[𝑖]=selection array Example : Subset Sum Problem

Given set: Step 3
Example {5, 10, 12} From D:
Given set: 𝐷→𝐶=9
{5, 10, 12, 13, 15, 18} Target sum:
17 Path:
Target sum: 𝐴→𝐵→𝐷→𝐶
𝑀 = 30 State Space Tree:
0
/ \ Step 4
Solution 5 X Return to starting city:
Possible subsets are: / \ 𝐶→𝐴=6
{5, 10, 15} 15 17
{12, 18} Solution: Final tour:
{5, 12, 13} 5 + 12 = 17 𝐴→𝐵→𝐷→𝐶→𝐴

State Space Tree Types of State Space Trees Minimum Cost

0 [Link] Tree 10 + 10 + 9 + 6 = 35
/ \ Used in:
5 X
/ \ • Subset Sum State Space Tree
15 17
/ \
• Knapsack A
Each level represents inclusion/exclusion of element. / | \
30 X B C D
Solution found: |
[Link] Tree
5 + 10 + 15 = 30 D
Used in:
|
• N-Queen C
Working of Backtracking
[Link] an element. • Hamiltonian Circuit |
A
[Link] whether sum exceeds target. Each level represents arrangement choices.
Optimal path:
[Link] valid, continue. 𝐴→𝐵→𝐷→𝐶→𝐴
[Link] invalid, backtrack. Advantages
[Link] another combination. [Link] solution search.
[Link] invalid paths early.
Pseudocode
Time Complexity [Link] unnecessary computations.
TSP(v)
𝑂(2𝑛 ) {
Disadvantages
if(all cities visited)
[Link] memory usage.
return cost;
Space Complexity [Link] complexity for large problems.
𝑂(𝑛) for(each unvisited city)
Applications
{
1.N-Queen problem.
Calculate bound;
Advantages [Link] Sum problem.
[Link] search method. [Link] Circuit.
if(bound<minimum)
[Link] invalid solutions early. [Link] coloring.
Visit city;
[Link] for moderate input size. }
Disadvantages Conclusion
}
[Link] exponential complexity. State Space Tree represents all possible states of a
[Link] suitable for very large datasets. Backtracking problem and helps in systematic exploration of
Time Complexity
valid solutions while rejecting invalid paths efficiently.
𝑂(𝑛!)
Applications
[Link] allocation.
[Link].
[Link] optimization.
[Link] problems.

Conclusion
Subset Sum problem uses Backtracking technique to find
subsets whose sum equals the target value by exploring valid
combinations systematically.
[Link] state space search tree for Travelling Salesman [Link] Branch and Bound technique with suitable [Link] classes P, NP, NP-Hard and NP-Complete with
Problem. example. suitable examples.
Travelling Salesman Problem (TSP) is a problem in which a Branch and Bound is an optimization technique used to solve Computational problems are classified into different
salesman visits every city exactly once and returns to the combinatorial problems efficiently. complexity classes based on the time required to solve them.
starting city with minimum travelling cost. It divides the problem into smaller subproblems(branching) Important complexity classes are:
State Space Tree represents all possible tours generated and removes non-promising solutions using 1.P
during Branch and Bound process. bounds(bounding). [Link]
Each node represents a partial path. It is mainly used for optimization problems like: [Link]-Hard

Example • Travelling Salesman Problem

[Link]-Complete
[Link] P
Consider 4 cities: • 0/1 Knapsack P(Polynomial Time) is the class of problems that can be
𝐴, 𝐵, 𝐶, 𝐷 solved in polynomial time using deterministic algorithms.
• Assignment Problem If a problem can be solved in time:
Start city: 𝑂(𝑛), 𝑂(𝑛2 ), 𝑂(𝑛3 )
𝐴 Terminology
[Link] then it belongs to class P.
Generating child nodes from parent node. Examples of P Problems
State Space Search Tree [Link] [Link] Search
A Calculating lower or upper bound of solution. [Link] Sort
/ | \ [Link] Node [Link]’s Algorithm
B C D Node that can generate further children. [Link] and DFS
/ \ / \ / \ [Link] Node Characteristics
C D B D B C Node that cannot generate better solution. [Link] solvable problems.
| | | | | | 5.E-node [Link] algorithms used.
D C D B C B Currently expanded node. [Link] time complexity.
| | | | | | [Link] NP
A A A A A A Algorithm NP(Non-deterministic Polynomial Time) is the class of
[Link] from root node. problems whose solutions can be verified in polynomial time.
Possible Tours [Link] child nodes. Solution may be difficult to find but easy to verify.
1. [Link] bound for each node. Examples of NP Problems
𝐴→𝐵→𝐶→𝐷→𝐴 [Link] node with best bound. [Link] Salesman Problem
[Link] nodes with poor bounds. [Link] Sum Problem
2. [Link] until optimal solution is found. [Link] Cycle Problem
𝐴→𝐵→𝐷→𝐶→𝐴 Characteristics
Example : 0/1 Knapsack Problem [Link] verification possible in polynomial time.
3. Knapsack Capacity: [Link] not have polynomial time solution.
𝐴→𝐶→𝐵→𝐷→𝐴 𝑊 = 16 [Link] P problems belong to NP.
Relationship Between P and NP
4. Given items: 𝑃 ⊆ 𝑁𝑃
𝐴→𝐶→𝐷→𝐵→𝐴 Item Profit Weight [Link]-Hard Problems
NP-Hard problems are at least as hard as the hardest
5. 1 40 2
problems in NP.
𝐴→𝐷→𝐵→𝐶→𝐴 2 30 5 They may or may not belong to NP.
3 50 10 Verification in polynomial time is not necessary.
6. Examples of NP-Hard Problems
𝐴→𝐷→𝐶→𝐵→𝐴 4 10 5 [Link] version of TSP
[Link] Problem
State Space Tree [Link] Playing Problem
Branch and Bound Concept Root Characteristics
[Link] possible paths. / \ [Link] than NP problems.
[Link] lower bound cost. Include Exclude [Link] known polynomial time algorithm.
[Link] paths with larger cost. 40 0 [Link] not be decision problems.
[Link] path with minimum cost. / \ [Link]-Complete Problems
70 40 NP-Complete problems are problems that are:
Advantages / \ [Link] NP
[Link] exploration of solutions. 120 70 [Link]-Hard
[Link] and Bound reduces unnecessary paths. Optimal profit: These are the hardest problems in NP.
[Link] visualize search process. 120 If one NP-Complete problem is solved in polynomial time,
then all NP problems can be solved in polynomial time.
Disadvantages Selected items: Examples of NP-Complete Problems
[Link] size grows rapidly. 1, 2, 3 1.3-SAT Problem
[Link] memory requirement. [Link] Cover Problem
[Link] Problem
Applications Working of Branch and Bound [Link] Cycle Problem
[Link] optimization. [Link] solution tree. [Link] Sum Problem
[Link] systems. [Link] bound value. Characteristics
[Link] optimization. [Link] bound is less than current best solution, prune node. [Link] to NP.
[Link] path planning. [Link] promising nodes only. [Link] NP-Hard.
[Link] known polynomial time solution.
Conclusion Types of Branch and Bound Relationship Among Classes
State Space Search Tree represents all possible tours of [Link] Branch and Bound NP-Hard
Travelling Salesman Problem and helps Branch and Bound [Link] Branch and Bound ___________
technique find the optimal minimum cost tour efficiently [Link] Cost Branch and Bound | |
| NP |
Pseudocode | ___ ___ |
BRANCH-BOUND() || P | |
{ | |_____| |
Create root node; | NP-Complete
|___________|
while(live nodes exist)
{ Comparison Table
Select best live node; Verification in
Polynomial
Class Definition Polynomial
Generate child nodes; Time Solution
Time

Compute bounds; Easy

P Yes Yes
problems
Prune non-promising nodes; Solution
} NP verifiable Not known Yes
} quickly
Hardest
Time Complexity NP-Hard No Not necessary
problems
Worst Case:
𝑂(2𝑛 ) NP- NP and NP- No known
Yes
Complete Hard solution
[Link] polynomial time reducibility with suitable [Link] that Subset Sum problem is NP-Complete. [Link] Clique Decision problem and Max Clique
example. Subset Sum problem is a decision problem in which, given a problem.
Polynomial Time Reducibility is a method used to convert one set of positive integers and a target sum 𝑀, we determine Clique is a subset of vertices in an undirected graph such that
problem into another problem in polynomial time. whether there exists a subset whose sum is equal to 𝑀. every pair of vertices is connected by an edge.
If problem 𝐴can be reduced to problem 𝐵, then solving
𝐵helps to solve 𝐴. Problem Statement Clique
It is denoted by: Given a set: If every vertex is connected to every other vertex in the
𝐴 ≤𝑝 𝐵 𝑆 = {𝑤1 , 𝑤2 , 𝑤3 , … , 𝑤𝑛 } subset, then the subset forms a Clique.
Meaning:
• Problem 𝐴is polynomially reducible to problem
Determine whether there exists a subset such that:
∑𝑤𝑖 = 𝑀
Example Graph
A
𝐵. /\
B---C
Definition Example \
A problem 𝐴is polynomially reducible to problem 𝐵if any Set: D
instance of 𝐴can be transformed into an instance of 𝐵in {3, 4, 5, 6} Vertices:
polynomial time. 𝐴, 𝐵, 𝐶
Target sum:
Purpose of Reducibility 9 form a Clique because every pair is connected.
[Link] prove NP-Completeness.
[Link] compare complexity of problems. Subset: [Link] Decision Problem
[Link] show one problem is at least as hard as another. {4, 5} Clique Decision Problem asks whether a graph contains a
clique of size 𝑘.
Steps for Proving Reducibility Hence solution exists.
[Link] a known NP-Complete problem. Problem Statement
[Link] it into another problem in polynomial time. To prove NP-Complete Given:
[Link] both problems are equivalent.
•
We must show:
[Link] target problem is NP-Complete. [Link] Sum belongs to NP. Graph 𝐺(𝑉, 𝐸)

Example : SAT to 3-SAT Reduction

[Link] Sum is NP-Hard. • Integer 𝑘
Determine whether graph contains a clique of size 𝑘.
SAT problem: Step 1: Subset Sum ∈ NP
Determine whether Boolean formula is satisfiable. Given a subset, we can verify whether its sum equals 𝑀in Example
Example: polynomial time. Graph:
(𝐴+𝐵+𝐶+𝐷) Example: A------B
Subset: \ /
Convert into 3-SAT form: {4, 5} \ /
Introduce new variable 𝑌:
C
(𝐴 + 𝐵 + 𝑌)(𝑌‾ + 𝐶 + 𝐷) Check: Question:
4+5=9 Does graph contain clique of size:
Now each clause has exactly 3 literals.
𝑘=3
Thus SAT is reduced to 3-SAT in polynomial time. Verification takes polynomial time.
Therefore: Answer:
Another Example : Vertex Cover to Clique 𝑆𝑢𝑏𝑠𝑒𝑡 𝑆𝑢𝑚 ∈ 𝑁𝑃 Yes.
Vertex Cover problem can be transformed into Clique
Clique:
problem in polynomial time.
{𝐴, 𝐵, 𝐶}
If graph 𝐺has: Step 2: Subset Sum is NP-Hard
• Vertex Cover of size 𝑘
To prove NP-Hard, reduce a known NP-Complete problem to
Subset Sum.
then complement graph 𝐺‾ has: Characteristics
Use:
•
[Link] problem.
Clique of size 𝑛 − 𝑘 3-𝑆𝐴𝑇 ≤𝑝 𝑆𝑢𝑏𝑠𝑒𝑡 𝑆𝑢𝑚 [Link] is YES or NO.
Thus: [Link] to NP-Complete class.
𝑉𝑒𝑟𝑡𝑒𝑥 𝐶𝑜𝑣𝑒𝑟 ≤𝑝 𝐶𝑙𝑖𝑞𝑢𝑒 Polynomial reduction is possible in polynomial time.
Thus Subset Sum is at least as hard as 3-SAT. Verification
Properties of Polynomial Reducibility Hence: If a subset of vertices is given, we can verify in polynomial
[Link] property holds. 𝑆𝑢𝑏𝑠𝑒𝑡 𝑆𝑢𝑚 𝑖𝑠 𝑁𝑃-𝐻𝑎𝑟𝑑 time whether every pair is connected.
If: Therefore:
𝐴 ≤𝑝 𝐵 𝐶𝑙𝑖𝑞𝑢𝑒 𝐷𝑒𝑐𝑖𝑠𝑖𝑜𝑛 𝑃𝑟𝑜𝑏𝑙𝑒𝑚 ∈ 𝑁𝑃
Therefore
and Since:
𝐵 ≤𝑝 𝐶 [Link] Sum belongs to NP [Link] Clique Problem (Max Clique)
[Link] Sum is NP-Hard Maximum Clique problem asks to find the largest clique
then: Therefore: present in a graph.
𝐴 ≤𝑝 𝐶 𝑆𝑢𝑏𝑠𝑒𝑡 𝑆𝑢𝑚 ∈ 𝑁𝑃-𝐶𝑜𝑚𝑝𝑙𝑒𝑡𝑒
Problem Statement
[Link] must take polynomial time. Find the clique having maximum number of vertices.
Flow Diagram
Importance in NP-Complete Problems 3-SAT Example
To prove problem 𝑋is NP-Complete: | Graph:
[Link] 𝑋 ∈ 𝑁𝑃 Polynomial Reduction A
[Link] known NP-Complete problem to 𝑋 ↓ /\
Subset Sum B---C
Time Complexity | \
Reduction process must take polynomial time such as: Verification in Polynomial Time D
𝑂(𝑛), 𝑂(𝑛2 ), 𝑂(𝑛3 ) Largest Clique:
Characteristics of Subset Sum {𝐴, 𝐵, 𝐶}
[Link] problem.
[Link] search space. Size:
[Link] known polynomial time solution. 3

Time Complexity
Brute force approach: Difference Between Clique Decision and Max Clique
𝑂(2𝑛 )
Clique Decision Maximum Clique
Feature
because all subsets are checked. Problem Problem
Check existence of
Objective Find largest clique
clique of size 𝑘
Output YES/NO Largest clique
Problem Optimization
Decision problem
Type problem
Complexity NP-Complete NP-Hard

Time Complexity
Brute force approach:
𝑂(2𝑛 )

because all subsets are checked.

Applications
[Link] network analysis.
[Link].
[Link] vision.
[Link] clustering.
[Link] Vertex Cover optimization problem and [Link] Hamiltonian Cycle problem and prove that [Link] Greedy method and Dynamic Programming
approximation algorithm. Directed Hamiltonian Cycle is NP-Complete. using Knapsack problem.
Vertex Cover is a graph problem in which a set of vertices is Hamiltonian Cycle is a cycle in a graph that visits every vertex Greedy Method and Dynamic Programming are important
selected such that every edge of the graph is incident to at exactly once and returns to the starting vertex. algorithm design techniques used for optimization problems.
least one selected vertex. Knapsack problem is commonly used to compare these
Hamiltonian Cycle methods.
Vertex Cover A graph contains Hamiltonian Cycle if there exists a cycle
A subset 𝐶 ⊆ 𝑉is called Vertex Cover if every edge has at passing through every vertex exactly once. Greedy Method
least one endpoint in 𝐶. Greedy method selects the locally optimal choice at each step
Example Graph hoping to obtain global optimum solution.
Example Graph A------B Used in:
A------B
\ /
| |
| | • Fractional Knapsack
\ / D------C
C Hamiltonian Cycle: Dynamic Programming
𝐴→𝐵→𝐶→𝐷→𝐴 Dynamic Programming solves problems by storing solutions
Edges:
of overlapping subproblems.
• AB Used in:
• AC Directed Hamiltonian Cycle Problem • 0/1 Knapsack
In Directed Hamiltonian Cycle problem, edges have directions
• BC and the cycle must follow edge directions. Fractional Knapsack using Greedy Method
Possible Vertex Cover: In Fractional Knapsack:
{𝐴, 𝐵} Example
because every edge is covered. A→B→C • Fraction of item can be selected.

Vertex Cover Optimization Problem

↑ ↓
D ←-----
• Items selected according to Profit/Weight
The objective is to find minimum number of vertices that ratio.
Directed Hamiltonian Cycle:
cover all edges. 𝐴→𝐵→𝐶→𝐷→𝐴
Example
Problem Statement Capacity:
Given graph 𝐺(𝑉, 𝐸), find minimum vertex cover. 𝑊 = 50
To Prove Directed Hamiltonian Cycle is NP-Complete
We must show:
Approximation Algorithm for Vertex Cover [Link] Hamiltonian Cycle belongs to NP. Item Profit Weight P/W Ratio
Since Vertex Cover is NP-Hard, approximation algorithm is [Link] Hamiltonian Cycle is NP-Hard. 1 60 10 6
used to find near optimal solution efficiently.
2 100 20 5
Step 1: Directed Hamiltonian Cycle ∈ NP
Approximation Algorithm Given a cycle, we can verify in polynomial time whether: 3 120 30 4
[Link] vertex cover set 𝐶 = ∅. [Link] vertices are visited exactly once. Select items according to ratio.
[Link] any uncovered edge (𝑢, 𝑣). [Link] returns to starting vertex. Total profit:
[Link] both vertices 𝑢and 𝑣to 𝐶. [Link] edges follow correct direction. 60 + 100 + 80 = 240
[Link] all edges incident on 𝑢and 𝑣. Verification takes polynomial time.
[Link] until all edges are covered. Therefore:
𝐷𝑖𝑟𝑒𝑐𝑡𝑒𝑑 𝐻𝑎𝑚𝑖𝑙𝑡𝑜𝑛𝑖𝑎𝑛 𝐶𝑦𝑐𝑙𝑒 ∈ 𝑁𝑃 0/1 Knapsack using Dynamic Programming
Pseudocode In 0/1 Knapsack:
APPROX-VERTEX-COVER(G)
{ Step 2: Directed Hamiltonian Cycle is NP-Hard • Item is either fully selected or rejected.
C=∅;
while(E is not empty)
Reduce known NP-Complete problem Hamiltonian Cycle to
Directed Hamiltonian Cycle.
• Fractional selection not allowed.
{ Transformation can be done in polynomial time by replacing
Example
Select edge(u,v); undirected edges with directed edges.
Capacity:
C=C∪{u,v}; Thus:
𝑊=5
Remove all edges incident 𝐻𝑎𝑚𝑖𝑙𝑡𝑜𝑛𝑖𝑎𝑛 𝐶𝑦𝑐𝑙𝑒 ≤𝑝 𝐷𝑖𝑟𝑒𝑐𝑡𝑒𝑑 𝐻𝑎𝑚𝑖𝑙𝑡𝑜𝑛𝑖𝑎𝑛 𝐶𝑦𝑐𝑙𝑒
on u and v;
} Therefore Directed Hamiltonian Cycle is NP-Hard. Item Profit Weight
return C; 1 6 1
} Therefore
2 10 2
Since:
Example [Link] Hamiltonian Cycle belongs to NP 3 12 3
Graph: [Link] Hamiltonian Cycle is NP-Hard DP Table:
A------B Hence:
|\ | Item/Weight 0 1 2 3 4 5
𝐷𝑖𝑟𝑒𝑐𝑡𝑒𝑑 𝐻𝑎𝑚𝑖𝑙𝑡𝑜𝑛𝑖𝑎𝑛 𝐶𝑦𝑐𝑙𝑒 ∈ 𝑁𝑃-𝐶𝑜𝑚𝑝𝑙𝑒𝑡𝑒
| \ | 0 0 0 0 0 0 0
| \ |
1 0 6 6 6 6 6
C------D Flow Diagram
Edges: Hamiltonian Cycle 2 0 6 10 16 16 16

• AB
|
Polynomial Reduction
3 0 6 10 16 18 22

• AC ↓
Maximum Profit:
22
• AD
Directed Hamiltonian Cycle
|
Selected items:
• BD Polynomial Time Verification
2, 3
• CD Characteristics
[Link] problem.
Step 1 Comparison Between Greedy Method and Dynamic
[Link] space grows exponentially.
Select edge: Programming
[Link] known polynomial time solution.
(𝐴, 𝐵) Dynamic
Feature Greedy Method
Add vertices: Time Complexity Programming
𝐴, 𝐵 Brute force approach: Optimal
Remove edges incident on A and B. 𝑂(𝑛!) Approach Local optimal choice subproblem
Remaining edge: solution
𝐶𝐷
Stores previous
Applications Decision Making Immediate decision
Step 2 results
[Link] optimization.
Select edge: [Link] design. May not always give Always gives
(𝐶 , 𝐷) [Link] routing.
Optimization
optimal solution optimal solution
Add vertices: [Link] sequencing.
𝐶, 𝐷 Complexity Lower Higher
Advantages Memory
Final Vertex Cover Less More
[Link] for optimization problems. Requirement
{𝐴, 𝐵, 𝐶 , 𝐷} [Link] in graph traversal systems. Suitable
Fractional Knapsack 0/1 Knapsack
Problems
Approximation Ratio Disadvantages
Approximation algorithm gives solution within: [Link]-Complete problem. Backtracking Not required Not required
2 × 𝑂𝑃𝑇 [Link] computational complexity. Table based
where 𝑂𝑃𝑇is optimal solution. Technique Selection strategy
computation
Time Complexity Time
𝑂(𝑛log⁡ 𝑛) 𝑂(𝑛𝑊)
𝑂(𝑉 + 𝐸) Complexity
[Link] recursive and iterative methods for solving [Link] time complexity of recursive and non-recursive [Link] Binary Search algorithm recursively and
recurrence relations. algorithms. iteratively with complexity analysis.
Recurrence relation is an equation that defines a function Time Complexity is the measure of amount of time required Binary Search is a searching algorithm used to search an
using smaller values of the same function. by an algorithm as input size increases. element in a sorted array.
Recursive and iterative methods are used to solve recurrence Algorithms are classified into: It repeatedly divides the search space into two halves.
relations. [Link] algorithms Working Principle
[Link]-recursive algorithms [Link] middle element.
[Link] Method [Link] key equals middle element, search successful.
In recursive method, a problem is solved by repeatedly calling [Link] Algorithms [Link] key is smaller, search left half.
the same function with smaller input values until a base Recursive algorithms solve a problem by calling the same [Link] key is larger, search right half.
condition is reached. function repeatedly with smaller input values until base [Link] until element is found.
condition is reached. Recursive Binary Search
Example Algorithm
Factorial: Example : Recursive Factorial BINARYSEARCH(A,low,high,key)
𝑛! = 𝑛 × (𝑛 − 1)! 𝑛! = 𝑛 × (𝑛 − 1)! {
Base condition: if(low<=high)
0! = 1 Recursive Algorithm {
FACTORIAL(n) mid=(low+high)/2;
Recursive Algorithm { if(A[mid]==key)
FACTORIAL(n) if(n==0) return mid;
{ return 1; else if(key<A[mid])
if(n==0) return BINARYSEARCH(A,low,mid-1,key);
return 1; else else
else return n*FACTORIAL(n-1); return BINARYSEARCH(A,mid+1,high,key);
return n*FACTORIAL(n-1); } }
} return -1;
Time Complexity Analysis }
Working Recurrence relation: Example
For: 𝑇(𝑛) = 𝑇(𝑛 − 1) + 1 Array:
4! Solving: 10, 20, 30, 40, 50, 60, 70
4! = 4 × 3! 𝑇(𝑛) = 𝑂(𝑛) Search key:
3! = 3 × 2! 50
2! = 2 × 1! Working
1! = 1 × 0! Example : Merge Sort Step 1
0! = 1 Recurrence relation: Middle element:
Therefore: 𝑛 40
𝑇(𝑛) = 2𝑇 ( ) + 𝑛
4! = 24 2 Since:
Using Master Theorem: 50 > 40
Advantages of Recursive Method 𝑇(𝑛) = 𝑂(𝑛log⁡ 𝑛) Search right half.
[Link] and elegant. Step 2
[Link] for divide and conquer problems. Middle element:
[Link] becomes shorter. Characteristics of Recursive Algorithms 60
[Link] calls itself repeatedly. Since:
Disadvantages of Recursive Method [Link] recursion stack memory. 50 < 60
[Link] memory required due to recursion stack. [Link] for divide and conquer problems. Search left half.
[Link] call overhead. Step 3
[Link] execution. [Link]-Recursive Algorithms Middle element:
Non-recursive algorithms use loops instead of recursive calls. 50
[Link] Method Element found.
In iterative method, loops are used instead of recursive Example : Iterative Factorial Iterative Binary Search
function calls. FACTORIAL(n) Algorithm
Repeated computations are performed using iteration. { BINARYSEARCH(A,n,key)
fact=1; {
Iterative Algorithm low=0;
FACTORIAL(n) for(i=1;i<=n;i++) high=n-1;
{ fact=fact*i; while(low<=high)
fact=1; {
return fact; mid=(low+high)/2;
for(i=1;i<=n;i++) } if(A[mid]==key)
fact=fact*i; return mid;
Time Complexity Analysis else if(key<A[mid])
return fact; Loop executes 𝑛times. high=mid-1;
} Therefore: else
𝑇(𝑛) = 𝑂(𝑛) low=mid+1;
Working }
For: return -1;
4! Example : Bubble Sort }
𝑓𝑎𝑐𝑡 = 1 × 1 × 2 × 3 × 4 for(i=0;i<n;i++) Time Complexity Analysis
4! = 24 { Recurrence relation:
for(j=0;j<n-1;j++) 𝑛
𝑇(𝑛) = 𝑇 ( ) + 1
{ 2
Advantages of Iterative Method comparison; Using Master Theorem:
[Link] execution. } 𝑎 = 1, 𝑏 = 2, 𝑓(𝑛) = 1
[Link] memory usage. } 𝑛log⁡𝑏 𝑎 = 1
[Link] recursion overhead. Time Complexity: Therefore:
𝑂(𝑛2 ) 𝑇(𝑛) = 𝑂(log⁡ 𝑛)
Disadvantages of Iterative Method Complexity Table
[Link] may become lengthy. Case Complexity
[Link] problems are harder to represent. Comparison Between Recursive and Non-Recursive
Best Case 𝑂(1)
Algorithms
Comparison Between Recursive and Iterative Methods Recursive Non-Recursive Average Case 𝑂(log⁡ 𝑛)
Feature
Feature Recursive Method Iterative Method Algorithm Algorithm Worst Case 𝑂(log⁡ 𝑛)
Technique Function calls Loops Technique Function calls Loops Space Complexity
Memory Memory Usage More Less Method Space Complexity
More Less
Usage Execution Recursive 𝑂(log⁡ 𝑛)
Slower Faster
Execution Speed Iterative 𝑂(1)
Slower Faster
Speed Uses recursion
Stack Usage No recursion stack Comparison Between Recursive and Iterative Binary Search
Code Size Shorter Longer stack
Feature Recursive Iterative
Stack Usage Uses recursion stack No recursion stack Code Size Shorter Longer
Technique Function calls Loop
Easy for recursive Easy for repetitive Suitable Divide and
Complexity Iterative computations Memory Usage More Less
problems tasks Problems Conquer
Execution Speed Slower Faster
Applications Stack Usage Uses recursion stack No recursion stack
Recursive Method
[Link] Sort
[Link] Sort
[Link] Traversal
Iterative Method
[Link] Search
[Link] Sort
[Link] using loops
[Link] Merge Sort and Quick Sort. Compare their [Link] Heap Sort, Merge Sort and Quick Sort and [Link] the following recurrence relations using Master
complexities and space requirements. compare their performances. Method.
Merge Sort Heap Sort a) (T(n)=2T(n/2)+n)
Merge Sort is a Divide and Conquer sorting algorithm. It Heap Sort is a comparison-based sorting algorithm based on b) (T(n)=4T(n/2)+n^2)
divides the array into two halves, recursively sorts them and Binary Heap data structure. c) (T(n)=5T(n/5)+\sqrt n)
merges the sorted halves. In Max Heap, parent node is greater than child nodes. d) (T(n)=T(n/2)+n)
Algorithm of Merge Sort Algorithm [Link] asymptotic notations Big O, Big Ω and Big Θ with
[Link] array into two halves. [Link] Max Heap. suitable examples.
[Link] each half recursively. [Link] root with last element. [Link] Merge Sort algorithm with example. Derive its
[Link] sorted halves. [Link] heap size. recurrence relation and time complexity.
Pseudocode [Link] heapify. [Link] Quick Sort algorithm with suitable example.
MERGESORT(A,low,high) [Link] until array is sorted. Analyze best, average and worst case complexities.
{ Pseudocode [Link] Randomized Quick Sort and compare it with
if(low<high) HEAPSORT(A,n) Quick Sort.
{ { [Link] Max Heap using heapify procedure for the
mid=(low+high)/2; BUILDHEAP(A); given elements and explain Heap Sort.
MERGESORT(A,low,mid); for(i=n-1;i>=0;i--) [Link] Breadth First Search (BFS) algorithm with
MERGESORT(A,mid+1,high); { example graph and complexity analysis.
swap(A[0],A[i]); [Link] Depth First Search (DFS) algorithm with example
MERGE(A,low,mid,high); HEAPIFY(A,i,0); graph and complexity analysis.
} }} [Link] BFS and DFS algorithms.
} Example [Link] AVL Tree insertion and perform LL, RR, LR and
Example Array:4, 10, 3, 5, 1 RL rotations with examples.
Array: Sorted array:1, 3, 4, 5, 10 [Link] Red Black Tree properties and compare Red
38, 27, 43, 3, 9, 82, 10 Time Complexity Black Tree with AVL Tree.
After Merge Sort: Case Complexity [Link] disjoint set operations using Union by Rank and
3, 9, 10, 27, 38, 43, 82 Path Compression.
Time Complexity of Merge Sort Best 𝑂(𝑛log⁡ 𝑛) [Link] Divide and Conquer paradigm with suitable
Recurrence relation: Average 𝑂(𝑛log⁡ 𝑛) examples.
𝑛 [Link] Prim’s algorithm and construct Minimum
𝑇(𝑛) = 2𝑇 ( ) + 𝑛 Worst 𝑂(𝑛log⁡ 𝑛)
2 Spanning Tree for a weighted graph.
Using Master Theorem: Space Complexity𝑂(1) [Link] Kruskal’s algorithm and construct Minimum
𝑇(𝑛) = 𝑂(𝑛log⁡ 𝑛) Merge Sort Spanning Tree for a weighted graph.
Space Complexity Merge Sort is a Divide and Conquer sorting algorithm that [Link] Prim’s and Kruskal’s algorithms.
𝑂(𝑛) divides the array into halves and merges sorted subarrays. [Link] shortest path using Dijkstra’s algorithm for a
Quick Sort Algorithm weighted graph. Show all steps.
Quick Sort is a Divide and Conquer sorting algorithm that [Link] array into two halves. [Link] Bellman Ford algorithm with suitable example
selects a pivot element and partitions the array into two [Link] recursively. and compare it with Dijkstra’s algorithm.
parts. [Link] sorted halves. [Link] Huffman Tree for given character frequencies
Elements smaller than pivot are placed on left side and larger Pseudocode and generate Huffman codes.
elements on right side. MERGESORT(A,low,high) [Link] Fractional Knapsack problem using Greedy
Algorithm of Quick Sort { method with suitable example.
[Link] pivot element. if(low<high) [Link] Matrix Chain Multiplication problem using
[Link] array. { Dynamic Programming and obtain optimal parenthesization.
[Link] Quick Sort recursively on left and right subarrays. mid=(low+high)/2; [Link] Longest Common Subsequence (LCS) for two given
Pseudocode MERGESORT(A,low,mid); strings using Dynamic Programming.
QUICKSORT(A,low,high) MERGESORT(A,mid+1,high); [Link] 0/1 Knapsack problem using Dynamic
{ MERGE(A,low,mid,high); Programming.
if(low<high) }} [Link] Floyd Warshall algorithm for all-pairs shortest
{ Example path problem with example.
p=PARTITION(A,low,high); Array:38, 27, 43, 3, 9, 82, 10 [Link] Optimal Binary Search Tree using Dynamic
QUICKSORT(A,low,p-1); Sorted array:3, 9, 10, 27, 38, 43, 82 Programming.
QUICKSORT(A,p+1,high); Time Complexity [Link] Maximum Flow problem and Max-flow Min-cut
} 𝑛
𝑇(𝑛) = 2𝑇 ( ) + 𝑛 theorem.
} 2 [Link] Naive String Matching algorithm with suitable
Example 𝑇(𝑛) = 𝑂(𝑛log⁡ 𝑛)
example.
Array: Space Complexity𝑂(𝑛)
[Link] Rabin-Karp string matching algorithm with
10, 80, 30, 90, 40, 50, 70 Quick Sort
suitable example.
After Quick Sort: Quick Sort is a Divide and Conquer sorting algorithm that
[Link] Knuth-Morris-Pratt (KMP) algorithm with
10, 30, 40, 50, 70, 80, 90 selects a pivot element and partitions the array.
construction of LPS table.
Time Complexity of Quick Sort Algorithm
[Link] String Matching using Finite Automata method.
Best/Average case recurrence: [Link] pivot element.
𝑛 [Link] Naive, Rabin-Karp and KMP string matching
𝑇(𝑛) = 2𝑇 ( ) + 𝑛 [Link] array.
2 algorithms.
[Link] left and right subarrays recursively.
Using Master Theorem: [Link] 4-Queen problem using Backtracking and draw
Pseudocode
𝑇(𝑛) = 𝑂(𝑛log⁡ 𝑛) the state space tree.
QUICKSORT(A,low,high)
Worst Case: [Link] Hamiltonian Circuit problem using
{
𝑂(𝑛2 ) Backtracking.
if(low<high)
Occurs when pivot becomes smallest or largest element. [Link] Subset Sum problem using Backtracking and
{
Space Complexity draw state space tree.
p=PARTITION(A,low,high);
Average Case: [Link] state space tree for Backtracking problems.
QUICKSORT(A,low,p-1);
𝑂(log⁡ 𝑛) [Link] Travelling Salesman Problem using Branch and
QUICKSORT(A,p+1,high);
Worst Case: Bound technique.
}
𝑂(𝑛) [Link] state space search tree for Travelling Salesman
}
Comparison Between Merge Sort and Quick Sort Problem.
Example
Feature Merge Sort Quick Sort [Link] Branch and Bound technique with suitable
Array:10, 80, 30, 90, 40, 50, 70
example.
Technique Divide and Conquer Divide and Conquer Sorted array:10, 30, 40, 50, 70, 80, 90
[Link] classes P, NP, NP-Hard and NP-Complete with
Time Complexity
Best Case 𝑂(𝑛log⁡ 𝑛) 𝑂(𝑛log⁡ 𝑛) suitable examples.
Best/Average Case:𝑂(𝑛log⁡ 𝑛)
[Link] polynomial time reducibility with suitable
Average Case 𝑂(𝑛log⁡ 𝑛) 𝑂(𝑛log⁡ 𝑛) Worst Case:𝑂(𝑛2 )
example.
Space Complexity
Worst Case 𝑂(𝑛log⁡ 𝑛) 𝑂(𝑛2 ) [Link] that Subset Sum problem is NP-Complete.
Average Case:𝑂(log⁡ 𝑛)
Space [Link] Clique Decision problem and Max Clique
𝑂(𝑛) 𝑂(log⁡ 𝑛) Comparison Between Heap Sort, Merge Sort and Quick Sort
Complexity problem.
Feature Heap Sort Merge Sort Quick Sort [Link] Vertex Cover optimization problem and
Stability Stable Not stable approximation algorithm.
Divide & Divide &
Technique Heap [Link] Hamiltonian Cycle problem and prove that
Extra Memory Required Not required Conquer Conquer
Directed Hamiltonian Cycle is NP-Complete.
Consistent Best Case 𝑂(𝑛log⁡ 𝑛) 𝑂(𝑛log⁡ 𝑛) 𝑂(𝑛log⁡ 𝑛)
Efficiency Faster in practice [Link] Greedy method and Dynamic Programming
performance
Average Case 𝑂(𝑛log⁡ 𝑛) 𝑂(𝑛log⁡ 𝑛) 𝑂(𝑛log⁡ 𝑛) using Knapsack problem.
Linked lists, large Arrays, internal [Link] recursive and iterative methods for solving
Suitable For Worst Case 𝑂(𝑛log⁡ 𝑛) 𝑂(𝑛log⁡ 𝑛) 𝑂(𝑛2 )
data sorting recurrence relations.
Space [Link] time complexity of recursive and non-recursive
𝑂(1) 𝑂(𝑛) 𝑂(log⁡ 𝑛)
Complexity algorithms.
Stability Not stable Stable Not stable [Link] Binary Search algorithm recursively and
iteratively with complexity analysis.
Not [Link] Merge Sort and Quick Sort. Compare their
Extra Memory Required Not required
required complexities and space requirements.
Fastest in [Link] Heap Sort, Merge Sort and Quick Sort and
Performance Good Consistent
practice compare their performances.