CS502 Assignment 1 Solution 2021 – Download solution File. CS502 Assignment 1 Solution Spring 2021.docx
Assignment No. 01
SEMESTER Spring 2021
CS502- Fundamentals of Algorithms
Question No 01: (Marks: 10)
Suppose that one of the largest commercial bank branch in UAE has recently experienced a significant distress due to covid 19. A huge No. of account holders withdraws the payment from the bank. Now manager want to check the total number of accounts those have less than 1000$.
You are required perform the following task:
A. Write only Pseudocode to check the total number of accounts, who have less than 1000$ using array list.
B. After writing Pseudocode calculate the worst-case time complexity T(n).
CS502 Assignment 1 Solution 2021 – Question 1
you may write this pseudo code in any format. As we know that pseudo code is not any format specific when we talk about cs502 assignment 1 2021 solution.
Pseudo Code
arraylist ()
for i=1 to no of accounts
if amount < 1000$
arraylist (account_no)
return false
CS502 Assignment 1 Solution 2021 Question NO 1 (Part b)
Solution
Time Complexity
Cost | Time |
C1 | 1 |
C2 | n+1 |
C3 | N |
C4 | n/2 |
C5 | 1 |
Grand Total = c1+c2(n+1)+c3(n)+c4(n/2)+c5
= c1+c2n+c2+c3n+c4n/2+c5
= n(c2+c3+c4(1/2))+c1+c2+c5
= remove lowest order terms & constant
= O(n)
Question No 02: (Marks: 10)
A prime number is a number that can only be divided by itself and 1. Using the following code, we can check whether the number is prime or not. Your task is to find the time complexity of the following code with respect to worst case.
int arr[5], j, x , y, z;
for(x=0; x<5; x++)
{
cout”Enter the no.”endl;
cin>>arr[x];
}
for(x=0;x<5;x++)
{
y=0;
for(j=2; j<arr[x];j++)
{
z=arr[x]%j;
if(z==0)
{
y=1;
break;
}
}
if(y==0)
coutarr[x]endl;
}
}
Question NO 2 Solution
Cost | Time |
C1 | 1 |
C2 | n+1 |
C3 | n |
C4 | n |
C5 | n+1 |
C6 | n |
C7 | n(n+1)/2 |
C8 | n2/2 |
C9 | n2/2 |
C10 | n |
C11 | n |
C12 | n |
C13 | n/2 |
Grand Total =
c1+c2n+c2+c3n+c4n+c5n+c5+c6n+c7n2/2+c7n/2+c8n2/2+c9n2/2+c10n+c11n+c12n+c13n/2 O(n2)