Introduction To Algorithms

What is an Algorithm?

An algorithm is a step-by-step procedure or formula for solving a problem. It is a sequence of finite steps that lead to a specific goal. In computer science, algorithms are essential for writing efficient and effective programs. They are used for data processing, calculations, automated reasoning, and other tasks.

Basic Properties of Algorithms

To be considered an algorithm, a sequence of instructions must possess the following properties:

Finiteness: An algorithm must terminate after a finite number of steps.
Definiteness: Each step of the algorithm must be precisely defined; the actions to be carried out must be rigorously and unambiguously specified for each case.
Input: An algorithm has zero or more inputs, taken from a specified set of objects.
Output: An algorithm has one or more outputs, which are the quantities produced by the algorithm.
Effectiveness: All operations to be performed in the algorithm must be sufficiently basic that they can be done exactly and in a finite length of time.

Examples of Algorithms in C

Let's look at some simple examples of algorithms implemented in the C programming language.

Example 1: Finding the Maximum of Two Numbers

The following C program finds the maximum of two numbers:

#include <stdio.h>

int main() {
    int num1, num2, max;
    printf("Enter two numbers: ");
    scanf("%d %d", &num1, &num2);
    if (num1 > num2)
        max = num1;
    else
        max = num2;
    printf("Maximum number is: %d\n", max);
    return 0;
}

Example 2: Bubble Sort

Bubble Sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order. The pass through the list is repeated until the list is sorted. Here is a C program to sort an array using Bubble Sort:

#include <stdio.h>

void bubbleSort(int arr[], int n) {
    int i, j, temp;
    for (i = 0; i < n-1; i++) {
        for (j = 0; j < n-i-1; j++) {
            if (arr[j] > arr[j+1]) {
                temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}

void printArray(int arr[], int size) {
    int i;
    for (i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr)/sizeof(arr[0]);
    bubbleSort(arr, n);
    printf("Sorted array: \n");
    printArray(arr, n);
    return 0;
}

Algorithm Complexity

Algorithm complexity refers to the amount of computational resources that an algorithm requires. The most common metrics are time complexity and space complexity.

Time Complexity

Time complexity is a measure of the amount of time an algorithm takes to process input data of a given size. It is commonly expressed using Big O notation, which describes the upper bound of the time required as a function of the input size.

Space Complexity

Space complexity is a measure of the amount of memory space an algorithm uses during its execution. This includes the memory space needed for the input data, as well as the memory space needed for the algorithm to process the data.

Conclusion

In this tutorial, we have introduced the concept of algorithms, discussed their basic properties, and provided examples of simple algorithms in C. We also touched upon the importance of algorithm complexity. Understanding algorithms and their properties is crucial for writing efficient and effective programs. As you continue your studies, you will encounter many more complex algorithms and learn how to analyze their performance.