Data Structures and Algorithms Tutorials | IT Developer
IT Developer

Data Structures & Algorithms - Algorithms Basics

Share with a Friend
Previous
HOME
Next

Algorithm - Definition

An algorithm is a finite set of step-by-step instructions to solve a problem efficiently. In Data Structures and Algorithms (DSA), algorithms are used to organize, manipulate, and process data.

Characteristics of a Good Algorithm:

✅ Input – Takes zero or more inputs.
✅ Output – Produces at least one output.
✅ Definiteness – Each step is well-defined.
✅ Finiteness – Must complete in a limited number of steps.
✅ Efficiency – Optimized for time and space.

1. Key Features of an Algorithm

A good algorithm must have the following properties:

✅ Input – Takes zero or more inputs
✅ Output – Produces at least one output
✅ Definiteness – Each step is precisely defined
✅ Finiteness – Must terminate after a finite number of steps
✅ Effectiveness – Simple and feasible for execution

2. Basic Steps to Design an Algorithm

1️⃣ Understand the problem statement
2️⃣ Decide on the input and output
3️⃣ Break down the problem into smaller steps
4️⃣ Choose the best data structures
5️⃣ Write pseudocode or flowchart
6️⃣ Optimize for time and space complexity

3. Types of Algorithms

1️⃣ Brute Force Algorithm (Linear Search)

Definition:
A simple approach that checks each element in a data structure one by one.

Time Complexity:

  • Best Case: O(1) (Element found at the first position)
  • Worst Case: O(n) (Element not found)

Implementation in Different Languages:

C

C

#include <stdio.h>


int linearSearch(int arr[], int n, int key) {
 for (int i = 0; i < n; i++) {
 if (arr[i] == key)
 return i;
 }
 return -1;
}


int main() {
 int arr[] = {10, 20, 30, 40, 50};
 int key = 30;
 int n = sizeof(arr) / sizeof(arr[0]);
 int result = linearSearch(arr, n, key);
 if (result != -1)
 printf("Element found at index %d", result);
 else
 printf("Element not found");
 return 0;
}

Output:

Element found at index 2

C++

C++

#include <iostream>
using namespace std;


int linearSearch(int arr[], int n, int key) {
 for (int i = 0; i < n; i++) {
 if (arr[i] == key)
 return i;
 }
 return -1;
}


int main() {
 int arr[] = {10, 20, 30, 40, 50};
 int key = 30;
 int n = sizeof(arr) / sizeof(arr[0]);
 int result = linearSearch(arr, n, key);
 if (result != -1)
 cout << "Element found at index " << result;
 else
 cout << "Element not found";
 return 0;
}

Output:

Element found at index 2

Java

Java

class LinearSearch {
 public static int search(int arr[], int key) {
 for (int i = 0; i < arr.length; i++) {
 if (arr[i] == key)
 return i;
 }
 return -1;
 }


public static void main(String[] args) {
 int arr[] = {10, 20, 30, 40, 50};
 int key = 30;
 int result = search(arr, key);
 if (result != -1)
 System.out.println("Element found at index " + result);
 else
 System.out.println("Element not found");
 }
}

Output:

Element found at index 2

Python

Python

def linear_search(arr, key):
 for i in range(len(arr)):
 if arr[i] == key:
 return i
 return -1


arr = [10, 20, 30, 40, 50]
key = 30
result = linear_search(arr, key)
print(f"Element found at index {result}" if result != -1 else "Element not found")

Output:

Element found at index 2

2️⃣ Divide and Conquer Algorithm (Binary Search)

Definition:
A faster searching method that divides the array into halves and searches in the appropriate half.

Time Complexity:

  • Best Case: O(1)
  • Worst Case: O(log n)

Implementation in Different Languages:

C

C

#include <stdio.h>


int binarySearch(int arr[], int low, int high, int key) {
 while (low <= high) {
 int mid = (low + high) / 2;
 if (arr[mid] == key)
 return mid;
 else if (arr[mid] < key)
 low = mid + 1;
 else
 high = mid - 1;
 }
 return -1;
}


int main() {
 int arr[] = {10, 20, 30, 40, 50};
 int key = 30;
 int n = sizeof(arr) / sizeof(arr[0]);
 int result = binarySearch(arr, 0, n - 1, key);
 if (result != -1)
 printf("Element found at index %d", result);
 else
 printf("Element not found");
 return 0;
}

Output:

Element found at index 2

C++

C++

#include <iostream>
using namespace std;


int binarySearch(int arr[], int low, int high, int key) {
 while (low <= high) {
 int mid = (low + high) / 2;
 if (arr[mid] == key)
 return mid;
 else if (arr[mid] < key)
 low = mid + 1;
 else
 high = mid - 1;
 }
 return -1;
}


int main() {
 int arr[] = {10, 20, 30, 40, 50};
 int key = 30;
 int n = sizeof(arr) / sizeof(arr[0]);
 int result = binarySearch(arr, 0, n - 1, key);
 cout << (result != -1 ? "Element found at index " + to_string(result) : "Element not found");
 return 0;
}

Output:

Element found at index 2

Java

Java

class BinarySearch {
 public static int binarySearch(int arr[], int key) {
 int low = 0, high = arr.length - 1;
 while (low <= high) {
 int mid = (low + high) / 2;
 if (arr[mid] == key)
 return mid;
 else if (arr[mid] < key)
 low = mid + 1;
 else
 high = mid - 1;
 }
 return -1;
 }


public static void main(String[] args) {
 int arr[] = {10, 20, 30, 40, 50};
 int key = 30;
 int result = binarySearch(arr, key);
 System.out.println(result != -1 ? "Element found at index " + result : "Element not found");
 }
}

Output:

Element found at index 2

Python

Python

def binary_search(arr, key):
 low, high = 0, len(arr) - 1
 while low <= high:
 mid = (low + high) // 2
 if arr[mid] == key:
 return mid
 elif arr[mid] < key:
 low = mid + 1
 else:
 high = mid - 1
 return -1


arr = [10, 20, 30, 40, 50]
key = 30
result = binary_search(arr, key)
print(f"Element found at index {result}" if result != -1 else "Element not found")

Output:

Element found at index 2

3️⃣ Greedy Algorithm

A greedy algorithm follows the approach of making the best possible choice at each step, assuming that this will lead to the optimal solution.

Key Properties:

  1. Greedy Choice Property – The global optimum can be reached by choosing local optima at each step.
  2. Optimal Substructure – A problem has an optimal solution that can be built using optimal solutions to its subproblems.

Example 1: Activity Selection Problem

Problem Statement:

  • Given n activities with their start and end times.
  • Select the maximum number of activities that can be performed without overlapping.

Approach:

  1. Sort activities by their ending time.
  2. Select the first activity and then pick subsequent ones that start after the previous activity ends.

Time Complexity:

  • O(n log n) (Sorting) + O(n) (Activity selection) = O(n log n).

 

C Implementation

C

#include <stdio.h>
#include <stdlib.h>


typedef struct {
 int start, end;
} Activity;


// Comparator function to sort activities by end time
int compare(const void *a, const void *b) {
 return ((Activity *)a)->end - ((Activity *)b)->end;
}


void activitySelection(Activity arr[], int n) {
 qsort(arr, n, sizeof(Activity), compare);
 
 printf("Selected activities: ");
 int lastEnd = arr[0].end;
 printf("(%d, %d) ", arr[0].start, arr[0].end);


for (int i = 1; i < n; i++) {
 if (arr[i].start >= lastEnd) {
 printf("(%d, %d) ", arr[i].start, arr[i].end);
 lastEnd = arr[i].end;
 }
 }
}


int main() {
 Activity arr[] = {{1, 3}, {2, 5}, {3, 6}, {8, 9}, {5, 7}, {8, 10}};
 int n = sizeof(arr) / sizeof(arr[0]);
 activitySelection(arr, n);
 return 0;
}

Output:

Selected activities: (1, 3) (3, 6) (5, 7) (8, 9)

C++ Implementation

C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;


struct Activity {
 int start, end;
};


// Comparator function to sort activities by end time
bool compare(Activity a, Activity b) {
 return a.end < b.end;
}


void activitySelection(vector<Activity> &arr) {
 sort(arr.begin(), arr.end(), compare);


cout << "Selected activities: ";
 int lastEnd = arr[0].end;
 cout << "(" << arr[0].start << ", " << arr[0].end << ") ";


for (int i = 1; i < arr.size(); i++) {
 if (arr[i].start >= lastEnd) {
 cout << "(" << arr[i].start << ", " << arr[i].end << ") ";
 lastEnd = arr[i].end;
 }
 }
}


int main() {
 vector<Activity> arr = {{1, 3}, {2, 5}, {3, 6}, {8, 9}, {5, 7}, {8, 10}};
 activitySelection(arr);
 return 0;
}

Output:

Selected activities: (1, 3) (3, 6) (5, 7) (8, 9)

Java Implementation

Java

import java.util.Arrays;
import java.util.Comparator;


class Activity {
 int start, end;
 Activity(int start, int end) {
 this.start = start;
 this.end = end;
 }
}


public class GreedyActivitySelection {
 static void activitySelection(Activity arr[]) {
 Arrays.sort(arr, Comparator.comparingInt(a -> a.end));


System.out.print("Selected activities: ");
 int lastEnd = arr[0].end;
 System.out.print("(" + arr[0].start + ", " + arr[0].end + ") ");


for (int i = 1; i < arr.length; i++) {
 if (arr[i].start >= lastEnd) {
 System.out.print("(" + arr[i].start + ", " + arr[i].end + ") ");
 lastEnd = arr[i].end;
 }
 }
 }


public static void main(String[] args) {
 Activity arr[] = {new Activity(1, 3), new Activity(2, 5), new Activity(3, 6), 
 new Activity(8, 9), new Activity(5, 7), new Activity(8, 10)};
 activitySelection(arr);
 }
}

Output:

Selected activities: (1, 3) (3, 6) (5, 7) (8, 9)

Python Implementation

Python

def activity_selection(activities):
 # Sort activities by end time
 activities.sort(key=lambda x: x[1])
 
 selected = []
 last_end = activities[0][1]
 selected.append(activities[0])
 
 for i in range(1, len(activities)):
 if activities[i][0] >= last_end:
 selected.append(activities[i])
 last_end = activities[i][1]
 
 print("Selected activities:", selected)


activities = [(1, 3), (2, 5), (3, 6), (8, 9), (5, 7), (8, 10)]
activity_selection(activities)

Output:

Selected activities: (1, 3) (3, 6) (5, 7) (8, 9)

4️⃣ Dynamic Programming (DP) Algorithm

Dynamic Programming (DP) is an optimization technique used to solve problems by breaking them down into overlapping subproblems and solving each subproblem only once, storing the result to avoid redundant computations.

Key Properties of DP:

  1. Optimal Substructure – The solution to a problem is built from solutions of its subproblems.
  2. Overlapping Subproblems – The problem can be broken into smaller problems that are solved multiple times.

Types of Dynamic Programming Approaches

  1. Top-Down Approach (Memoization): Recursion + storing results in a table.
  2. Bottom-Up Approach (Tabulation): Filling a table iteratively.

 

Example 1: Fibonacci Sequence (Using DP)

Problem Statement:

Compute the n-th Fibonacci number using Dynamic Programming.

Mathematical Formula (Recurrence Relation)

F(n)=F(n−1)+F(n−2)F(n) = F(n-1) + F(n-2)F(n)=F(n−1)+F(n−2)

where:

  • F(0)=0F(0) = 0F(0)=0
  • F(1)=1F(1) = 1F(1)=1

Time Complexity:

  • Brute Force Recursion: O(2n)O(2^n)O(2n) (exponential)
  • Memoization (Top-Down DP): O(n)O(n)O(n)
  • Tabulation (Bottom-Up DP): O(n)O(n)O(n)

C Implementation (Top-Down: Memoization)

C

#include <stdio.h>


#define MAX 100
int dp[MAX];


int fibonacci(int n) {
 if (n <= 1) return n;
 if (dp[n] != -1) return dp[n]; // Use cached result
 return dp[n] = fibonacci(n - 1) + fibonacci(n - 2);
}


int main() {
 for (int i = 0; i < MAX; i++) dp[i] = -1; // Initialize dp array
 int n = 10;
 printf("Fibonacci(%d) = %d\n", n, fibonacci(n));
 return 0;
}

Output:

Fibonacci(10) = 55

C++ Implementation (Bottom-Up: Tabulation)

C++

#include <iostream>
using namespace std;


int fibonacci(int n) {
 int dp[n + 1];
 dp[0] = 0, dp[1] = 1;
 
 for (int i = 2; i <= n; i++)
 dp[i] = dp[i - 1] + dp[i - 2];


return dp[n];
}


int main() {
 int n = 10;
 cout << "Fibonacci(" << n << ") = " << fibonacci(n) << endl;
}

Output:

Fibonacci(10) = 55

Java Implementation (Top-Down: Memoization)

Java

import java.util.Arrays;


class FibonacciDP {
 static int[] dp;


static int fibonacci(int n) {
 if (n <= 1) return n;
 if (dp[n] != -1) return dp[n];
 return dp[n] = fibonacci(n - 1) + fibonacci(n - 2);
 }


public static void main(String[] args) {
 int n = 10;
 dp = new int[n + 1];
 Arrays.fill(dp, -1);
 System.out.println("Fibonacci(" + n + ") = " + fibonacci(n));
 }
}

Output:

Fibonacci(10) = 55

Python Implementation (Bottom-Up: Tabulation)

Python

def fibonacci(n):
 dp = [0] * (n + 1)
 dp[1] = 1
 
 for i in range(2, n + 1):
 dp[i] = dp[i - 1] + dp[i - 2]


return dp[n]


n = 10
print(f"Fibonacci({n}) =", fibonacci(n))

Output:

Fibonacci(10) = 55

5️⃣ Backtracking Algorithm

 

Backtracking is an algorithmic technique used for finding solutions recursively by trying all possible options and removing (backtracking) the ones that fail. It is commonly used for combinatorial problems like Sudoku, N-Queens, and Maze Solving.

Key Concepts

  1. Recursive exploration of possibilities.
  2. Backtrack when a solution path is not valid.
  3. Pruning to eliminate unnecessary computations.

Example 1: N-Queens Problem

Problem Statement:

  • Place N queens on an N × N chessboard such that no two queens attack each other.

Approach:

  • Use backtracking to place queens row by row.
  • Ensure queens do not attack each other in the same column, row, or diagonals.

Time Complexity: O(N!)O(N!)O(N!) (Exponential)

C Implementation (N-Queens)

C

#include <stdio.h>
#include <stdbool.h>


#define N 4


void printSolution(int board[N][N]) {
 for (int i = 0; i < N; i++) {
 for (int j = 0; j < N; j++)
 printf("%d ", board[i][j]);
 printf("\n");
 }
 printf("\n");
}


bool isSafe(int board[N][N], int row, int col) {
 for (int i = 0; i < row; i++)
 if (board[i][col]) return false;
 
 for (int i = row, j = col; i >= 0 && j >= 0; i--, j--)
 if (board[i][j]) return false;


for (int i = row, j = col; i >= 0 && j < N; i--, j++)
 if (board[i][j]) return false;


return true;
}


bool solveNQueens(int board[N][N], int row) {
 if (row == N) {
 printSolution(board);
 return true;
 }


bool found = false;
 for (int col = 0; col < N; col++) {
 if (isSafe(board, row, col)) {
 board[row][col] = 1;
 found |= solveNQueens(board, row + 1);
 board[row][col] = 0;
 }
 }
 return found;
}


int main() {
 int board[N][N] = {0};
 solveNQueens(board, 0);
 return 0;
}

Output:

0 0 1 0
1 0 0 0
0 0 0 1
0 1 0 0

C++ Implementation (N-Queens)

C++

#include <iostream>
#include <vector>
using namespace std;


#define N 4


void printSolution(vector<vector<int>> &board) {
 for (auto &row : board) {
 for (int cell : row) cout << cell << " ";
 cout << "\n";
 }
 cout << "\n";
}


bool isSafe(vector<vector<int>> &board, int row, int col) {
 for (int i = 0; i < row; i++)
 if (board[i][col]) return false;


for (int i = row, j = col; i >= 0 && j >= 0; i--, j--)
 if (board[i][j]) return false;


for (int i = row, j = col; i >= 0 && j < N; i--, j++)
 if (board[i][j]) return false;


return true;
}


bool solveNQueens(vector<vector<int>> &board, int row) {
 if (row == N) {
 printSolution(board);
 return true;
 }


bool found = false;
 for (int col = 0; col < N; col++) {
 if (isSafe(board, row, col)) {
 board[row][col] = 1;
 found |= solveNQueens(board, row + 1);
 board[row][col] = 0;
 }
 }
 return found;
}


int main() {
 vector<vector<int>> board(N, vector<int>(N, 0));
 solveNQueens(board, 0);
 return 0;
}

Output:

0 0 1 0
1 0 0 0
0 0 0 1
0 1 0 0

Java Implementation (N-Queens)

Java

class NQueens {
 static final int N = 4;


static void printSolution(int[][] board) {
 for (int[] row : board) {
 for (int cell : row) System.out.print(cell + " ");
 System.out.println();
 }
 System.out.println();
 }


static boolean isSafe(int[][] board, int row, int col) {
 for (int i = 0; i < row; i++)
 if (board[i][col] == 1) return false;


for (int i = row, j = col; i >= 0 && j >= 0; i--, j--)
 if (board[i][j] == 1) return false;


for (int i = row, j = col; i >= 0 && j < N; i--, j++)
 if (board[i][j] == 1) return false;


return true;
 }


static boolean solveNQueens(int[][] board, int row) {
 if (row == N) {
 printSolution(board);
 return true;
 }


boolean found = false;
 for (int col = 0; col < N; col++) {
 if (isSafe(board, row, col)) {
 board[row][col] = 1;
 found |= solveNQueens(board, row + 1);
 board[row][col] = 0;
 }
 }
 return found;
 }


public static void main(String[] args) {
 int[][] board = new int[N][N];
 solveNQueens(board, 0);
 }
}

Output:

0 0 1 0
1 0 0 0
0 0 0 1
0 1 0 0

Python Implementation (N-Queens)

Python

N = 4


def print_solution(board):
 for row in board:
 print(" ".join(str(cell) for cell in row))
 print()


def is_safe(board, row, col):
 for i in range(row):
 if board[i][col] == 1:
 return False
 
 for i, j in zip(range(row, -1, -1), range(col, -1, -1)):
 if board[i][j] == 1:
 return False
 
 for i, j in zip(range(row, -1, -1), range(col, N)):
 if board[i][j] == 1:
 return False


return True


def solve_n_queens(board, row):
 if row == N:
 print_solution(board)
 return True


found = False
 for col in range(N):
 if is_safe(board, row, col):
 board[row][col] = 1
 found |= solve_n_queens(board, row + 1)
 board[row][col] = 0
 return found


board = [[0] * N for _ in range(N)]
solve_n_queens(board, 0)

Output:

0 0 1 0
1 0 0 0
0 0 0 1
0 1 0 0

4. Time and Space Complexity Analysis

Complexity Best Case Worst Case Example
O(1)

Constant

Constant

Accessing an array element
O(log n)

Logarithmic

Logarithmic

Binary Search
O(n)

Linear

Linear

Linear Search
O(n log n)

Log-linear

Log-linear

Merge Sort, Quick Sort
O(n²)

Quadratic

Quadratic

Bubble Sort, Selection Sort
O(2ⁿ)

Exponential

Exponential

Fibonacci (without DP)
O(n!)

Factorial

Factorial

N-Queens Problem
Previous
Next