Algorithms Design a brute-force algorithm for computing the value of a polynomia

Question

Algorithms

Design a brute-force algorithm for computing the value of a polynomial p(x) = a_n x^n + a_n - 1 x^n - 1 + ... + a_1 x + a_0 at a given point x_0. Determine its worst-case efficiency class. Explain how exhaustive search can be applied to the sorting problem and determine the efficiency class of such an algorithm. Consider the problem of counting, in a given text, the number of strings that start with Y and end with Z. For example, for the string YAZYZ, there are three such substrings. Design a brute-force algorithm for this problem and determine its efficiency class. Given a graph G(V, E) with vertices V and edges E, provide pseudocode for an exhaustive-search algorithm that determines whether or not a Hamiltonian path, a path that uses every vertex in the graph exactly once, exists for G. Determine the complexity of such algorithm as well. Modify BFS or DFS to output vertices of connected components for an undirected graph G(V, E). Write pseudocode for the divide into three algorithm for the fake-coin problem. Your algorithm must handle properly all values of n. Write pseudocode for a nonrecursive implementation of quickselect. Generate all permutations of A, B, C, D using the Johnson-Trotter algorithm and the lexicographic-order algorithm.

Explanation / Answer

Algorithm BruteForcePolynomialEvaluation(A[0..n], x):
The algorithm computes the value of polynomial A at a given point x by the “highest-to-lowest term”

brute-force algorithm
Input: Array A[0..n] of the coefficients of a polynomial of degree n, stored from the lowest to the highest and a number x
Output: The value of the polynomial at the point x
p 0.0
for i n downto 0 do
power 1
for j 1 to i do
power power x
p p + A[i] power
return p

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

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