Sometimes, the constants that you ignore in Big O notation are important. For ex

Question

Sometimes, the constants that you ignore in Big O notation are important. For example, suppose you have two algorithms that can do the same job. The first requires 1,500 * N steps, and the other algorithm requires 30 * N2 step. For what values of N would you choose each algorithm? – 5 pts

The fast exponentiation algorithm described in chapter 2 is at a high-level. Specify and show the computation steps for the Big O of both the algorithms. Please comment your pseudocode well. – 25 pts

Write a low-level algorithm in the form of a pseudocode that one can use to implement.

Now change the pseudocode to implement modular fast exponentiation.

The least common multiple (LCM) of integers A and B is the smallest integer that A and B both divide into evenly. Specify and show the computation steps for the Big O of both the algorithms. Please comment your pseudocode well. – 25 pts

Write an efficient pseudocode to compute GCD of two numbers.

How can you use the GCD to computer LCM? Write the pseudocode to do that.

Write an algorithm in the form of a pseudocode to find the largest item in an unsorted singly linked list with cells containing integers. Please comment your pseudocode well. Specify and show the computation steps for the Big O of both the algorithms. – 20 pts

Write an algorithm in the form of a pseudocode to find the second smallest item in an unsorted singly linked list with cells containing integers. Please comment your pseudocode well. Specify and show the computation steps for the Big O of both the algorithms. – 20 pts

Is there any difference between the Big O running time of algorithms in question 4 and question 5? Which of the algorithms would run faster in real-time? Explain. – 5 pts

Explanation / Answer

(5)

Pseudocode of the LCM of integers A and B:

//prompt user to enter A and B values

A <-- read input from user;

B <-- read input from user;

//find the minimum number among A,B

minimum = (A>B)?A:B;

while(true)

{

//if minimum is divisible by both A and B

//then lcm is minimum

ifminimum %A==0 && minimum %B==0)

{

print as LCM of A,B is minimum

break;

}

//increment minimum till we get lcm

minimum ++;

}

Steps for the Big O of LCM:

In worst case of the LCM while loop will iterate n times from the program,

The time complexity of LCM will be in terms of O(n).

(6)

Pseudocode of the GCD of integers A and B:

A <-- read input from user;

B <-- read input from user;

//send the A,B values to gcd function

gcd(A,B);

//Implementation of gcd method

int gcd(A,B)

{

if(A==B)

return A;

if(A>B)

return gcd(A-B,B);

//B is greater than A

return gcd(A,B-A);

}

(7)

//calculate LCM by GCD

//LCM is equals to A*B/gcd(A,B)

LCM=A*B/gcd (A, B);

Efficiency of GCD algorithm:

GCD will also take same as O(n) as LCM.

Thus the efficiency of GCD algorithm is O(n)

(8)

Pseudocode to find largest item in the singly linked list

//method to find largest element take head/root as parameter

findLargestElement(Node *root)

{

*temp=root;

max=temp->data;

temp=temp->next;

//iterate till items are completed

while(temp!=NULL)

{

//current element is larger than maximum

//maximum will be current element

if(temp->data > maximum)

maximum =temp->data;

}

print maximum;

}

To find largest element, we need to traversal all the elements in the linked list.

Consider n is efficiency time complexity will be O(n).

(9)

Pseudocode to find second smallest item in linked list

*root; //root or head

*temp=root; //assign root to temporary pointer

//smallest item

first=second=temp->data;

temp=temp->next;

while(temp!=NULL)

{

//if current element is smaller than first element

//then update first as well as second also

if(temp->data<first)

{

second=first;

first=temp->data;

}

//if current element is between first and second

//update second element

else if(temp->data<second && temp->data !=first)

second=temp->data

//increment

temp=temp->next;

}

//Display second item as second smallest item

print second

Efficiency

To find to second smallest element, traversal all the elements in the linked list, then the efficiency is O(n).

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.