Data Structures & Algorithms

Definition: A Stack is a linear data structure in which insertion and deletion operations are performed at only one end called the 'top'.

It works on the principle of LIFO (Last In First Out). The element which is inserted at the last will be removed first.

Input Variables:

• stack: denotes the array name.
• n: denotes the size of the array.
• top: denotes the index of the topmost element. Initialized to top = -1.
• value: denotes the element to be inserted into the stack.

Operations & Algorithms

1. Push (Inserting an element)

Algorithm push (stack, n, top, value)
{
    if (top == n - 1)
        Print ("stack full transaction insertion can't be perform")
    else
    {
        top++
        stack[top] = value
    }
}

2. Pop (Deleting an element)

Algorithm pop ()
{
    if (top == -1)
        print "stack empty deletion not possible"
    else
    {
        Print stack[top] "Deleted"
        top--
    }
}

3. Peak / Peek (Retrieving topmost element)

Algorithm peek ()
{
    if (top == -1)
        print "stack empty"
    else
        print stack[top] "is the topmost element"
}

4. Traverse (Displaying all elements)

Alg traverse ()
{
    if (top == -1)
        print "stack empty"
    else
        for i = top to 0 (i--)
            print stack[i]
}

Input Variables:

• a: denotes the array.
• n: denotes the current size of the array.
• pos: denotes the index position to insert/delete an element.
• value: denotes the element value.
• max: denotes the maximum size of an array.

1. Insert Operation

Alg Array insert(a, n, pos, value)
{
    if (n == max)
        print "Array full, Insertion not possible"
    else
    {
        for i = n - 1 to pos  // (for i=n-1; i>=pos; i--)
            a[i+1] = a[i]
        
        a[pos] = value
        n = n + 1
    }
}

2. Delete Operation

Alg Array delete(a, n, pos)
{
    if (n == 0)
        print "Array empty, deletion not possible"
    else
    {
        for i = pos to n - 2  // (for i=pos; i<n-1; i++)
            a[i] = a[i+1]
        
        n = n - 1
    }
}

3. Traverse Operation

Algorithm Traversal(a, n)
{
    for i = 0 to n - 1
        print a[i]
}

Definition: Asymptotic notation is the mathematical representation of an algorithm to analyze its performance. It measures:

• Time Complexity: Amount of time required to solve a problem.
• Space Complexity: Amount of memory required by an algorithm to solve a problem.

1. Big Oh Notation ($O$)

• It is used to find the upper bound value (Worst-case running time).
• Definition: $f(n)$ is $O(g(n))$, if there exist positive constants $c$ and $n_0$ such that:
  $f(n) \le c \cdot g(n)$ , for all $n \ge n_0$ (where $c > 0, n \ge 1$)
• Example: $f(n) = 2n + 5 \le 3n \implies O(n)$

2. Big Omega Notation ($\Omega$)

• It is used to find the lower bound value (Best-case running time).
• Definition: $f(n)$ is $\Omega(g(n))$, if there exist positive constants $c$ and $n_0$ such that:
  $f(n) \ge c \cdot g(n)$ , for all $n \ge n_0$ (where $c > 0, n \ge 1$)
• Example: $2n + 5 \ge 2n \implies \Omega(n)$

3. Big Theta Notation ($\Theta$)

• It is used to find the average bound value.
• Definition: $f(n)$ is $\Theta(g(n))$, if there exist positive constants $c_1$ and $c_2$ such that $f(n)$ is greater than or equal to $c_1 \cdot g(n)$ and less than or equal to $c_2 \cdot g(n)$.
  $c_1 \cdot g(n) \le f(n) \le c_2 \cdot g(n)$ , for all $n \ge n_0$ (where $c_1 > 0, c_2 > 0, n \ge 1$)

Linear Search

Definition: A searching algorithm that sequentially checks each element in a list until the target key is found.

• Input: n denotes size, a is an array, key is the search element.
• Output: To find the index position of the search element.
• Complexity: $O(n)$

Algorithm Linearsearch(n, a, key)
{
    for i = 0 to n - 1
        if (key == a[i]) {
            print i
            break;
        }
    if (i == n)
        print "Not found"
}

Binary Search

Definition: A searching algorithm used in a sorted array by repeatedly dividing the search interval in half.

• Complexity: $O(\log n)$

Algorithm binary search(a, n, key)
{
    l = 0;
    h = n - 1;
    while (l <= h)
    {
        mid = (l + h) / 2
        if (key == a[mid]) {
            write mid
            break;
        }
        else if (key > a[mid])
            l = mid + 1
        else if (key < a[mid])
            h = mid - 1
    }
}

Bubble Sort

Definition: It works by repeatedly comparing and swapping adjacent elements. The largest elements "bubble up" to the end.

• Complexity: Worst/Average Case is $O(n^2)$. Best case is $O(n)$.

Algorithm bubble sort(a, n)
{
    for i = 0 to n - 1             // Outer loop for passes
    {
        for j = 0 to n - 1 - i     // Inner loop for comparisons
        {
            if (a[j] > a[j+1])
            {
                swap(a[j], a[j+1]) // Temporary variable logic
            }
        }
    }
}

Insertion Sort

Definition: Splits the array into a sorted and unsorted section. Iteratively picks the first element from the unsorted section and inserts it into its correct position within the sorted section.

Algorithm insertionSort(arr, n)
{
    for i = 1 to n - 1
    {
        key = arr[i];
        j = i - 1;
        while (j >= 0 && arr[j] > key) 
        {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

Selection Sort

Definition: Sorts an array by repeatedly finding the minimum element from the unsorted portion and swapping it with the first element of the unsorted portion.

Algorithm selectionsort(arr, n) 
{ 
    for i = 0 to n - 1
    { 
        small = i;               
        for j = i + 1 to n - 1
        {
            if (arr[j] < arr[small]) 
                small = j;       
        } 
        swap(arr[i], arr[small]); 
    } 
}

Definition:

• Infix: Operator is placed between two operands (e.g., A + B).
• Postfix: Operator is placed after the operands (e.g., A B +).

A stack is used to hold operators until they can be added to the postfix output based on operator precedence rules.