1.
Sequential Search Algorithm
Algorithm SequentialSearch(A, n, key)
1. for i ← 0 to n-1 do
2. if A[i] = key then
3. return i
4. return -1
Key idea: Check each element one by one
2. Binary Search Algorithm (Iterative)
Algorithm BinarySearch(A, low, high, key)
1. while low ≤ high do
2. mid ← (low + high) / 2
3. if A[mid] = key then
4. return mid
5. else if key < A[mid] then
6. high ← mid - 1
7. else
8. low ← mid + 1
9. return -1
Condition: Array must be sorted
3. Topological Sorting (Kahn’s Algorithm)
Algorithm TopologicalSort(G)
1. Compute indegree of all vertices
2. Add all vertices with indegree 0 to queue
3. while queue not empty do
4. u ← dequeue
5. print u
6. for each neighbor v of u do
7. indegree[v] ← indegree[v] - 1
8. if indegree[v] = 0 then
9. enqueue v
Used for: Directed Acyclic Graph (DAG)
4. Binary Tree Traversals
Inorder (LNR)
Algorithm Inorder(root)
1. if root ≠ NULL then
2. Inorder([Link])
3. print [Link]
4. Inorder([Link])
Preorder (NLR)
Algorithm Preorder(root)
1. if root ≠ NULL then
2. print [Link]
3. Preorder([Link])
4. Preorder([Link])
Postorder (LRN)
Algorithm Postorder(root)
1. if root ≠ NULL then
2. Postorder([Link])
3. Postorder([Link])
4. print [Link]
5. Matrix Multiplication (Normal Method)
Algorithm MatrixMultiply(A, B, n)
1. for i ← 0 to n-1 do
2. for j ← 0 to n-1 do
3. C[i][j] ← 0
4. for k ← 0 to n-1 do
5. C[i][j] ← C[i][j] + A[i][k] * B[k][j]
6. return C
Idea: Row × Column multiplication
6. Strassen’s Matrix Multiplication
Algorithm Strassen(A, B)
1. Divide A and B into 4 submatrices
2. Compute 7 products (P1 to P7)
3. Combine results into matrix C
4. return C
Key point: Uses 7 multiplications instead of 8
7. Travelling Salesman Problem (Brute Force)
Algorithm TSP(graph, n)
1. minCost ← ∞
2. for each permutation of cities do
3. cost ← calculate path cost
4. if cost < minCost then
5. minCost ← cost
6. return minCost
Idea: Try all possible path
1. Bubble Sort
Algorithm BubbleSort(A, n)
1. for i ← 0 to n-1 do
2. for j ← 0 to n-i-2 do
3. if A[j] > A[j+1] then
4. swap A[j], A[j+1]
Idea: Largest element “bubbles up” to the end
2. Selection Sort
Algorithm SelectionSort(A, n)
1. for i ← 0 to n-1 do
2. min ← i
3. for j ← i+1 to n-1 do
4. if A[j] < A[min] then
5. min ← j
6. swap A[i], A[min]
Idea: Select minimum and place it correctly
3. Insertion Sort
Algorithm InsertionSort(A, n)
1. for i ← 1 to n-1 do
2. key ← A[i]
3. j ← i - 1
4. while j ≥ 0 and A[j] > key do
5. A[j+1] ← A[j]
6. j←j-1
7. A[j+1] ← key
Idea: Insert element into sorted part
4. Merge Sort
Algorithm MergeSort(A, low, high)
1. if low < high then
2. mid ← (low + high) / 2
3. MergeSort(A, low, mid)
4. MergeSort(A, mid+1, high)
5. Merge(A, low, mid, high)
Merge Procedure
Algorithm Merge(A, low, mid, high)
1. Create temp arrays L and R
2. Copy elements into L and R
3. Compare elements of L and R
4. Place smaller into A
5. Copy remaining elements
Idea: Divide and merge sorted halves
5. Quick Sort
Algorithm QuickSort(A, low, high)
1. if low < high then
2. p ← Partition(A, low, high)
3. QuickSort(A, low, p-1)
4. QuickSort(A, p+1, high)
Partition Procedure
Algorithm Partition(A, low, high)
1. pivot ← A[high]
2. i ← low - 1
3. for j ← low to high-1 do
4. if A[j] < pivot then
5. i←i+1
6. swap A[i], A[j]
7. swap A[i+1], A[high]
8. return i+1
Idea: Pivot and partition