DATA STRUCTURES &

ALGORITHMS
Complete Study Guide
Units 1 – 5 | With Examples & Diagrams

EEE Department | B.S. Vidya

 UNIT 1: Sorting Algorithms & Searching
1.1 Bubble Sort
Definition
Bubble Sort is the simplest sorting algorithm. It repeatedly compares adjacent elements and swaps
them if they are in the wrong order. After each pass, the largest element 'bubbles up' to its correct
position.

Algorithm
for i = 0 to n-2:
for j = 0 to n-2-i:
if arr[j] > arr[j+1]:
swap(arr[j], arr[j+1])

Example
Array: [64, 34, 25, 12, 22]
Pass Array After Pass Swaps
Pass 1 [34, 25, 12, 22, 64] 4
Pass 2 [25, 12, 22, 34, 64] 3
Pass 3 [12, 22, 25, 34, 64] 2
Pass 4 [12, 22, 25, 34, 64] 0 → DONE
Sorted [12, 22, 25, 34, 64] -

Metric Value
Best Case O(n)
Worst Case O(n²)
Average O(n²)
Space O(1)
Stable? Yes

1.2 Selection Sort

Definition
Selection Sort divides the array into sorted and unsorted parts. It repeatedly finds the minimum element
from the unsorted part and places it at the beginning of the sorted part.

Algorithm
for i = 0 to n-2:
minIndex = i
for j = i+1 to n-1:
if arr[j] < arr[minIndex]: minIndex = j
swap(arr[i], arr[minIndex])
Example
Array: [64, 25, 12, 22, 11]
Pass Min Found Array After Swap
Pass 1 (i=0) 11 at index 4 [11, 25, 12, 22, 64]
Pass 2 (i=1) 12 at index 2 [11, 12, 25, 22, 64]
Pass 3 (i=2) 22 at index 3 [11, 12, 22, 25, 64]
Pass 4 (i=3) 25 at index 3 [11, 12, 22, 25, 64]
Result - [11, 12, 22, 25, 64] SORTED

Metric Value
Best Case O(n²)
Worst Case O(n²)
Space O(1)
Stable? No

1.3 Insertion Sort

Definition
Insertion Sort builds the sorted array one element at a time. It picks each element and inserts it into its
correct position in the already-sorted portion. Like sorting playing cards in hand.

Algorithm
for i = 1 to n-1:
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j+1] = arr[j]
j = j - 1
arr[j+1] = key

Example
Array: [12, 11, 13, 5, 6]
Step Key Array State
i=1 key=11 [11, 12, 13, 5, 6]
i=2 key=13 [11, 12, 13, 5, 6]
i=3 key=5 [5, 11, 12, 13, 6]
i=4 key=6 [5, 6, 11, 12, 13]

Metric Value
Best Case O(n)
Worst Case O(n²)
 Space O(1)
Stable? Yes

1.4 Merge Sort

Definition
Merge Sort uses Divide and Conquer strategy. It divides the array into two halves, recursively sorts
each half, then merges the two sorted halves. It always runs in O(n log n) time.

Algorithm
mergeSort(arr, l, r):
if l < r:
mid = (l + r) / 2
mergeSort(arr, l, mid)
mergeSort(arr, mid+1, r)
merge(arr, l, mid, r)

merge: combine two sorted halves into one sorted array

Example
Array: [38, 27, 43, 3]
Split: [38, 27, 43, 3]
[38, 27] [43, 3]
[38] [27] [43] [3]
Merge: [27, 38] [3, 43]
Result: [3, 27, 38, 43]

Metric Value
Best Case O(n log n)
Worst Case O(n log n)
Space O(n)
Stable? Yes

1.5 Quick Sort

Definition
Quick Sort also uses Divide and Conquer. It selects a 'pivot' element and partitions the array so
elements less than pivot go to left, greater go to right. It recursively sorts the sub-arrays.

Algorithm
quickSort(arr, low, high):
if low < high:
pi = partition(arr, low, high) // pivot index
quickSort(arr, low, pi-1)
quickSort(arr, pi+1, high)

partition: place pivot at correct position, smaller left, larger right

Example
Array: [10, 7, 8, 9, 1, 5] → Pivot = 5 (last element)
Initial: [10, 7, 8, 9, 1, 5] pivot = 5
After P1: [1, 5, 8, 9, 10, 7] → pivot 5 in correct pos
Left: [1] (already sorted)
Right: [8, 9, 10, 7] → pivot = 7
After P2: [7, 9, 10, 8] → ...
Final: [1, 5, 7, 8, 9, 10]

Metric Value
Best Case O(n log n)
Worst Case O(n²)
Average O(n log n)
Space O(log n)
Stable? No

1.6 Heap Sort

Definition
Heap Sort uses a Binary Heap data structure. It first builds a Max Heap from the array, then repeatedly
extracts the maximum element (root) and places it at the end. The heap is restructured after each
extraction.

Steps
• Build Max Heap: rearrange array so parent is always >= children
• Extract max (root) and swap with last element
• Reduce heap size by 1 and heapify the root
• Repeat until heap has 1 element

Example
Array: [4, 10, 3, 5, 1]
Build Max Heap: [10, 5, 3, 4, 1]
Swap root with last: [1, 5, 3, 4, 10] → 10 sorted
Heapify: [5, 4, 3, 1, 10]
Swap: [1, 4, 3, 5, 10] → 5 sorted
... Continue ...
Final: [1, 3, 4, 5, 10]

Metric Value
Best Case O(n log n)
Worst Case O(n log n)
Space O(1)
Stable? No
 1.7 Sorting Algorithms Comparison
Algorithm Best Average Worst Space Stable
Bubble Sort O(n) O(n²) O(n²) O(1) Yes
Selection Sort O(n²) O(n²) O(n²) O(1) No
Insertion Sort O(n) O(n²) O(n²) O(1) Yes
Merge Sort O(n log n) O(n log n) O(n log n) O(n) Yes
Quick Sort O(n log n) O(n log n) O(n²) O(log n) No
Heap Sort O(n log n) O(n log n) O(n log n) O(1) No

1.8 Linear Search

Definition
Linear Search sequentially checks each element of the list until the target is found or the list ends. It
works on both sorted and unsorted arrays.

Algorithm
linearSearch(arr, n, key):
for i = 0 to n-1:
if arr[i] == key:
return i // found at index i
return -1 // not found

Example
Array: [20, 40, 60, 10, 50] → Search for 10
Step 1: arr[0] = 20 ≠ 10
Step 2: arr[1] = 40 ≠ 10
Step 3: arr[2] = 60 ≠ 10
Step 4: arr[3] = 10 = 10 → FOUND at index 3!

Metric Value
Best Case O(1) — first element
Worst Case O(n) — last or not found
Space O(1)

1.9 Binary Search

Definition
Binary Search works ONLY on sorted arrays. It repeatedly divides the search interval in half. If the
target is less than the mid element, search the left half; else search the right half.

Algorithm
binarySearch(arr, low, high, key):
while low <= high:
mid = (low + high) / 2
 if arr[mid] == key: return mid
else if arr[mid] < key: low = mid + 1
else: high = mid - 1
return -1

Example
Sorted Array: [2, 5, 8, 12, 16, 23, 38, 45] → Search for 23
Step low high mid arr[mid] Action
1 0 7 3 12 23 > 12 → low = 4
2 4 7 5 23 23 = 23 → FOUND at 5!

Metric Value
Best Case O(1) — mid is target
Worst Case O(log n)
Space O(1)
Requirement Array must be SORTED
 UNIT 2: Stack & Queue
2.1 Stack
Definition
A Stack is a linear data structure that follows the LIFO (Last In, First Out) principle. The element
inserted last is the first to be removed. Think of a stack of plates — you add and remove from the top.

Real-World Examples
• Stack of plates in a cafeteria
• Browser back button (history of visited pages)
• Undo operation in text editors
• Function call stack in programming

Stack Operations
Operation Description Time Complexity
push(x) Insert element x at top of stack O(1)
pop() Remove and return top element O(1)
peek() / top() Return top element without removing O(1)
isEmpty() Check if stack is empty O(1)
isFull() Check if stack is full (array-based) O(1)

Stack Representation (Array-based)

Initially: Stack = [] TOP = -1

push(10): Stack = [10] TOP = 0

push(20): Stack = [10, 20] TOP = 1
push(30): Stack = [10,20,30] TOP = 2
pop(): Stack = [10, 20] TOP = 1 returns 30
peek(): returns 20 TOP = 1

Applications of Stack
• Expression Evaluation (Infix, Postfix, Prefix)
• Expression Conversion (Infix to Postfix/Prefix)
• Balanced Parentheses Checking
• Function call management (Recursion)
• DFS (Depth First Search) in graphs
• Backtracking algorithms
 2.2 Stack – Expression Evaluation
Types of Expressions
Type Notation Example
Infix Operator between operands A+B*C
Prefix (Polish) Operator before operands +A*BC
Postfix (Reverse Operator after operands ABC*+
Polish)

Infix to Postfix Conversion (Using Stack)

Rules: Scan left to right. Operands → output directly. Operators → manage with stack using
precedence (* / before + -). '(' → push. ')' → pop until '('.
Example: Convert A + B * C - D to Postfix
Symbol Stack Output
A A
+ + A
B + AB
* +* AB
C +* ABC
- - ABC*+
D - ABC*+D
END ABC*+D-

Result: Postfix of A + B * C - D is A B C * + D -

Postfix Expression Evaluation (Using Stack)

Rule: Scan left to right. If operand → push to stack. If operator → pop two operands, apply operator,
push result.
Example: Evaluate 5 6 2 + * 12 4 / -
Token Action Stack
5 Push 5 [5]
6 Push 6 [5, 6]
2 Push 2 [5, 6, 2]
+ Pop 2,6 → 6+2=8, Push 8 [5, 8]
* Pop 8,5 → 5*8=40, Push 40 [40]
12 Push 12 [40, 12]
4 Push 4 [40, 12, 4]
/ Pop 4,12 → 12/4=3, Push 3 [40, 3]
 - Pop 3,40 → 40-3=37, Push 37 [37]
END Result = 37

2.3 Queue
Definition
A Queue is a linear data structure that follows the FIFO (First In, First Out) principle. The element
inserted first is the first to be removed. Think of people standing in a line — first person joins first,
served first.

Real-World Examples
• People waiting in a bank queue
• Print spooler (printer queue)
• CPU process scheduling
• BFS (Breadth First Search) in graphs

Queue Operations
Operation Description Time Complexity
enqueue(x) Insert element x at rear O(1)
dequeue() Remove element from front O(1)
peek() / front() Return front element without removing O(1)
isEmpty() Check if queue is empty O(1)
isFull() Check if queue is full O(1)

Queue Representation
Initially: FRONT = -1, REAR = -1

enqueue(10): FRONT=0, REAR=0 Queue=[10]

enqueue(20): FRONT=0, REAR=1 Queue=[10, 20]
enqueue(30): FRONT=0, REAR=2 Queue=[10, 20, 30]
dequeue(): FRONT=1, REAR=2 Queue=[20, 30] returns 10

2.4 Types of Queue

1. Simple / Linear Queue
Basic FIFO queue. Problem: After multiple dequeue operations, front moves right and space at
beginning is wasted even when queue appears full.

2. Circular Queue
Overcomes the limitation of linear queue. The last position wraps around to connect to the first position,
forming a circle. REAR = (REAR + 1) % MAX_SIZE.
Advantage:
• No wasted space — reuses positions freed by dequeue
• More memory efficient than linear queue
enqueue: REAR = (REAR + 1) % SIZE
dequeue: FRONT = (FRONT + 1) % SIZE
Full condition: (REAR + 1) % SIZE == FRONT
Empty condition: FRONT == REAR

3. Double-Ended Queue (Deque)

Insertion and deletion can happen at BOTH ends (front and rear). More flexible than standard queue.
Operation Description
insertFront() Add element at front
insertRear() Add element at rear
deleteFront() Remove from front
deleteRear() Remove from rear

Input-Restricted Deque: Insertion at one end only, deletion at both ends.

Output-Restricted Deque: Insertion at both ends, deletion at one end only.

4. Priority Queue
Each element has a priority. Elements with higher priority are served before lower priority elements,
regardless of insertion order.
Type Behavior
Min-Priority Queue Element with LOWEST priority value is served first
Max-Priority Queue Element with HIGHEST priority value is served first

Applications of Queue
• CPU Scheduling (Round Robin, FCFS)
• Disk Scheduling algorithms
• Breadth First Search (BFS) in graphs
• Handling requests on a single shared resource (printer, CPU)
• Simulation of real-world queues (bank, ticket counter)
 UNIT 3: Trees & Graph Algorithms
3.1 Binary Tree
Definition
A Binary Tree is a hierarchical data structure where each node has at most TWO children, called the
left child and right child. The topmost node is called the root.

Key Terminology
Term Definition
Root Topmost node; has no parent
Leaf Node Node with no children
Height Length of longest path from root to leaf
Depth Distance of a node from the root
Degree Number of children a node has (max 2 in binary tree)
Subtree A node and all its descendants

Example Binary Tree

1 ← Root (Level 0)
/ \
2 3 ← Level 1
/ \ / \
4 5 6 7 ← Level 2 (Leaf nodes)

Tree Traversals
Three standard traversal methods — all use recursion:
Traversal Order Result for above tree
Inorder (LNR) Left → Node → Right 4, 2, 5, 1, 6, 3, 7
Preorder (NLR) Node → Left → Right 1, 2, 4, 5, 3, 6, 7
Postorder (LRN) Left → Right → Node 4, 5, 2, 6, 7, 3, 1

3.2 Types of Binary Trees

Type Definition Property
Full Binary Tree Every node has 0 or 2 children No node has exactly 1 child
Complete Binary Tree All levels filled except possibly last; Used in Heap Sort
last filled left to right
Perfect Binary Tree All internal nodes have 2 children; all 2^h - 1 total nodes
leaves at same level
Skewed Tree All nodes have only left or only right Degenerates to linked list
 child
Balanced Binary Tree Height difference between left & AVL trees are balanced
right subtrees ≤ 1

3.3 Binary Search Tree (BST)

Definition
A Binary Search Tree is a binary tree with the ordering property: for any node N, all values in the LEFT
subtree are LESS than N, and all values in the RIGHT subtree are GREATER than N.
BST Property: Left subtree values < Node value < Right subtree values

BST Operations
1. Search
• Start at root
• If key == root → found
• If key < root → search left subtree
• If key > root → search right subtree
• If null → not found

2. Insertion
• Search for correct position using BST property
• Insert new node as leaf at that position

3. Deletion — Three Cases:

Case Condition Action
Case 1 Node is a leaf Simply delete the node
Case 2 Node has ONE child Replace node with its child
Case 3 Node has TWO children Replace with Inorder Successor (smallest in right
subtree) or Inorder Predecessor

Example — Build BST from: 50, 30, 70, 20, 40, 60, 80
Insert 50: 50
Insert 30: 50
/
30
Insert 70: 50
/ \
30 70
Insert 20,40,60,80: 50
/ \
30 70
/ \ / \
20 40 60 80
Inorder traversal of this BST: 20, 30, 40, 50, 60, 70, 80 (Sorted!)
Key Property: Inorder traversal of a BST always gives SORTED output.

Operation Average Worst (Skewed)

Search O(log n) O(n)
Insert O(log n) O(n)
Delete O(log n) O(n)

3.4 Dijkstra's Algorithm

Definition
Dijkstra's Algorithm finds the SHORTEST PATH from a single source vertex to all other vertices in a
weighted graph (with non-negative weights). It is a Greedy algorithm.
Restriction: All edge weights must be NON-NEGATIVE (≥ 0)

Algorithm Steps
1. Initialize distance of source = 0, all others = ∞
2. Add all vertices to unvisited set
3. Select unvisited vertex with minimum distance → call it 'current'
4. For each unvisited neighbor of current: calculate tentative distance = dist[current] +
edge_weight
5. If tentative distance < dist[neighbor], update dist[neighbor]
6. Mark current as visited (remove from unvisited set)
7. Repeat steps 3-6 until all vertices visited

Example Graph
Graph edges (source → dest, weight):
A → B: 4 A → C: 2
B → C: 1 B → D: 5
C → B: 1 C → D: 8 C → E: 10
D → E: 2 E → D: 3

Source = A

Step-by-Step Execution
Step Visited dist[A] dist[B] dist[C] dist[D] dist[E]
Initial {} 0 ∞ ∞ ∞ ∞
Visit A {A} 0 4 2 ∞ ∞
Visit C {A,C} 0 3 2 10 12
(min=2)
 Visit B {A,C,B} 0 3 2 8 12
(min=3)
Visit D {A,C,B,D} 0 3 2 8 10
(min=8)
Visit E {A,C,B,D,E} 0 3 2 8 10
(min=10)

Final Shortest Paths from A:

Destination Shortest Distance Path
A 0 A
B 3 A→C→B
C 2 A→C
D 8 A→C→B→D
E 10 A→C→B→D→E

Metric Value
Time Complexity (Simple) O(V²)
Time Complexity (Priority Queue) O((V+E) log V)
Space O(V)
 UNIT 4: Algorithm Analysis & Asymptotic Notations
4.1 What is an Algorithm?
Definition
An algorithm is a finite set of well-defined, unambiguous instructions to solve a problem or perform a
computation. It takes input, processes it, and produces output.

Properties of a Good Algorithm

Property Meaning
Input Has zero or more inputs
Output Produces at least one output
Definiteness Each step is clearly defined and unambiguous
Finiteness Terminates after a finite number of steps
Effectiveness Each step is basic enough to be carried out

4.2 Algorithm Efficiency

Time Complexity
Time complexity measures how the running time of an algorithm grows as the input size n increases. It
is expressed as a function of n.

Space Complexity
Space complexity measures the amount of memory an algorithm uses relative to input size n.

Types of Analysis
Case Description Example
Best Case Minimum time for any input of size n Searching: element found at first
position
Worst Case Maximum time for any input of size n Searching: element at last position or
absent
Average Case Expected time over all possible Average behavior over random inputs
inputs of size n

4.3 Asymptotic Notations

Why Asymptotic Analysis?
We analyze algorithms for large input sizes to understand scalability. Asymptotic notations describe
how running time grows as n → ∞, ignoring constants and lower-order terms.
1. Big-O Notation — O(f(n)) [Upper Bound]
Big-O gives the WORST CASE upper bound on an algorithm's running time. It tells us: the algorithm
will NEVER take more than O(f(n)) time.
f(n) = O(g(n)) means: ∃ constants c > 0 and n₀ such that f(n) ≤ c·g(n) for all n ≥ n₀

Example: f(n) = 3n² + 5n + 2

3n² + 5n + 2 ≤ 10n² for large n
Therefore: f(n) = O(n²)
We say: f(n) grows no faster than n²

2. Big-Omega Notation — Ω(f(n)) [Lower Bound]

Big-Omega gives the BEST CASE lower bound. It tells us: the algorithm takes AT LEAST Ω(f(n)) time.
f(n) = Ω(g(n)) means: ∃ constants c > 0 and n₀ such that f(n) ≥ c·g(n) for all n ≥ n₀

Example: f(n) = 3n² + 5n + 2

3n² + 5n + 2 ≥ 1·n² for all n ≥ 1
Therefore: f(n) = Ω(n²)

3. Big-Theta Notation — Θ(f(n)) [Tight Bound]

Big-Theta gives BOTH upper and lower bounds. It means the algorithm runs exactly (tightly) as fast as
Θ(f(n)).
f(n) = Θ(g(n)) means: f(n) = O(g(n)) AND f(n) = Ω(g(n))

Example: f(n) = 3n² + 5n + 2 = Θ(n²)

4. Little-o — o(f(n)) and Little-omega — ω(f(n))

Notation Meaning Relationship
o(g(n)) Strictly less than g(n) asymptotically f grows SLOWER than g
ω(g(n)) Strictly greater than g(n) asymptotically f grows FASTER than g

Common Complexity Classes (Best to Worst)

Notation Name Example Algorithm
O(1) Constant Array access by index
O(log n) Logarithmic Binary Search
O(n) Linear Linear Search
O(n log n) Linearithmic Merge Sort, Quick Sort (avg)
O(n²) Quadratic Bubble Sort, Insertion Sort
O(n³) Cubic Floyd-Warshall Algorithm
O(2ⁿ) Exponential Subset enumeration
 O(n!) Factorial Travelling Salesman (brute force)

Comparing Notations
Notation Type Condition Usage
O(g(n)) Upper Bound f(n) ≤ c·g(n) Worst case guarantee
Ω(g(n)) Lower Bound f(n) ≥ c·g(n) Best case guarantee
Θ(g(n)) Tight Bound Both above Exact behavior
o(g(n)) Strict Upper f(n) < c·g(n) f strictly slower than g
ω(g(n)) Strict Lower f(n) > c·g(n) f strictly faster than g
 UNIT 5: Algorithm Design Techniques
5.1 Knapsack Problem
Problem Statement
Given n items each with a weight and value, and a knapsack with capacity W: select items to maximize
total value without exceeding capacity W.

Two Variants
Type Items Approach
0/1 Knapsack Either take whole item or leave it Dynamic Programming
Fractional Knapsack Can take fraction of an item Greedy Algorithm

Fractional Knapsack (Greedy Approach)

Strategy: Calculate value/weight ratio for each item. Sort by ratio in descending order. Take items
greedily until knapsack is full.
Example:
Knapsack Capacity W = 50 kg
Item Weight (kg) Value (₹) Value/Weight Ratio
Item 1 10 60 6.0
Item 2 20 100 5.0
Item 3 30 120 4.0

Greedy Selection (sorted by ratio: 6 > 5 > 4):

Step Action Weight Used Value Gained
1 Take all of Item 1 (ratio=6) 10 kg ₹60
2 Take all of Item 2 (ratio=5) 20 kg ₹100
3 Take 20/30 of Item 3 (ratio=4) 20 kg ₹80
TOTAL 10+20+20 = 50 kg 50 kg = W ₹240

Maximum Value = ₹60 + ₹100 + (20/30)×₹120 = ₹60 + ₹100 + ₹80 = ₹240

Metric Value
Time Complexity O(n log n) for sorting
Space O(1)
0/1 Knapsack (Dynamic Programming)
Use a 2D table dp[i][w] = maximum value using first i items with capacity w.
Example: n=3 items, W=4
Item Weight Value
Item 1 1 1
Item 2 3 4
Item 3 4 5

DP Table dp[i][w]:
Item \ W 0 1 2 3 4
0 (no items) 0 0 0 0 0
1 (w=1,v=1) 0 1 1 1 1
2 (w=3,v=4) 0 1 1 4 5
3 (w=4,v=5) 0 1 1 4 5

Maximum value = dp[3][4] = 5 → Select Item 2 (value 4) — wait, = 5 means Item 1+2 = 1+4 = 5

Metric Value
Time Complexity O(n × W)
Space Complexity O(n × W)

5.2 N-Queen Problem

Problem Statement
Place N queens on an N×N chessboard such that no two queens threaten each other. Queens attack
along the same row, column, or diagonal.
Constraint: No two queens share the same row, column, or diagonal.

Approach: Backtracking
Place queens one column at a time. For each column, try all rows. If placement is safe → move to next
column. If no row is safe → backtrack to previous column and try next row.

Safety Check
• Same row: arr[i] == arr[j]
• Same diagonal: |arr[i] - arr[j]| == |i - j|
• Same column: automatically avoided by column-by-column placement
Example: 4-Queen Problem (N=4)
Board size: 4×4

One solution: Q . . .
. . Q .
. . . Q
. Q . .

Column: 1 2 3 4
Row placed: 1 3 4 2 → arr = [1, 3, 4, 2]

Verification:
Queens at (1,1),(2,3),(3,4),(4,2)
No two share row ✓ No two share column ✓
No two share diagonal ✓ VALID SOLUTION!

Total solutions for N=4: 2

N Solutions
1 1
4 2
5 10
8 92

Metric Value
Time Complexity O(N!)
Space O(N)

5.3 All-Pairs Shortest Path — Floyd-Warshall Algorithm

Problem Statement
Find shortest paths between ALL pairs of vertices in a weighted graph. Unlike Dijkstra (single source),
Floyd-Warshall computes shortest path for every pair (i, j).
Floyd-Warshall handles NEGATIVE edge weights but NOT negative cycles.

Algorithm Idea
Consider vertices 1, 2, ..., n one by one as intermediate vertices. For each pair (i, j), check if going
through intermediate vertex k gives a shorter path.
Initialize dist[i][j] = weight of edge (i,j), or ∞ if no direct edge
dist[i][i] = 0 for all i

for k = 1 to n: // k = intermediate vertex

for i = 1 to n:
for j = 1 to n:
if dist[i][k] + dist[k][j] < dist[i][j]:
dist[i][j] = dist[i][k] + dist[k][j]
Example
Graph with 4 vertices (V1, V2, V3, V4):
Edges:
V1→V2: 3 V1→V3: ∞ V1→V4: 7
V2→V1: 8 V2→V3: 2 V2→V4: ∞
V3→V1: 5 V3→V2: ∞ V3→V4: 1
V4→V1: 2 V4→V2: ∞ V4→V3: ∞

Initial Distance Matrix (D⁰):

V1 V2 V3 V4
V1 0 3 ∞ 7
V2 8 0 2 ∞
V3 5 ∞ 0 1
V4 2 ∞ ∞ 0

After k=1 (V1 as intermediate) — D¹:

V1 V2 V3 V4
V1 0 3 ∞ 7
V2 8 0 2 15
V3 5 8 0 1
V4 2 5 ∞ 0

Example update: V2→V4: ∞ → V2→V1→V4 = 8+7 = 15 ✓

After k=2 (V2 as intermediate) — D²:

V1 V2 V3 V4
V1 0 3 5 7
V2 8 0 2 15
V3 5 8 0 1
V4 2 5 7 0

After k=3 — D³:

V1 V2 V3 V4
V1 0 3 5 6
V2 7 0 2 3
V3 5 8 0 1
V4 2 5 7 0
Final Matrix after k=4 — D⁴ (All-Pairs Shortest Paths):
V1 V2 V3 V4
V1 0 3 5 6
V2 5 0 2 3
V3 3 6 0 1
V4 2 5 7 0

Reading the final matrix: dist[i][j] gives the shortest path from vertex i to vertex j.

Example: Shortest path from V2 to V1 = 5 (via V4: V2→V3→V4→V1 = 2+1+2 = 5)

Metric Value
Time Complexity O(V³)
Space Complexity O(V²)
Handles Negative Weights Yes
Handles Negative Cycles No (detects them: dist[i][i] < 0)
vs Dijkstra Floyd-Warshall is all-pairs; Dijkstra is single-source

5.4 Algorithm Comparison Summary

Algorithm Type Problem Solved Time Space
Bubble Sort Exchange Sorting O(n²) O(1)
Merge Sort Divide & Conquer Sorting O(n log n) O(n)
Quick Sort Divide & Conquer Sorting O(n log n) avg O(log n)
Binary Search Divide & Conquer Searching O(log n) O(1)
Dijkstra Greedy Single-source shortest path O(V²) O(V)
Floyd-Warshall Dynamic All-pairs shortest path O(V³) O(V²)
Programming
Fractional Knapsack Greedy Optimization O(n log n) O(1)
0/1 Knapsack Dynamic Optimization O(nW) O(nW)
Programming
N-Queens Backtracking Constraint satisfaction O(N!) O(N)

— End of Study Guide —