Enrollment No.

___________________ Name___________________________

INDEX

Page
List of Practical Date Sign
No.
1: Implement and perform time analysis of following algorithms

1.1 Linear Search algorithm.

Selection Sort, Bubble Sort and Insertion Sort
1.2
algorithms.
1.3 Max Heap Sort algorithm.
Find factorial number of given integer using
1.4
iterative and recursive method.

2: Implement and perform time analysis of following using divide and conquer
method.
2.1 Binary Search
2.2 Merge Sort
2.3 Quick Sort

3: Implement following greedy algorithms

3.1 Fractional Knapsack Problem

3.2 Activity Selection
3.3 Job Scheduling
3.4 Prim’s Algorithm
3.5 Krushkal’s Algorithm

4: Implement following using dynamic programming method.

4.1 Making Change Problem

4.2 0/1 Knapsack Problem
4.3 Longest Common Subsequence
4.4 Chained Matrix Multiplication

5: Implement following algorithms for graph

5.1 Breadth First Search

5.2 Depth First Search

Government Engineering College, Rajkot

Enrollment No.___________________ Name___________________________

Assignments

Sr. No. Assignment Date Page No. Sign

Government Engineering College, Rajkot

Enrollment No.___________________ Name___________________________

Linear Search Output

Best case: search first element of array

Worst case: element not found in array

No. of elements (N) Best Case Running Worst Case

Time (milliseconds) Running Time
(milliseconds)
1000
2000
3000
4000
5000
6000
7000
8000
9000
10000

Government Engineering College, Rajkot

 No. of No. of
case
Best

9000
8000
7000
6000
5000
4000
3000
2000
1000
9000
8000
7000
6000
5000
4000
3000
2000
1000

Case
elements (N) elements (N)

10000
10000

Worst
No. of No. of
comparisons comparisons

No. of No. of
swapping swapping

Selection
Selection

Running Time Running Time

Enrollment No.___________________

(milliseconds) (milliseconds)

No. of No. of
comparisons comparisons

No. of No. of
swapping swapping

Bubble
Bubble

Running Time Running Time

Government Engineering College, Rajkot

(milliseconds) (milliseconds)

No. of No. of
comparisons comparisons

No. of No. of
Name___________________________

swapping swapping
Insertion
Insertion

Running Time Running Time

(milliseconds) (milliseconds)
Enrollment No.___________________ Name___________________________

Binary Search Output

Take Sorted array as input.

In best case, consider middle element of array for search.
In worst case, consider element not found in array

No. of elements (N) Best Case Running Worst Case

Time (milliseconds) Running Time
(milliseconds)
1000
2000
3000
4000
5000
6000
7000
8000
9000
10000

Government Engineering College, Rajkot

Enrollment No.___________________ Name___________________________

Factorial Number Output

Factorial (N) Iterative Method Recursive Method

Running Time Running Time
(milliseconds) (milliseconds)
5
6
7
8
9
10
11
12
13
14

Government Engineering College, Rajkot

Enrollment No.___________________ Name___________________________

Take all the input elements in sorted order.

In quick sort – best case, select middle element of array as pivot
In quick sort – worst case, select first element of array as pivot

Merge Sort Quick Sort

Best Case Worst Case

(milliseconds)

(milliseconds)

(milliseconds)
No. of Merge
elements (N)

Partition

Partition
Running

Running

Running
No. of

No. of
No. of
Time

Time

Time
Calls

Calls

Calls
10
15
20
25
30

Government Engineering College, Rajkot

Enrollment No.___________________ Name___________________________

Heap Sort Output

Consider best case as already sorted array and worst case as reverse sorted array

Best Case Worst Case

Number of Elements
Running Time Running Time
(N)
(milliseconds) (milliseconds)
10
20
30
40
50
60
70
80
90
100

Government Engineering College, Rajkot