Algorithm Spring semester

Table of contents:

• Algorithm
• Characteristics
• Need for analysis of algorithm
• Design strategis
• Pros and Cons of divide and conquer
• Application of Divide and Conquer Approach
• Data Structure
• Big O Notation
• Big Omega Notation
• Big Theta Notation
• Selection Sort
• Selection sort in python

Algorithm

Defⁿ :

step by step procedure,every procedure have many instructions,every instruction have many logical instruction and every instruction goes to output

Characteristics:

1. Deterministic
   • It is known , what is the goal of the algorithm
2. Termination
   • An algorithm must be terminated
3. input
4. output

Need for Analysis of Algorithm

• Analysis of algorithm is the process of analyzing the problem sovling capabilities depends on time and space
  1. worst case
     • maximum number of steps
  2. Best case
     • minimum number of steps
  3. Average case
     • Average number of steps

Design Strategies

• Many algorithm are recursive in nature to solve a given problem recursively to dealing with sub-problems

• In divide and conquer approach , a problem is divided into smaller problems,then the smaller problems are solved independently and finally smaller problems are combined into a solution for the large problem

  Generally divide and conquer algorithms have 3 parts

  1. Divde the problem into a number of sub-problems
  2. Conquer the sub-problems by solving them recursively
  3. Combine the solution to the sub-problem into the solution for the original problem

Pros and Cons of Divide and Conquer

• An algorithm which is designed using this technique, can run on the multiprocessor system or in different machines simultaneously
• In this approach, most of the algorithms are designed using recursion,hence memory management is very high
• For recursive function stack is used, where function state needs to be stored

Application of Divide and Conquer Approach

• Following are some problems, which are solved using divide and conquer approach
  • Finding the maximum and minimum of a sequence of numbers
  • Matrix Multiplication
  • Merge Sort
  • Binary Search

Data Structure:

A way to store , organise and manipulate data within a computer, in an efficient manner

Asymptotic Notation: 3 types:-

1. Big oh - O()
2. Big omega - Ω()
3. Big theta - Θ()

Big Oh Notation:

If ∃ (there exists or there is at least one) constants a,k > 0 such f(n) ≤ a * g(n) and ∀ n ≥ k, then f(n) = O(g(n))

• Upper bound on the order of growth of a function

Graphical Representation:

Example:

f(n) = 20n³ + 5n² + 3

g(n) = n³

Is it f(n) = O(g(n))?

Solution:

we know, If ∃ (there exists or there is at least one) constants a,k > 0 such f(n) ≤ a * g(n) and ∀ n ≥ k, then f(n) = O(g(n)) so, we get,

20n³ + 5n² + 3 ≤ 20n³ + 5n³ + 3n³

or, 20n³ + 5n² + 3 ≤ 28n³

so, a = 28 and b = 1 and all other conditions a * g(n) satisfied

Big Omega Notation

If ∃ (there exists or there is at least one) constants a,k > 0 such f(n) ≥ a * g(n) and ∀ n ≥ k, then f(n) = Ω(g(n))

Graphical View:

Big Theta Notation

If ∃ (there exists or there is at least one) constants a₁,a₂,k > 0 such that a ₁ x g(n) ≤f(n) ≤ a ₂ x g(n) and ∀ n ≥ k, then f(n) = Θ(g(n))

Graphical View:

Example:

f(n) = n² + 2 g(n) = n² Is that , f(n) = Θ(g(n))?

Solution:

If ∃ (there exists or there is at least one) constants a1,a2,k > 0 such that a 1 x g(n) ≤f(n) ≤ a 2 x g(n) and ∀ n ≥ k, then f(n) = Θ(g(n))

1 * n ² ≤ n ² + 2 ≤ 2 + n ²

so, a₁ ,a₂ = 2 and b = 1

and all other condition satisfied

so, we can say, f(n)= Θ(g(n))

Selection Sort

• In this technique, we find the smallest-element and place it in the appropirate position
• If we have n elements then it requires (n-1) pass to sort the elements

  Array

Here, we have 5 elements . so we need (5-1) = 4 pass to sort the array

Pass1:

In pass1 smallest element is searched between A[0] to A[4] and swapped with A[0]

Pass2:

In pass 2 smallest element is searched between A[1] to A[4] and swapped with A[1]

Pass3:

In pass 3 smallest element is searched between A[2] to A[4] and swapped with A[2]

Pass4:

In pass 4 smallest element is searched between A[3] to A[4] and swapped with A[3]

Selection Sort in python

# Array elements
A = [ 3,7,6,2,1]
# Traverse through all array elements
for i in range(len(A)):
    # let mimimum value of index
    minimum = i
    # find the minimum element in unsorted array
    for j in range(i+1,len(A)):
        if A[minimum] > A[j]:
            minimum = j
    # swap the minimum element with first elment
    A[i], A[minimum] = A[minimum], A[i]
#Print sorted array
print("Sorted Array:")
for i in range(len(A)):
    print("%d" %A[i]),

Sorted Array:
1
2
3
6
7

Space Complexity

Analysis of space complexity of an algorithm or program is the ? amout of memory it needs to run to completion some of the reasons for swapping

space complexity are:

1. Swapping without third variable
2. longest number finding with ternary operator

• If the program is to run variable on multiuser system,it may be required to specify the amount of memory to be allocated to program

• To Know in advance that sufficient memory is available to run the program

• Can be used to estimate the size of the largest problem that a program can solve.

Merge Sort Algorithm

Merge(A,p,n,q,r)
    n1 = q-p+1
    n2 = r-q
Let L(1....n1 + 1) and R(1 to n2+1) be new arrays
for ( i = 1 to n1)
    L[i] = A[p+i-1]
for(j=1 to n2)
    R[j] = A[q+j]
L[n1+1] = infinity
R[n2+1] = infinity
i = 1
j = 1
for(k=p to r)
    if(L[i] <= R[j])
        A[k] = L[i]
        i+=1
    else
        A[k] = R[j]
        j += 1

explanation

dividing array elements

Knapsack Problem

Given, total knapsack weight = 16

Array of weight = 16

Array of weight (w1,w2,w3,w4,w5,w6) = (1,3,5,6,3,10)

Array of Profit (p1,p2,p3,p4,p5,p6) = (3,5,8,6,1,2)

Knapsack Solution

Binary Search Algorithm

Binary(data, lb, ub, item, loc)

[Here ,data is a sorted array, where lower bound is ‘LB’,upper bound =’UB’,item = identified data element]

Beg, End, Mid 3 variables => where beg = 1st segment, end = end segment and mid = Middle segment of array element

1. beg := LB, end := UB , and Mid := Int( ( beg + end ) / 2 )
2. beg <= end and data[mid] != item
   • repeat step 3 and 4

3. If item < data[mid]

   end = mid -1

   else

   beg = mid + 1

4. Mid := Int( ( beg / end ) / 2 )

5. If data[mid] = item

   loc = mid

   else

   loc = null

Bubble Sort

let data elements A[1] A[2] …. A[N]

step1:

Compare A[1] and A[2] if A[1] > A[2] then swapping

if A[1] < A[2] then no change,no swapping

Pass1:

1. 32 < 51 , swap no
2. 51 > 27 swapping

1. 51 < 85 , now swap
2. 85 > 66 , swapping

1. 85 > 23 , swapping

1. 85 > 13, swapping

1. 85 > 57 , swapping

pass2 and others:

please try yourself

Algorithm Bubble sort

 BubbleSort(A)

    for i in range(1,length(A))
      do for i length(A) down to i+1
        do if A[j] < A[j-1]
          then exchange A[j] <-> A[j-1]

Longest Increasing Subsequence

Given Sequence : 1 , 6, 2, 4, 5, 0

subsequence : (2) or (1,4) or(6,4,0)

Increasing Subsequence : ( 1,6),(1,2)(1,2,4)

Notice that (1),(6),(5) etc are also increasing subsequence

Increasing Sequence : (1),(6),(2),(4),(5),(0)

= (1,6),(1,2),(1,2,4),(1,2,4,5),(0)

LIS = 1 2 2 3 4 1

so answer = maxof(LIS) = 4

Selection Sort in C++

Selection Sort in c++

Insertion Sort in C++

Insertion Sort in c++