Department of Computer Science CSC-221:Data structures & Algorithm

Bahria University Karachi Campus Semester 03 (Fall 2022)

ASSIGNMENT 01
Marks: 2.5
CLO1, C2

NAME: _Raamish Ahmed

CLASS: BS IT 3 A
REG. NO. 79056

Read Carefully:
• The deadline for this assignment is before 29/10/2022.

WARNING: This is an individual assignment; you must solve it by yourself.

Any form of plagiarism will result in receiving zero in the assignment.

WARNING: Late submission will not be accepted. Any assignment submitted after the cutoff
time will receive zero.

• Submit SOFTCOPY on LMS in pdf format.

• Answer should be hand written. If there is any programming related tasks then attach the
print of code properly along with the screenshots of output.
 Department of Computer Science CSC-221:Data structures & Algorithm

Bahria University Karachi Campus Semester 03 (Fall 2022)

Question 1: (CLO1)

1. Compare all sorting algorithms that you have studied in class.

2. If we have a telephone directory with 10 million records, Explain which algorithm

works best in your opinion with justification. (If your suggestion is other than studied
algorithms then discuss the working of that algorithm as well)

3. Consider the given list and Infer which searching algorithm you would prefer for given
data. Show how many comparisons would be made to search “Scheduling”.

Computer Fan Network Program Resourc Scheduling Unix Wire

e

4. Assume that we have a list of votes about candidates in university election. Outline an
algorithm for determining who wins the election and show the results

[Implementation required]

umar irma sara Umar huzaifa umar Irma sara sara Irma
irma sara irma Madiha wajahat irma Sara umar maria irma

1. Compare all sorting algorithms that you have studied in class.

 Department of Computer Science CSC-221:Data structures & Algorithm

Bahria University Karachi Campus Semester 03 (Fall 2022)

SORTING TIME COMPLEXITY

ALGORITHM
BEST | AVERAGE WORST
SPACE

BUBBLE SORT Ω(n) O(N^2) O(1)

INSERTION SORT Ω(n^2) O(N^2) O(1)

SELECTION SORT Ω(n) O(N^2) O(1)

QUICK SORT Ω(N LOG N) O(N log N) 0(n)

MERGE SORT Ω(N LOG N) O(N log N) O(n)

2. If we have a telephone directory with 10 million records, explain which algorithm works
best in your opinion with justification. (If your suggestion is other than studied
algorithms then discuss the working of that algorithm as well)

ANS:

Heap Sort works best. Because Heapsort is a comparison-based sorting

technique based on Binary Heap data structure. It is similar to

the Selection Sort where we first find the minimum element and place the
minimum element at the beginning. Repeat the same process for the
remaining elements.
like Merage sort Heapsort doesn’t requires an additional space of O(n). Even if the
array is sorted, the merge sort goes through the entire process ….
 Department of Computer Science CSC-221:Data structures & Algorithm

Bahria University Karachi Campus Semester 03 (Fall 2022)

3. Consider the given list and Infer which searching algorithm you would prefer for given
data. Show how many comparisons would be made to search “Scheduling”.

Computer Fan Network Program Resourc Scheduling Unix Wire

e

ANS:
Search : Scheduling
Comparison:1
s Computer Fan Network Program Resourc Scheduling Unix Wire
e

LEFT MID
RIGHT

Comparisons : 2 Resourc Scheduling Unix Wire

e

MID

LEFT RIGHT

Scheduling FOUND!.
 Department of Computer Science CSC-221:Data structures & Algorithm

Bahria University Karachi Campus Semester 03 (Fall 2022)

4 Assume that we have a list of votes about candidates in university election. Outline an
algorithm for determining who wins the election and show the results

[Implementation required]

umar irma sara Umar huzaifa umar Irma sara sara Irma
irma sara irma Madiha wajahat irma Sara umar maria irma

SOURCE CODE
#include “iostream”
#include <string>

using namespace std;

int main(){
int a= 0;
int b= 0;
int c= 0;
int d= 0;
int e= 0;
int f= 0;

string arr[20] = {"umar" ,"irma","sara", "Umar"," huzaifa", "umar","Irma",

"sara" ,"sara" ,"Irma",
"irma" , "sara", "irma", "Madiha", "wajahat", "irma", "Sara", "umar","maria"
, "irma"
};
for(int i=0 ; i<=19;i++)
{
if(arr[i]=="umar"){
Department of Computer Science CSC-221:Data structures & Algorithm

Bahria University Karachi Campus Semester 03 (Fall 2022)

a = a+1;
}
if(arr[i]== "imra"){
b= b+1 ;
}
else if(arr[i]== "sara"){
c=c +1 ;
}
else if(arr[i]== "huzaifa"){
d++ ;
}
else if(arr[i]== "Madiha"){
e++ ;
}
else if(arr[i]== "wajahat"){
f++ ;
}
}

if (a>b &&a>c && a>d && a>e && a>f){

cout <<"TOTAL VOTES ARE "<< a <<" AND UMER WINS ";

}
if (b>a &&b>c && b>d && b>e && b>f){
cout <<"TOTAL VOTES ARE "<< b <<" AND IRMA WINS";

}
if (c>a &&c>b && c>d && c>e && c>f){
cout <<" TOTAL VOTES ARE "<<c <<" AND SARA WINS ";
 Department of Computer Science CSC-221:Data structures & Algorithm

Bahria University Karachi Campus Semester 03 (Fall 2022)

}
if (a>b &&a>c && a>d && a>e && a>f){
cout <<a;
cout<<"OTHERS WINS"<<endl;

return 0;
}

Output: