PRELIMINARIES - Mathematical Notations and Functions, Algorithmic Notation, Control Structures.

Introduction-

The development of algorithms for creating and processing data structures is a key feature of this text. Computer programs that implement complex algorithms are easier to understand when organized into module hierarchies. In this structure, each program starts with a main module that provides a general description of the algorithm. This main module refers to submodules that contain more detailed information. Each submodule may, in turn, refer to even more detailed submodules, and so on. In the Preliminaries, we will learn about various mathematical functions that are important in the study of algorithms in computer science. Measuring algorithms is crucial as it allows us to compare different algorithmic solutions to a particular problem. These concepts apply not only to data structures but also to almost all areas of computer science.

Mathematical Notations and Functions-

A little explanation of each of the mathematical notations and functions used in data structures and algorithms:

Certainly! Let's add the requested details and explanations:

Floor and Ceiling Functions

• Floor Function (⌊x⌋):

  • Definition: The largest integer less than or equal to x.

  • Example: ⌊3.7⌋ = 3, ⌊-2.3⌋ = -3.

• Ceiling Function (⌈x⌉):

  • Definition: The smallest integer greater than or equal to x.

  • Example: ⌈3.7⌉ = 4, ⌈-2.3⌉ = -2.

Remainder Function

• Remainder Function (a % b or k (mod M)):

  • Definition: The remainder of the division of a by b.

  • Example: 7 % 3 = 1, 10 % 2 = 0.

  • Notation Explanation: ( k*r =mod{M} ) where ( k = r + M*q ) for some integer ( q ) and ( 0<r< M ).

  • Example: If ( k = 7 ) and ( M = 3 ), then ( k \mod M = 1 ) because ( 7 = 1 + 3*2 ).

Integer and Absolute Value Functions

• Integer Function (int(x)):

  • Definition: The integer part of x (truncates the decimal part).

  • Example: int(3.7) = 3, int(-2.3) = -2.

• Absolute Value Function (|x|):

  • Definition: The non-negative value of x without regard to its sign.

  • Example: |3| = 3, |-3| = 3.

Summation Symbol

• Summation (∑):

  • Definition: The sum of a sequence of numbers.

  • Example: ∑ (i = 1 to n) i = 1 + 2 + 3 + ... + n.

Factorial Function

• Factorial (n!):

  • Definition: The product of all positive integers less than or equal to n.

  • Recursive Definition: For ( n > 1 ), ( n! = n \times (n-1)! ).

  • Example: 5! = 5 × 4 × 3 × 2 × 1 = 120.

  • Recursive Example: 5! = 5 × 4! = 5 × 4 × 3! = 5 × 4 × 3 × 2! = 5 × 4 × 3 × 2 × 1! = 120.

Permutation

• Permutation (P(n, r)):

  • Definition: The number of ways to arrange r elements from a set of n elements.

  • Formula: ( P(n, r) = \frac{n!}{(n-r)!} ).

  • Example: ( P(5, 2) = \frac{5!}{(5-2)!} = \frac{120}{6} = 20 ).

Exponent and Logarithm

• Exponent (a^b or exp):

  • Definition: The result of raising a to the power of b.

  • Example: 2^3 = 8.

• Logarithm (log_b(a)):

  • Definition: The power to which the base b must be raised to produce a.

  • Example: log_2(8) = 3 because 2^3 = 8.

Types of Logarithms:

• Common Logarithm (log or log_10):

  • Base 10 logarithm.

  • Example: log_10(100) = 2 because 10^2 = 100.

• Natural Logarithm (ln or log_e):

  • Base e (where e is approximately 2.71828).

  • Example: ln(e) = 1 because e^1 = e.

• Binary Logarithm (log_2):

  • Base 2 logarithm.

  • Example: log_2(8) = 3 because 2^3 = 8.

Undefined Logarithms:

• Logarithm of Zero:

  • Undefined because no number raised to any power will equal zero.

• Logarithm of Negative Numbers:

  • Undefined in the set of real numbers because a positive base raised to any real power cannot yield a negative result.

Understanding these mathematical notations and functions is crucial for solving problems in data structures and algorithms efficiently. They form the basis for analyzing time complexity, space complexity, and other properties of algorithms.

Algorithmic Notations-

An algorithm is said to be a finite step-by-step list of well-defined instructions for solving a particular problem.

Let's take an example for better understanding:

Let's say We have an array DATA of numerical values in memory. We want to find the location LOC and the value MAX of the largest element of DATA. Except these we don't have any other information.

Approach: Initially we can begin with LOC=1 and MAX=DATA[1] with each successive element DATA[i] of DATA. If DATA[i] exceeds MAX then update LOC to i and MAX to DATA[i]. Continuously traverse the whole array to check where the MAX value is.

The Diagram for this approach is given below-

And Here's the implementation of this algorithm in C Language-

#include <stdio.h>

int main(){
    int DATA[10]={22,65,1,99,32,17,74,49,33,2};
    int N,LOC, MAX, k;
    N=10;
    k=0;
    LOC=0;
    MAX=DATA[0];

    for(int i=0; i<N;i++){
        k=k+1;
        if(k==N){
            printf("LOC=%d, MAX=%d",LOC,MAX);
        }
        if(MAX<DATA[k]){
            LOC=k;
            MAX=DATA[k];
        }
    }
    return 0;
}

While writing and implementing algorithms we need to be aware of some things-

1. Input/Output.

2. Variable Names.

3. Identifying Number.

4. Comments.

5. Assignment Statement.

6. Procedures.

Control Structures-

We've Three types of Control Strucures-

1. Sequence Logic

#include <stdio.h>

int main(){
    printf("Step 1: Read input data.\n");
    printf("Step 2: Process the data according to specified calculations.\n");
    printf("Step 3: Output the result.\n");
    return 0;
}

In this example, each printf statement executes in sequence, performing steps one after another.

2. Selection Logic (Conditional Statements)

#include <stdio.h>

int main(){
    int x=10;
    if(x>0){
        printf("x is positive.\n");
    }
    if(x%2==0){
        printf("x is even.\n");
    }else{
        printf("x is odd.\n");
    }

    if(x>0){
        if(x%2==0){
            printf("x is a positive even number.\n");
        }else{
            printf("x is a positive odd number.\n");
        }
    }else{
        printf("x is not a positive number.\n");
    }

    return 0;
}

These examples demonstrate conditional statements (if, if-else, and nested if-else) in C, which allow the program to make decisions based on the value of x.

3. Iteration Logic (Loops)

#include <stdio.h>

int main() {
    int i;

    // For loop example
    printf("For loop example:\n");
    for(i=1; i<=5; i++){
        printf("%d ", i);
    }
    printf("\n");

    // While loop example
    printf("While loop example:\n");
    i=1;
    while(i <= 5){
        printf("%d ", i);
        i++;
    }
    printf("\n");

    // Do-while loop example
    printf("Do-while loop example:\n");
    i = 1;
    do{
        printf("%d ", i);
        i++;
    } while(i <= 5);
    printf("\n");

    return 0;
}

These examples demonstrate different types of loops (for, while, and do-while) in C. Each loop prints numbers from 1 to 5 sequentially. Note how the do-while loop guarantees at least one execution even if the condition is false initially.

That's all for today. To recap, we've discussed Mathematical Functions and Notations, including Exponents and Logarithms, as well as Algorithmic Notations and Control Structures.