What is the primary motivation for using a sparse representation (a list of non-zero terms) for polynomials instead of a dense one (a list of all coefficients)?
Explanation
Choosing the right data representation is crucial for performance. For polynomials that are 'sparse' (having few non-zero terms over a large range of powers), a representation that only stores the non-zero terms is far more space- and time-efficient than one that stores all coefficients, including the zeros.
Other questions
What is the primary purpose of data abstraction in program design, as introduced in the chapter?
In the rational-number arithmetic system example, what set of functions forms the abstraction barrier between the operations like `add_rat` and the underlying representation of rational numbers as pairs?
What is the key characteristic of an operation that possesses the 'closure property'?
Given the list `const squares = list(1, 4, 9, 16, 25);`, what is the result of evaluating `list_ref(squares, 3)`?
What is the fundamental difference between the `append` function and the `append_mutator` function described in Exercise 3.12?
What does the higher-order function `map` do when applied to a function and a list?
In the functional representation of pairs where `function pair(x, y) { return m => m(x, y); }`, what is the correct definition for `tail(z)`?
According to the symbolic differentiation example, how is the algebraic expression `ax + b` represented using prefix notation in list structure?
When representing a set as an ordered list of numbers, what is the order of growth in the number of steps for the `intersection_set` operation for two sets of size n?
In a Huffman encoding tree, where is the information about the relative frequency of symbols (the weights) used?
What is the purpose of using type tags in a data system with multiple representations, such as the complex number example?
What is a major weakness of implementing generic operations using explicit dispatch-on-type (as in Section 2.4.2) that data-directed programming aims to solve?
What is the process of viewing an object of one type as an equivalent object of another type called in the context of generic arithmetic?
Consider the representation of a set as a balanced binary tree. What is the order of growth for checking if an element is in a set of size n?
In the `count_leaves` function for a tree, what is the base case for a leaf node (an object that is not null and not a pair)?
Given the list structure created by `const x = list(list(1, 2), list(3, 4));`, what is the result of `length(x)`?
What is meant by a 'headed list' in the context of the table implementation in Section 3.3.3?
Why is the first version of the rational-number implementation in Section 2.1.1, which does not reduce fractions, considered incomplete or imperfect?
In the signal-flow model for sequence processing, what is the role of the `filter` operation?
What is the result of evaluating `equal(list("a", "b"), list("a", "b"))` according to the definition in Exercise 2.54?
When Alyssa P. Hacker represents complex numbers in polar form, which function is straightforward to implement?
In the message-passing implementation of `make_from_real_imag(x, y)`, what does the function actually return?
According to Exercise 2.1, if `make_rat` is modified to normalize the sign of a rational number, what should `make_rat(-2, -3)` produce internally before creating the pair?
What does the function `flatmap` do, as defined in the section on nested mappings?
In the eight-queens puzzle implementation, what does the function `queen_cols(k)` aim to return?
What is the result of the expression `const z2 = pair(list("a", "b"), list("a", "b"));` followed by `head(z2) === tail(z2)`?
In the picture language from Section 2.2.4, what is a `painter` represented as?
What is stratified design, as described in the context of the picture language?
What is the value of the expression `member("red", list("red", "shoes", "blue", "socks"))`?
In the context of the generic arithmetic system in Section 2.5, what is a 'tower of types'?
When defining the `mul_poly` function for multiplying two polynomials, how is the coefficient of a new term calculated?
In the `div_rat` function for rational numbers, the returned rational number is `make_rat(numer(x) * denom(y), denom(x) * numer(y))`. What mathematical operation does this correspond to?
What is the purpose of the `is_pair` predicate in the `count_leaves` function?
According to the definition of a queue in Section 3.3.2, which operation removes an item from the sequence?
Why is the simple list representation for a queue inefficient for the `insert_queue` operation?
In the `permutations` function from Section 2.2.3, what is the base case for the recursion?
If `deriv` is called with the expression `list("*", "x", "y")` and the variable `"x"`, what is the unsimplified result?
What does the `put(op, type, item)` function do in the data-directed programming framework?
In the extended exercise on interval arithmetic, why does Lem E. Tweakit's program give different answers for the two algebraically equivalent formulas for parallel resistance?
Consider the representation of points and line segments in Exercise 2.2. A point is a pair of numbers (x, y) and a segment is a pair of points. How would you select the y-coordinate of the end point of a segment `s`?
What is the key idea behind the `accumulate` function introduced in Exercise 1.32 and used in Section 2.2.3?
In the representation of a queue as a pair of pointers (front_ptr, rear_ptr), what is the state of an empty queue created by `make_queue()`?
If you evaluate `horner_eval(2, list(1, 3, 0, 5, 0, 1))`, which polynomial is being evaluated?
The function `square_of_four` in Section 2.2.4 abstracts a pattern of painter combination. What does it take as arguments?
In the `accumulate_n` function from Exercise 2.36, what does the first `??` in `pair(accumulate(op, init, ??), ...)` represent?
What is the result of `dot_product(list(1, 2, 3), list(4, 5, 6))` as defined in Exercise 2.37?
According to footnote 2 on page 74, what is a potential disadvantage of defining `make_rat` as `const make_rat = pair;`?
What does Euclid's Algorithm, as presented for polynomial GCD in Exercise 2.94, rely on?
In the two-dimensional table implementation, how is a subtable identified when performing a lookup?