Design and analyze the Algorithms Assignment
Royal Commission for Jubail and Yanbu Jubail University College
Computer Science & Engineering Department
Cover Page
FX-ACA-002 Issue 0 Rev. 1 January 2, 2014
i Exam Type: Assign 1(LT) Semester: 391
Course Code CS 313 Course Title Design and analysis of Algorithms
Submission Date WEEK 7(Sunday)
PART I TO BE FILLED BY THE STUDENT
STUDENT’S
NAME
ID. No.
Course Section
TO BE FILLED BY THE CONCERNED DEPARTMENT
PART II 1st Marker 2nd Marker
Question
No.
Max
Marks
Actual
Marks Comments/Remarks
Actual
Marks Comments/Remarks
1 20
2 3
3 3
4 4
Total 30
Name: Dr. Ruchi Tuli Name:
Signature: Signature:
1. Calculate the time and space complexity(total amount of space required) of the following: (20 Marks)
a. Algorithm sum(a[ ], n) [4 Marks] sum =0
for(i=0 to n)
sum = sum + a[i]
return sum
b. Algorithm A1() [3 Marks] int i
for(i= 1 to n)
print(i)
c. Algorithm A3() [4 Marks]
int i, j
for(i= 1 to n)
for(j= 1 to n)
print(“hello”)
d. int sum(int x, int y, int z) { [2 Marks]
int w = x + y + z;
return w;
}
Instructions :-
Write the answers in your own handwriting. Do not type it
Late submissions will face penalties.
No email submission. Only hard copy submission
e. void Add(int a[ ], int b[ ], int c[ ], int n) { [4 Marks]
for (int i = 0; i < n; ++i) {
c[i] = a[i] + b[j]
}
}
f. void Multiply(int a[ ], int b[ ], int c[ ][ ], int n) { [3 Marks]
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
c[i] = a[i] + b[j];
}}}
2. Show that 3n3+2n2+7n+9 is O(n3) [3 Marks]
3. Show that n! is O(nn) [3 Marks]
4. Prove that n10 is O(2n ) [4 Marks]
