210280116514 Chavda Urvashi Analysis & Design of Algorithm

Lab Manual of Analysis,

Design and Algorithms
(2150703)

L.D. College Of Engineering

Navarangpura, Ahmedabad.
(Affiliated to Gujarat Technological
University)
 210280116514 Chavda Urvashi Analysis & Design of Algorithm

INDEX
Sr Practical Start End Sign
No. date date

1 Implementation and Time analysis of sorting

algorithms. Bubble sort, Selection sort,
Insertion sort, Merge sort and Quick sort

2 Implementation and Time analysis of linear and

binary search algorithm.

3 Implementation of max-heap sort algorithm

4 Implementation and Time analysis of factorial

program using iterative and recursive method

5 Implementation of a knapsack problem using

dynamic programming

6 Implementation of chain matrix multiplication

using dynamic programming

7 Implementation of making a change problem

using dynamic programming

8 Implementation of a knapsack problem using

greedy algorithm

9 Implementation of Graph and Searching (DFS

and BFS)

10 Implement prim’s algorithm

 210280116514 Chavda Urvashi Analysis & Design of Algorithm

11 Implement kruskal’s algorithm.

12 Implement LCS problem.

210280116514 Chavda Urvashi Analysis & Design of Algorithm

Practical- 1
Aim: Implementation and Time analysis of sorting algorithms. Bubble sort,
Selection sort, Insertion sort, Merge sort and Quick sort.

>>Bubble Sort
Explanation:

Algorithm:

1. We are given with an input array which is supposed to be sorted in

ascending order
2. We start with the first element and i=0 index and check if the element
present at i+1 is greater then we swap the elements at index i and i+1.
3. If above is not the case, then no swapping will take place.
4. Now  “ i ” gets incremented and the above 2 steps happen again until the
array is exhausted.
5. We will ignore the last index as it is already sorted.
6. Now the largest element will be at the last index of the array.
210280116514 Chavda Urvashi Analysis & Design of Algorithm

7. Now we will again set i=0 and continue with the same steps that will
eventually place second largest at second last place in the array. Now the
last 2 indexes of the array are sorted.

Analysis:
Time Complexity

 Each and every element is compared with the other elements for array
which takes n time
 And the above steps continues for n iterations
 Best Time Complexity: O(n^2)
 Average Time Complexity: O(n^2)
 Worst Time Complexity: O(n^2)

Space Complexity

 No auxiliary space is required in bubble sort implementation

 Hence space complexity is: O(1)
210280116514 Chavda Urvashi Analysis & Design of Algorithm

>>Selection Sort

Explanation:

Algorithm:

 Set min  index to the first index of an unsorted array

 Iterate the entire unsorted array and do the comparison with min
 If element present at the min is greater than the element present at the
current index then update min with a current index
 Once the iteration is complete, swap the element of min index with the
first element of the unsorted part
 For descending order, instead of maintaining the smallest element index,
maintain the largest element index
210280116514 Chavda Urvashi Analysis & Design of Algorithm

Analysis:
Time Complexity

 In the worst case, in every iteration, we have to traverse the entire array
for finding min elements and this will continue for all n elements. Hence
this will perform n^2 operations in total. 
 In the best case that is sorted array, we can do some modification by
using lag to check whether the lament is already sorted or not
 Best Time Complexity: O(n)
 Average Time Complexity: O(n^2)
 Worst Time Complexity: O(n^2)

Space Complexity

 No auxiliary space is required in Selection Sort implementation that is

we are not using any arrays, linked list, stack, queue, etc to store our
elements
 Hence space complexity is: O(1)
210280116514 Chavda Urvashi Analysis & Design of Algorithm

>>Insertion sort

Explanation:

Algorithm:

 Take the first element and consider it to be a sorted part(a single element
is always sorted)
 Now pick arr[1] and store it is a temporary variable
 Start comparing the values of tmp with elements of the sorted part from
the rear side
 If tmp is less than the rear element, say arr[k], then shift arr[k] to k+1
index
 This shifting will continue until the appropriate location is identified.
Then, we will put the temporary element at the identified location
210280116514 Chavda Urvashi Analysis & Design of Algorithm

 This will continue for all the elements, and we will have our desired
sorted array in ascending order

Analysis:

Time Complexity

 In the worst-case scenario, n will pick all elements and then n shifts to set
it to the right position
 In the best-case scenario, that is a sorted array, we will just pick the
elements, but no shifting will take place leading it to n time complexity,
that is, every element is traversed at least once
 Best Time Complexity: O(n)
 Average Time Complexity: O(n^2)
 Worst Time Complexity: O(n^2)

Space Complexity

 No auxiliary space is required in insertion sort implementation. That is,

we are not using any arrays, linked list, stack, queue, etc, to store our
elements
 Hence space complexity is: O(1)
210280116514 Chavda Urvashi Analysis & Design of Algorithm

>>Merge sort

Explanation:

Algorithm:

 Declare left and right var which will mark the extreme indices of the array
 Left will be assigned to 0 and right will be assigned to n-1
 Find mid = (left+right)/2
 Call mergeSort on (left,mid) and (mid+1,rear)
 Above will continue till left<right
210280116514 Chavda Urvashi Analysis & Design of Algorithm

 Then we will call merge on the 2 sub-problems.

Analysis:

Time Complexity

 In the worst case, in every iteration, we are dividing the problem into
further 2 subproblems. Hence this will perform log n operations and this
has to be done for n iteration resulting in n log n operations total. 
 In the best case that is sorted array, we can do some modification by
using a flag to check whether the lament is already sorted or not
 Best Time Complexity: O(nlogn)
 Average Time Complexity: O(nlogn)
 Worst Time Complexity: O(nlogn)

Space Complexity 

 n auxiliary space is required in Merge Sort implementation as all the

elements are copied into an auxiliary array
 Hence space complexity is: O(n)

>>Quicksort
210280116514 Chavda Urvashi Analysis & Design of Algorithm

Explanation:

Algorithm:

 We are given with an input array

 Choose pivot, here we are choosing the last element as our pivot
 Now partition the array as per pivot
o Keep a partitioned index say p and initialize it to -1
o Iterate through every element in the array except the pivot
o If an element is less than the pivot element then increment p and
swap the elements at index p with the element at index i.
o Once all the elements are traversed, swap pivot with element
present at p+1 as this will the same position as in the sorted
array
o Now return the pivot index
 Once partitioned, now make 2 calls on quicksort
o One from beg to p-1
o Other from p+1 to n-1
210280116514 Chavda Urvashi Analysis & Design of Algorithm

Analysis:

Time Complexity

 Partition of elements take n time

 And in quicksort problem is divide by the factor 2
 Best Time Complexity : O(nlogn)
 Average Time Complexity : O(nlogn)
 Worst Time Complexity : O(n^2)
 Worst Case will happen when array is sorted

Space Complexity

 O(n) : basic approach

 O(logn) : modified approach