Who can solve these? I keep getting WRONG answers. God Bless you. A) Write a pse
ID: 3587944 • Letter: W
Question
Who can solve these? I keep getting WRONG answers. God Bless you.
A) Write a pseudo-code description for a method of finding the smallest and largest numbers in an array of integers. Compare your pseudo-code to a Java method that would do the same thing.
(B) Write a short Java program that outputs all of the possible strings formed using each of the characters ‘c’, ‘a’, ‘t’, ‘d’, ‘o’, and ‘g’ exactly once.
(C) Draw the recursion trace for the execution of the method PuzzleSolve(3, S, U) (Code Fragment 5.11), where S is empty and U = {a,b,c,d}.
(D) Describe a fast recursive algorithm for reversing a singly linked list L, so that the ordering of the nodes becomes opposite to what it was before.
(E) Describe a recursive algorithm for solving the Towers of Hanoi puzzle for an arbitrary n (see Creativity Exercise C-5.16 for more details).
(F) Give a pseudo-code description for the O(n)-time algorithm for computing the power function, p(x,n). Draw the recursion trace of this algorithm to compute p(2,5).
(G) Given a set A = {a1, a2, …, an} of n integers, use pseudo-code to describe an efficient method of computing each of the partial sums sk = a1 + a2 + …+ ak for k = 1,2,…,n. What is the running time for this method?
Explanation / Answer
A. INTODUCTION - Since we have to smallest and largest numbers in array of integers, we can simply do sorting of array(either ascending /descending order) using any sorting algorithm and return first and last elsement of that array.
Pseudo-code
Step1- Take array of intergers as an input.
Step2-Do sorting using any sorting algorithm(Here we have selected Selection Sort in ascending order).
Step2- return first and last element.
Java Method-/*Function to sort array using insertion sort and finding smallest and largest numbers*/
void find_smallest_largest(int arr[])
{
int n = arr.length;
for (int i=1; i<n; ++i)
{
int key = arr[i];
int j = i-1;
/* Move elements of arr[0..i-1], that are
greater than key, to one position ahead
of their current position */
while (j>=0 && arr[j] > key)
{
arr[j+1] = arr[j];
j = j-1;
}
arr[j+1] = key;
}
/* Once this loop will end array numbers will be sorted in ascending order.
System.out.println("smallest Number is "+ arr[0]);
System.out.println("larget Number is "+ arr[arr.length-1]);
}
-------------------------------------------------------------------------------------------------------------------------
B.
class Permutation
{
public static void main(String args[])
{
char[] str = {'c','a','r','b','o','n'};
int count =0;
for(int i=0;i <str.length ;i++){
for(int j=0; j<str.length;j++){
for(int k = 0; k< str.length;k++){
for(int l=0;l<str.length;l++) {
for(int m=0;m<str.length;m++) {
for(int n=0;n<str.length;n++) {
if(i!=j && i!=k && i!=l && i!=m && i!=n && j!=k && j!=l && j!=m && j!=n && k!=l && k!=m && k!=n && l!=m && l!=n && m!=n ){
System.out.println(""+ str[i] + str[j]+str[k]+str[l]+str[m]+str[n]);
count +=1;
}
}
}
}
}
}
}
System.out.println(count);
}
}
-----------------------------------------------------------------------------------------------------------------------------
C. For this question we need some more information as we don't know what is mentioned in Code Fragment 5.11.
--------------------------------------------------------------
D. 1) Divide the list in two parts - first node and rest of the linked list.
2) Call reverse for the rest of the linked list.
3) Link rest to first.
4) Fix head pointer
Java Method-
// A simple and tail recursive function to reverse a linked list. prev is passed as NULL initially.
Node reverseList(Node curr, Node prev) {
/* If last node mark it head*/
if (curr.next == null) {
head = curr;
/* Update next to prev node */
curr.next = prev;
return null;
}
/* Save curr->next node for recursive call */
Node next1 = curr.next;
/* and update next ..*/
curr.next = prev;
reverseList(next1, curr);
return head;
}
-------------------------------------------------------------------------------------------
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.