Introduction to Algorithms in C

Welcome to this step-by-step guide to understanding algorithms in C. This tutorial is designed to introduce you to the basics of algorithms and how they are implemented in the C programming language. We’ll start with the basics and gradually introduce more complex concepts, offering practical examples and code snippets along the way.

What is an Algorithm?

An algorithm, in the simplest terms, is a set of instructions designed to perform a specific task. It’s like a recipe in cooking, but instead of making a delicious meal, you’re solving a problem or completing a task in programming.

Why Learn Algorithms in C?

C is a powerful, efficient, and widely-used programming language that forms the basis for many modern languages. Learning algorithms in C can provide a solid foundation for understanding more complex programming concepts.

Basics of Algorithms in C

Before we dive into the deep end, let’s start with the basics. In C, algorithms often involve working with variables, constants, and data types. These are the building blocks of your code, and understanding them is crucial to implementing effective algorithms.

Variables and Constants

Variables are like containers that store data. Constants, on the other hand, are fixed values that do not change. In C, you’ll often use variables and constants to hold data that your algorithm will process.

Primitive and Structured Types

C has several primitive data types, including int (integer), char (character), and float (floating-point number). Structured types, like arrays and structures, allow you to group multiple variables together.

Implementing Algorithms in C

Now that we’ve covered the basics, let’s move on to implementing some simple algorithms in C. We’ll start with two of the most common types of algorithms: sorting and searching.

Sorting Algorithms

Sorting algorithms arrange elements in a certain order. The most common types are bubble sort and selection sort. Here’s a simple example of a bubble sort algorithm in C:

#include <stdio.h>

void bubbleSort(int array[], int size) {
  for (int step = 0; step < size - 1; ++step) {
    for (int i = 0; i < size - step - 1; ++i) {
      if (array[i] > array[i + 1]) {
        int temp = array[i];
        array[i] = array[i + 1];
        array[i + 1] = temp;
      }
    }
  }
}

int main() {
  int data[] = {-2, 45, 0, 11, -9};
  int size = sizeof(data) / sizeof(data[0]);
  bubbleSort(data, size);
  printf("Sorted Array in Ascending Order:\n");
  for (int i = 0; i < size; ++i) {
    printf("%d  ", data[i]);
  }
  return 0;
}


In this code, the bubbleSort function sorts an array of integers in ascending order. The main function creates an array of integers, calls the bubbleSort function to sort this array, and then prints the sorted array.

Searching Algorithms

Searching algorithms are used to find a specific item in a data structure. The simplest type of searching algorithm is a linear search, which checks each element in the data structure until it finds the target item. Here’s an example of a linear search algorithm in C:

#include <stdio.h>

int linearSearch(int array[], int size, int target) {
  for (int i = 0; i < size; ++i) {
    if (array[i] == target) {
      returni;
    }
  }
  return -1;
}

int main() {
  int data[] = {3, 4, 7, 2, 9};
  int size = sizeof(data) / sizeof(data[0]);
  int target = 7;
  int result = linearSearch(data, size, target);
  if (result != -1) {
    printf("Element found at index: %d", result);
  } else {
    printf("Element not found in the array.");
  }
  return 0;
}

In this code, the linearSearch function searches for a target integer in an array. If it finds the target, it returns the index of the target in the array. If it doesn’t find the target, it returns -1. The main function creates an array of integers, calls the linearSearch function to find the index of a target integer in this array, and then prints the result.

Basic Types of Algorithms

In the world of algorithms, there are a few basic types that you’ll come across again and again. Let’s take a closer look at four of them: Divide and Conquer, Dynamic Programming, Greedy Algorithms, and Backtracking.

Divide and Conquer

Divide and Conquer is a type of algorithm that breaks a problem into smaller subproblems until they become simple enough to solve directly. The solutions to the subproblems are then combined to give a solution to the original problem.

A classic example of a Divide and Conquer algorithm is the binary search algorithm. Here’s a simple implementation in C:

#include <stdio.h>

int binarySearch(int array[], int start, int end, int target) {
  if (end >= start) {
    int mid = start + (end - start) / 2;

    if (array[mid] == target)
      return mid;

    if (array[mid] > target)
      return binarySearch(array, start, mid - 1, target);

    return binarySearch(array, mid + 1, end, target);
  }

  return -1;
}

int main() {
  int data[] = {2, 3, 4, 10, 40};
  int size = sizeof(data) / sizeof(data[0]);
  int target = 10;
  int result = binarySearch(data, 0, size - 1, target);
  (result == -1) ? printf("Element is not present in array")
                 : printf("Element is present at index %d", result);
  return 0;
}

Code Explanation: Divide and Conquer: Binary Search

The binary search algorithm works by dividing the search space in half each time. It starts by comparing the target value to the middle element of the array. If they are not equal, the half in which the target cannot lie is eliminated, and the search continues on the remaining half until it is successful or the remaining half is empty.

In the provided code:

• The binarySearch function takes an array, a start and end index, and a target value as parameters.
• It calculates the middle index of the current search space and compares the value at this index with the target.
• If the target is found, it returns the index.
• If the target is less than the value at the middle index, it calls itself recursively with the first half of the array.
• If the target is greater, it calls itself recursively with the second half of the array.
• If the target is not found, it returns -1.

Dynamic Programming

Dynamic Programming is a method for solving complex problems by breaking them down into simpler subproblems. It is mainly used when the subproblems overlap, i.e., when the same subproblem is solved multiple times.

A common example of a Dynamic Programming problem is the Fibonacci sequence. Here’s how you can compute it in C:

#include <stdio.h>

int fibonacci(int n) {
  int f[n+2];
  int i;

  f[0] = 0;
  f[1] = 1;

  for (i = 2; i <= n; i++) {
    f[i] = f[i-1] + f[i-2];
  }

  return f[n];
}

int main () {
  int n = 9;
  printf("%d", fibonacci(n));
  return 0;
}

Code Explanation : Dynamic Programming: Fibonacci Sequence

The Fibonacci sequence is a series of numbers where a number is the sum of the two preceding ones, usually starting with 0 and 1. Dynamic programming is used to store the Fibonacci numbers calculated so far to avoid recalculating them.

In the provided code:

• The fibonacci function takes an integer n as a parameter.
• It initializes an array f of size n+2 to store the Fibonacci numbers.
• It sets the first two Fibonacci numbers f[0] and f[1] to 0 and 1, respectively.
• It calculates each Fibonacci number from f[2] to f[n] by adding the two preceding Fibonacci numbers and stores them in the array.
• It returns the nth Fibonacci number.

Greedy Algorithms

Greedy algorithms make the locally optimal choice at each stage with the hope of finding a global optimum. They are used for optimization problems.

A classic example of a problem that can be solved by a greedy algorithm is the coin change problem. Here’s a simple implementation in C:

#include <stdio.h>

void findMin(int cost, int coins[], int size) {
  for (int i = size - 1; i >= 0; i--) {
    while (cost >= coins[i]) {
      cost -= coins[i];
      printf("%d ", coins[i]);
    }
  }
}

int main() {
  int coins[] = {1, 2, 5, 10, 20, 50, 100, 500, 1000};
  int size = sizeof(coins)/sizeof(coins[0]);
  int cost = 93;

  printf("Following is minimal number of change for %d: ", cost);
  findMin(cost, coins, size);
  return 0;
}

Code Explanation: Greedy Algorithms: Coin Change

The coin change problem is an example of a greedy algorithm. The problem is to find the minimum number of coins that make a given value. The idea of the greedy algorithm is to choose the largest coin, as long as it doesn’t exceed the remaining value, and repeat this process until the remaining value is 0.

In the provided code:

• The findMin function takes a cost and an array of coins as parameters.
• It starts from the largest coin and subtracts it from the cost if it doesn’t exceed the remaining cost.
• It prints the coin used and repeats this process until the remaining cost is 0.

Backtracking

Backtracking is an algorithmic technique for solving problems recursively by trying to build a solution incrementally, one piece at a time, removing those solutions that

fail to satisfy the constraints of the problem at any point of time.

A classic example of a problem that can be solved using backtracking is the N-Queens problem, where you have to place N queens on an NxN chessboard so that no two queens threaten each other. Here’s a simple implementation in 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");
  }
}

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

bool solveNQUtil(int board[N][N], int col) {
  if (col >= N)
    return true;
  for (int i = 0; i < N; i++) {
    if (isSafe(board, i, col)) {
      board[i][col] = 1;
      if (solveNQUtil(board, col + 1))
        return true;
      board[i][col] = 0; // BACKTRACK
    }
  }
  return false;
}

bool solveNQ() {
  int board[N][N] = { {0, 0, 0, 0},
                      {0, 0, 0, 0},
                      {0, 0, 0, 0},
                      {0, 0, 0, 0} };
  if (solveNQUtil(board, 0) == false) {
    printf("Solution does not exist");
    return false;
  }
  printSolution(board);
  return true;
}

int main() {
  solveNQ();
  return 0;
}

Code Explanation in brief

In this code, the solveNQUtil function is a utility function to check if a queen can be placed on board[row][col]. If it can, then it calls itself to place queens in the next column. If it can’t place a queen, it backtracks and returns false. The solveNQ function solves the N Queen problem using Backtracking. It mainly uses solveNQUtil to solve the problem. It returns false if queens cannot be placed, otherwise, it returns true and prints placement of queens in the form of 1s.

Code Explanation in details: Backtracking: N-Queens Problem

The N-Queens problem is to place N queens on an NxN chessboard so that no two queens threaten each other. The idea of the backtracking algorithm is to place queens one by one in different columns, starting from the leftmost column. When placing a queen in a column, it checks for clashes with already placed queens. If it finds a place in the current column where there is no clash, it marks this cell and moves on to the next column. If it doesn’t find such a place, it backtracks and returns false.

In the provided code:

• The isSafe function checks if a queen can be placed at board[row][col] by checking if there is a queen in the same row or the same diagonal.
• The solveNQUtil function places queens in different columns.
• It calls isSafe to check if a queen can be placed at the current position. If it can, it marks this cell and moves on to the next column.
• If it can’t place a queen or if it has placed all the queens, it backtracks by unmarking this cell and returns false or true, respectively.
• The solveNQ function initializes the chessboard and calls solveNQUtil to solve the problem. If a solution exists, it prints the chessboard with queens; otherwise, it prints “Solution does not exist”.

I hope this provides a clearer understanding of the code snippets for each type of algorithm. Remember, understanding algorithms takes time and practice, so don’t worry if you don’t get everything right away. Keep studying and practicing, and it will start to make sense!

Wrapping Up

By now, you should have a solid understanding of algorithms in C. Remember, mastering algorithms takes time and practice, so don’t be discouraged if you don’t get everything right away. Keep studying and practicing, and you’ll get there!

Frequently Asked Questions (FAQ)

Related Tutorials

If you enjoyed this tutorial, you might also like these related tutorials:

1. Command Line Arguments in C
2. Function Pointers in C
3. Efficient Memory Management in C
4. Hashing in C
5. Multithreading in C
6. Network Programming in C
7. Building a Web Server in C
8. Advanced Algorithms in C
9. Building a Chat Application in C
10. Searching Algorithms in C
11. Sorting Algorithms in C