5) A polynomial \'p\' may be represented as a list of integers in an array as fo
ID: 3919410 • Letter: 5
Question
5) A polynomial 'p' may be represented as a list of integers in an array as follows:
for every term in 'p', there is one entry in the array, consisting of the term's coefficient stored at the index that corresponds with its degree. The entries are ordered according to values of degrees; zero-coefficient terms are stored as 0.
a)Draw the array and show how the following polynomial is stored in the array. 3x6 -4x4 +x3 -2x2+6x1 –2x0 (x0 ==1)
b) Propose an algorithm that adds two polynomials and produce the resulting polynomial based on the above array representation given above.
( Here is a second polynomial 2x5 + 4x3 + 5x2 - 2x1 )
6) Given a linked list, one can reverse the list using a Stack. Assuming that Java API LinkedList and Stack are available for you, write Java code(NOT pseudo-code) to accomplish this task. You must show the construction of input list using several integers. The output of your solution should be a LinkedList.
4) Given a singly linked list with only the head reference, one can reverse the list using a Stack. Provide a detail algorithm to accomplish this reversal. The final outcome is a linked list.
6) Given a linked list, one can reverse the list using a Stack. Assuming that Java API LinkedList and Stack are available for you, write Java code(NOT pseudo-code) to accomplish this task. You must show the construction of input list using several integers. The output of your solution should be a LinkedList.
Explanation / Answer
5) a)
3x6 -4x4 +x3 -2x2+6x1 –2x0 (x0 ==1)
The array will look like as follows:
|-2 | 6 | -2 | 1 |-4| 3 |
0 1 2 3 4 5
The polnomial is stored in revese order.The indexes are shown just below the coefficients
b) Algorithm to add
1. We will allocate an array of length n to store our result.Here n is the degree
of the polynomial whose degree is higher.
2. Now we can traverse the higher degree polynomial from 0 to n. We can keep on adding
the corresponding elements of the two arrays provided we the corresponding elements
in two arrays.It is possible that lower degree polynomia array will be finished in
between as we traverse.
3x6 -4x4 +x3 -2x2+6x1 –2x0 (x0 ==1)
|-2 | 6 | -2 | 1 |-4| 3 | ----first polynomial
0 1 2 3 4 5
2x5 + 4x3 + 5x2 - 2x1 ---- second polynomial
|0 | -2 | 5 | 4 | 0 | 2 | ----second polynomial
0 1 2 3 4 5
By adding we can get:
|-2 | 4 | 3 | 5 | -4 | 5 | ----Result polynomial
0 1 2 3 4 5
4. Algorith for reverse using stack
1. We will keep on traversing the linked list from head onwards pushing the elements
in the stack.
2. Now we can create a new linked list by popping elements out of the stack and adding
to the list. The resultant list will be the reverse of the original list. As we
know stack is Last in first out so top of the stack will caontain the last element
at the top and next element will be second last element and so and so forth. So
when we are popping out the stack we are getting the elements in reverse order and
thats how the new list which is created is the reverse of the original list
6. The code is as follows:
LinkedList<Integer> list1 = new LinkedList<Integer>();
LinkedList<Integer> list2 = new LinkedList<Integer>();
Stack<Integer> stack = new Stack<Integer>();
list1.add(1);
list1.add(2);
list1.add(3);
System.out.println("The given list:");
for (int i = 0; i<list1.size(); i++){
System.out.println(list1.get(i));
}
for (int i = 0; i<list1.size(); i++){
int b = list1.get(i);
stack.push(b);
}
while(!stack.empty()){
int c = stack.pop();
list2.add(c);
}
System.out.println("The reversed list:");
for (int i = 0; i<list2.size(); i++){
System.out.println(list2.get(i));
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.