Description
1. The purpose of the course is to learn how to analyse the complexity of the
algorithm.
2. You are supposed to do this assignment on your own. While you may discuss
the problem with other students, you are not allowed to copy any part of the
code from other students or to copy from any other source. Any form of
plagiarism will not be tolerated. If there is substantial overlap between the
codes submitted by two students, both will get reduction in the course grade.
3. The assignment should be shown to lab instructor in the lab session and
must be submitted on LMS by given date.
It should also carry the following statement:
“I have done this assignment on my own. I have not copied any code from
another student or any online source. I understand if my code is found
similar to somebody else’s code, my case can be sent to the Disciplinary
committee of the institute for appropriate action.”
Lab Assignment 3
Q1. In this assignment, students are required to randomly generated 100 numbers and write
it down in a output file “Lab3_input.txt”. Next, students are required to read the input
file “Lab3_input.txt” and sort the numbers using: a) Insertion sort (b) Selection sort (c)
Bubble sort
With each algorithm, students are required to find the time complexity (in terms of
number of iterations) of the algorithm to sort the data.
For example, suppose the randomly generated file has following numbers:
Expected output: A output file by name “Lab3_output.txt”:
12
34
5
2
56
78
32
5
1
45
Bennett University Greater Noida
Department of CSE
Subject Lab: Algorithms & Complexity Lab Duration: 10:40-12:35
Lab Code: ECSE202L Max Marks: 10
Insertion sort
1
2
5
5
12
32
34
45
56
78
Selection sort:
1
2
5
5
12
32
34
45
56
78
Bubble sort:
1
2
5
5
12
32
34
45
56
78
Case/Time complexity Bubble Selection Insertion
Best Case 32 40 40
Worst case 32 23 65
Average Case
Bennett University Greater Noida
Department of CSE
Subject Lab: Algorithms & Complexity Lab Duration: 10:40-12:35
Lab Code: ECSE202L Max Marks: 10
Q2. In this question, you will get the file from your lab instructor which will be taken as
input to read the data. Based on the given input file, you are supposed to sort the data
by applying
(a) Insertion sort (b) Selection sort (c) Bubble sort
Again you have to find the expected running time of all the algorithms to sort the data
in:
(i) Best case (ii) Average case (iii) Worst case.
For example, the given file will hold the data in this form:
Expected Output:
S
W
A
T
D
Z
Insertion sort
A
D
S
T
W
Z
Selection sort:
A
D
S
T
W
Z
Bubble sort:
A
D
S
T
W
Z
Case/Time complexity Bubble Selection Insertion
Best Case 5 6 6
Worst case 6 6 5
Average Case 2 4 3