IGNOU BCS-042-Introduction to Algorithm Design, Latest Solved Assignment (July 2023 - January 2024 )
Q4. Write a pseudocode of evaluating polynomial expression using Horner’s rule and perform complexity analysis (step by step). Apply it to evaluation the polynomial expression:
P(x) = 3x^6+4x^5+2x^4+2x^3+8x+9
Sol) Evaluating a polynomial expression using Horner’s rule:
def horner(coeffs, x):
Evaluates a polynomial expression using Horner’s rule.
Args:
coeffs: A list of coefficients of the polynomial.
x: The value to evaluate the polynomial at.
Returns:
The value of the polynomial at x.
y = coeffs[0]
for i in range(1, len(coeffs)):
y = y * x + coeffs[i]
return y
The time complexity of Horner’s rule is O(n), where n is the degree of the polynomial. This is because the algorithm only needs to perform multiplications and n additions.
To apply Horner’s rule to the polynomial expression P(x) = 3x^6+4x^5+2x^4+2x^3+8x+9, we would first need to convert the polynomial into a list of coefficients. This can be done by expanding the polynomial andcollecting the coefficients.
The resulting list of coefficients would be [3, 0, 4, 0, 2, 8, 9].
- Initialize y to the first coefficient, which is 3.
- Multiply y by x and add the second coefficient, which is 0.
- Multiply y by x and add the third coefficient, which is 4.
- Continue steps 2 and 3 until all of the coefficients have been processed.
- The final value of y will be the value of the polynomial P(x) at x.
In this case, the value of P(x) when x = 2 is 209. This can be verified by expanding the polynomial and evaluating it at x = 2.
Q5. Write pseudocode for left to right binary exponentiation evaluation. Applythe algorithm for evaluating a280 and show a step by step result.
Sol) pseudocode for left-to-right binary exponentiation:
function binaryExponentiation(base, exponent):
result = 1
binaryExponent = convertToBinary(exponent)
for i = 0 to length(binaryExponent) – 1:
result = result * result
if binaryExponent[i] == 1:
result = result * base
return result
base = a
exponent = 280
binaryExponent = convertToBinary(280) Binary representation: 100011000
result = 1
Iteration 1: i = 0, binaryExponent[0] = 0
result = result * result = 1 * 1 = 1
Iteration 2: i = 1, binaryExponent[1] = 0
result = result * result = 1 * 1 = 1
Iteration 3: i = 2, binaryExponent[2] = 1
result = result * result = 1 * 1 = 1
result = result * base = 1 * a = a
Iteration 4: i = 3, binaryExponent[3] = 1
result = result * result = a * a = a^2
result = result * base = a^2 * a = a^3
Iteration 5: i = 4, binaryExponent[4] = 0
result = result * result = a^3 * a^3 = a^6
Iteration 6: i = 5, binaryExponent[5] = 0
result = result * result = a^6 * a^6 = a^12
Iteration 7: i = 6, binaryExponent[6] = 0
result = result * result = a^12 * a^12 = a^24
Iteration 8: i = 7, binaryExponent[7] = 1
result = result * result = a^24 * a^24 = a^48
result = result * base = a^48 * a = a^49
Final result: a^280 = a^49
Assignment Submission Last Date
The IGNOU open learning format requires students to submit study Assignments. Here is the final end date of the submission of this particular assignment according to the university calendar.
30th April (if Enrolled in the June Exams)
31st October (if Enrolled in the December Exams)