Write a low-level algorithm in the form of a pseudocode that one can use to impl
ID: 3871212 • Letter: W
Question
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
Explanation / Answer
/*
Pseudocode to compute LCM of two integers
*/
//prompt user to enter A and B values
A <-- get it from user;
B <-- get it from user;
//find the min number among A,B
min = (A>B)?A:B;
//always true
//terminates when we find lcm
while(true)
{
//if min is divisible by both A and B
//then lcm is min
//break it to terminate the while loop
if(min%A==0 && min%B==0)
{
print as LCM of A,B is min
break;
}
//increment min, till we get lcm
min++;
}
/*
In worst case the while loop will iterate n times,
therefore, the time complexity of LCM will be O(n)
*/
/*
Pseudocode to compute GCD of two integers
*/
//prompt user to enter A and B values
A <-- get it from user;
B <-- get it from user;
//pass A,B values to gcd function
gcd(A,B);//calling gcd method
//defination of gcd method
int gcd(A,B)
{
//base condition
//if both A and B are same, return gcd as A or B
if(A==B)
return A;
//if A is greater than B, then recursion as
//A-B as A and B as B only
if(A>B)
return gcd(A-B,B);
//if B is greater than A, then recursion as
//A as A and B as B-A
return gcd(A,B-A);
}
//finding LCM by GCD
//LCM is equals to A*B/gcd(A,B)
LCM=A*B/gcd(A,B);
/*
GCD wil also take O(n) as LCM
*/
/*
Pseudocode to find largest item in the singly linked list
*/
//method to find largest element
//this method will take head/root as parameter
findLargest(Node *root)
{
//head will pointing by temporary pointer
*temp=root;
//first item in the linked list will be max
max=temp->data;
//increment to next item
temp=temp->next;
//iterate till items are over
while(temp!=NULL)
{
//current item is larger than max
//max will be current item
if(temp->data > max)
max=temp->data;
}
//print max element
print max;
}
/*
To find largest element, we need to traversal all the
items in the linked list. lets say n.
therefore, time complexity will be O(n)
*/
/*
Pseudocode to find second smallest item in linked list
*/
*root;//root or head
*temp=root;//assign root to temporary pointer
//check for base condition
base condition=atleast 2 items should be there
//assign first item in the linked list as first and second
//smallest item
first=second=temp->data;
//increment
temp=temp->next;
//iterate till the last item
while(temp!=NULL)
{
//if current item is smallar than first item
//update first as well as second also
if(temp->data<first)
{
second=first;
first=temp->data;
}
//if current item is between first ans second
//update second
else if(temp->data<second && temp->data !=first)
second=temp->data
//increment to next item
temp=temp->next;
}
//print second item as second smallest item
print second
/*
to find to second smallest item, we need traversal all the item,
so, it will O(n)
*/
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.