Module 31: Algorithms in C++

Introduction

Algorithms are step-by-step procedures used to solve computational problems efficiently. Together with data structures, algorithms form the foundation of computer science and software engineering.

A good algorithm minimizes:

• Execution time
• Memory usage
• Computational complexity

Algorithms are used in:

• Search Engines
• Artificial Intelligence
• Databases
• Operating Systems
• Robotics
• Networking
• Compilers
• Competitive Programming

This module introduces the most important algorithmic techniques used in C++.

Learning Objectives

After completing this module, you will understand:

• Sorting Algorithms
• Searching Algorithms
• Greedy Algorithms
• Backtracking
• Recursion
• Divide and Conquer
• Dynamic Programming
• Graph Algorithms
• Time Complexity

Algorithm Categories

1. Sorting Algorithms

Sorting arranges data in ascending or descending order.

Example

textCopy
140 10 30 20
2
3↓
4
510 20 30 40

Bubble Sort

Time Complexity: O(n²)

cppCopy
1#include <iostream>
2using namespace std;
3
4void bubbleSort(int arr[], int n)
5{
6    for(int i = 0; i < n - 1; i++)
7    {
8        for(int j = 0; j < n - i - 1; j++)
9        {
10            if(arr[j] > arr[j + 1])
11                swap(arr[j], arr[j + 1]);
12        }
13    }
14}
15
16int main()
17{
18    int arr[] = {5,3,8,1,2};
19
20    bubbleSort(arr,5);
21
22    for(int x : arr)
23        cout << x << " ";
24}

Output

textCopy
11 2 3 5 8

Merge Sort (Divide & Conquer)

Time Complexity: O(n log n)

cppCopy
1#include <algorithm>
2#include <iostream>
3using namespace std;
4
5void mergeSort(int arr[], int left, int right)
6{
7    if(left >= right)
8        return;
9
10    int mid = (left + right) / 2;
11
12    mergeSort(arr, left, mid);
13    mergeSort(arr, mid + 1, right);
14
15    inplace_merge(arr + left, arr + mid + 1, arr + right + 1);
16}
17
18int main()
19{
20    int arr[] = {9,5,2,7,1};
21
22    mergeSort(arr,0,4);
23
24    for(int x : arr)
25        cout << x << " ";
26}

Output

textCopy
11 2 5 7 9

2. Searching Algorithms

Searching finds an element within a collection.

Linear Search

Time Complexity: O(n)

cppCopy
1#include <iostream>
2using namespace std;
3
4int linearSearch(int arr[], int n, int key)
5{
6    for(int i = 0; i < n; i++)
7    {
8        if(arr[i] == key)
9            return i;
10    }
11
12    return -1;
13}
14
15int main()
16{
17    int arr[] = {10,20,30,40};
18
19    cout << linearSearch(arr,4,30);
20}

Output

textCopy
12

Binary Search

Time Complexity: O(log n)

cppCopy
1#include <iostream>
2using namespace std;
3
4int binarySearch(int arr[], int left, int right, int key)
5{
6    while(left <= right)
7    {
8        int mid = left + (right - left) / 2;
9
10        if(arr[mid] == key)
11            return mid;
12
13        if(arr[mid] < key)
14            left = mid + 1;
15        else
16            right = mid - 1;
17    }
18
19    return -1;
20}
21
22int main()
23{
24    int arr[] = {10,20,30,40,50};
25
26    cout << binarySearch(arr,0,4,40);
27}

Output

textCopy
13

3. Greedy Algorithm

A greedy algorithm always chooses the best immediate option.

Example: Coin Change (assuming canonical coin values)

cppCopy
1#include <iostream>
2using namespace std;
3
4int main()
5{
6    int coins[] = {25,10,5,1};
7    int amount = 63;
8
9    for(int coin : coins)
10    {
11        while(amount >= coin)
12        {
13            cout << coin << " ";
14            amount -= coin;
15        }
16    }
17}

Output

textCopy
125 25 10 1 1 1

Note: The greedy approach is optimal only for certain coin systems.

4. Backtracking

Backtracking tries a choice, and if it fails, it reverses the choice and tries another.

Example: Generate all binary strings of length 3.

cppCopy
1#include <iostream>
2using namespace std;
3
4void generate(string s, int n)
5{
6    if((int)s.size() == n)
7    {
8        cout << s << endl;
9        return;
10    }
11
12    generate(s + "0", n);
13    generate(s + "1", n);
14}
15
16int main()
17{
18    generate("",3);
19}

Output

textCopy
1000
2001
3010
4011
5100
6101
7110
8111

5. Recursion

Recursion is a technique where a function calls itself to solve a smaller instance of the same problem.

Factorial

cppCopy
1#include <iostream>
2using namespace std;
3
4int factorial(int n)
5{
6    if(n <= 1)
7        return 1;
8
9    return n * factorial(n - 1);
10}
11
12int main()
13{
14    cout << factorial(5);
15}

Output

textCopy
1120

Fibonacci

cppCopy
1#include <iostream>
2using namespace std;
3
4int fibonacci(int n)
5{
6    if(n <= 1)
7        return n;
8
9    return fibonacci(n - 1) + fibonacci(n - 2);
10}
11
12int main()
13{
14    cout << fibonacci(8);
15}

Output

textCopy
121

6. Divide and Conquer

Divide the problem into smaller subproblems, solve them independently, then combine the results.

Examples:

• Merge Sort
• Quick Sort
• Binary Search

Quick Sort example:

cppCopy
1#include <algorithm>
2#include <iostream>
3using namespace std;
4
5void quickSort(int arr[], int left, int right)
6{
7    if(left >= right)
8        return;
9
10    int pivot = arr[(left + right) / 2];
11    int i = left;
12    int j = right;
13
14    while(i <= j)
15    {
16        while(arr[i] < pivot) i++;
17        while(arr[j] > pivot) j--;
18
19        if(i <= j)
20        {
21            swap(arr[i], arr[j]);
22            i++;
23            j--;
24        }
25    }
26
27    quickSort(arr, left, j);
28    quickSort(arr, i, right);
29}
30
31int main()
32{
33    int arr[] = {8,4,2,9,5};
34
35    quickSort(arr,0,4);
36
37    for(int x : arr)
38        cout << x << " ";
39}

Output

textCopy
12 4 5 8 9

7. Dynamic Programming

Dynamic Programming (DP) stores solutions to previously solved subproblems to avoid repeated computation.

Fibonacci using DP

cppCopy
1#include <iostream>
2#include <vector>
3using namespace std;
4
5int main()
6{
7    int n = 10;
8
9    vector<int> dp(n + 1);
10
11    dp[0] = 0;
12    dp[1] = 1;
13
14    for(int i = 2; i <= n; i++)
15        dp[i] = dp[i - 1] + dp[i - 2];
16
17    cout << dp[n];
18}

Output

textCopy
155

0/1 Knapsack

cppCopy
1#include <iostream>
2#include <vector>
3using namespace std;
4
5int main()
6{
7    vector<int> wt = {1,3,4,5};
8    vector<int> val = {1,4,5,7};
9
10    int W = 7;
11    int n = wt.size();
12
13    vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));
14
15    for(int i = 1; i <= n; i++)
16    {
17        for(int w = 1; w <= W; w++)
18        {
19            if(wt[i - 1] <= w)
20                dp[i][w] = max(dp[i - 1][w],
21                               val[i - 1] + dp[i - 1][w - wt[i - 1]]);
22            else
23                dp[i][w] = dp[i - 1][w];
24        }
25    }
26
27    cout << dp[n][W];
28}

Output

textCopy
19

8. Graph Algorithms

Graphs represent relationships between objects.

textCopy
1A ----- B
2|       |
3|       |
4C ----- D

Breadth-First Search (BFS)

cppCopy
1#include <iostream>
2#include <queue>
3#include <vector>
4using namespace std;
5
6int main()
7{
8    vector<vector<int>> graph =
9    {
10        {1,2},
11        {0,3},
12        {0,3},
13        {1,2}
14    };
15
16    vector<bool> visited(4,false);
17    queue<int> q;
18
19    q.push(0);
20    visited[0] = true;
21
22    while(!q.empty())
23    {
24        int node = q.front();
25        q.pop();
26
27        cout << node << " ";
28
29        for(int next : graph[node])
30        {
31            if(!visited[next])
32            {
33                visited[next] = true;
34                q.push(next);
35            }
36        }
37    }
38}

Output

textCopy
10 1 2 3

Depth-First Search (DFS)

cppCopy
1#include <iostream>
2#include <vector>
3using namespace std;
4
5void dfs(int node,
6         vector<vector<int>>& graph,
7         vector<bool>& visited)
8{
9    visited[node] = true;
10
11    cout << node << " ";
12
13    for(int next : graph[node])
14    {
15        if(!visited[next])
16            dfs(next, graph, visited);
17    }
18}
19
20int main()
21{
22    vector<vector<int>> graph =
23    {
24        {1,2},
25        {0,3},
26        {0},
27        {1}
28    };
29
30    vector<bool> visited(4,false);
31
32    dfs(0, graph, visited);
33}

Output

textCopy
10 1 3 2

Time Complexity Summary

Real-World Applications

Best Practices

• Choose algorithms based on time and space complexity.
• Prefer std::sort() in production for general-purpose sorting.
• Use binary search only on sorted data.
• Add clear base cases in recursive functions.
• Use memoization or tabulation to optimize recursive solutions.
• Avoid unnecessary copying of large containers by passing them by reference.

Common Mistakes

Using Binary Search on Unsorted Data

Binary search requires the input to be sorted.

Missing Base Case in Recursion

A recursive function without a proper base case can cause infinite recursion and stack overflow.

Ignoring Time Complexity

An O(n²) algorithm may become impractical for large inputs.

Interview Questions

1. What is an algorithm?

A finite sequence of well-defined steps used to solve a problem or perform a computation.

2. What is the difference between Linear Search and Binary Search?

Linear Search checks elements sequentially, while Binary Search repeatedly halves a sorted search space.

3. What is Divide and Conquer?

A technique that splits a problem into smaller subproblems, solves them independently, and combines their results.

4. What is Dynamic Programming?

An optimization technique that stores solutions to overlapping subproblems to avoid repeated computation.

5. What is a Greedy Algorithm?

An algorithm that makes the locally optimal choice at each step in the hope of finding a globally optimal solution.

6. What is Backtracking?

A technique that explores possible solutions and abandons a path as soon as it determines that the path cannot lead to a valid solution.

7. What is the difference between BFS and DFS?

BFS explores nodes level by level using a queue, while DFS explores as deeply as possible using recursion or a stack.

8. Why is Merge Sort preferred for large datasets?

Because it guarantees O(n log n) time complexity regardless of the input order and is stable.

Module Summary

In this module, you learned:

• Sorting algorithms such as Bubble Sort, Merge Sort, and Quick Sort
• Searching techniques including Linear Search and Binary Search
• The Greedy approach for locally optimal decisions
• Backtracking for exploring all possible solutions
• Recursive problem solving
• Divide and Conquer strategies
• Dynamic Programming with memoization/tabulation concepts
• Graph traversal using Breadth-First Search (BFS) and Depth-First Search (DFS)
• Time complexity analysis and practical algorithm selection

These algorithms form the core of technical interviews, competitive programming, and production-quality software development in C++.