Data structures and algorithms

DS_Algo.md

Introduction

data structure are user to organize our data in a specific way to make the operation on the data will be easier and faster. The steps taken on the data structure to get the results out of the raw data is called algorithm.

Types

Data structure is of 2 types-

• Primitive - The data structure which is provided by the language we ra working on is called primitive dta structure. ex - Integer, Double, Float, Boolean in case of Java.
• Non-primitive - the data structure which is created with the help of the primitive DS is non-primitive DS. This can again be categorized into 2 types.
  1. Physical - DS which is physically present in the memory. ex - Array, linked list.
  2. Virtual - DS which is user defined and not directly present in memory. this takes help of physical and primitive DS to work. ex - stack queue, tree, graph.

Recursion

Any operation which is performed repeatedly with different data set to arrive at output is called a recursion. Here in every step we try to make the problem smaller and at last get the result.

In real world we use this in case of searching in binary tree search.

In the most popular kind of algorithms like greedy, divide and concur and dynamic programming recursion is used heavily. In case of tree and graph its kind of mandatory to use recursive programming to get the result.

Structure of Recursive method

A recursive code block has 2 elements -

1. Recursive code
2. break condition

How recursive method is stored in stack memory

Lets say we have a recursive method.

fun foo(input : Int){
    if(input == 1){
        return
    }
    foo(input - 1)
}

foo(3)

This code will save its calls in stack as follows

Stack Memory
foo(2)
foo(3)

Factorial with recursion

this is multiplication of 1 till n. where n is a non negative integer.

4! = 1 * 2 * 3 * 4 = 24

fun factorial(number : Int){
    if(number == 1)
        return 1
    factorial(number * factorial(number - 1))
}

factorial(4)

//first recursion
//factorial(4) >> 4 * factorial(3)
//factorial(3) >> 3 * factorial(2)
//factorial(2) >> 2 * factorial(1)
//return 1
//return 2 * 1
//return 3 * 2
//return 4 * 6
//return 24 <<result

The function has a break condition and a recursion code block.

Fibonacci Series

this is the contentious addition of previous two number in a series. the first two number are 0 and 1. which makes it 0, 1, 1, 2, 3, 5, 8 ...

fun fibo(fibboIndex : Int){
    if(fibboIndex == 0 || fibboIndex == 1)
        return 1
        
    return (fibo(fibboIndex - 2) + fibbo(fibboIndex - 1))
}

fibbo(5)

/*
fibbo(3) + fibbo(4)
fibbo(1) + fibbo(2) + fibbo(2) + fibbo(3)
1 + fibbo(0) + fibbo(1) + fibbo(0) + fibbo(1) + fibbo(1) + fibbo(2)
1 + 1 + 1 + 1 + 1 + 1 + fibbo(0) + fibbo(1)
1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
8 << Result
*/

Recursion Vs Iteration

• We can solve the problem of recursion also with iteration.
• Also recursion has disadvantage of space and time over iteration, and iteration takes teh head in these case.

When to use recursion

• We can use recursion when
  1. We can divide problem into similar sub problems.
  2. We can compromise with time and space.
  3. We want a quick solution over a efficient one.

Practical use of recursion

We use recursion in stack, tree, sorting, divide and concur, dynamic programming.

Algorithm Run time analysis

This is the measurement of performance of any algorithm.

Notation for alg runtime

• Omega ( Ω ) - Lower bound of an algorithm. minimum run time of an algorithm. or we can say that the best case scenario for the algorithm.
• Big-o ( O ) - Upper bound for an algorithm. this is the worst case for the algorithm.
• Theta ( θ ) - Decides if the upper and lower bound of an algorithm are same or not. or in other words it says what is the average time for and algorithm.

Algorithm time analysis in 1D array

lets say we have an array - 5, 10, 45, 43, ..., 34, 5, 23, 1, ...

and now if we want to search for 43. and lets say it took 10 n time to find the value in the array. where n is time taken to traverse 1 element.

• here the omega for the algorithm would be - n
• big-o would be - number of elements * n
• theta would be - n / 2

Examples of algorithm run time complexity

• order of 1 or constant time complexity.
• order of log n
• order of n - linear time complexity
• order n log n - linear logarithmic complexity
• order n Sq
• order n Cube
• order 2 power n - exponential time complexity