TRB PG Assistant - Dynamic programming, approximation in function space, successive approximations Online Test (MCQ Quiz)

1. What is the fundamental principle behind dynamic programming?

A) Divide and conquer B) Breaking down a problem into overlapping subproblems and solving each subproblem only once C) Greedy approach to find the optimal solution D) Randomized search for the best solution

2. In dynamic programming, what is a 'stage' typically associated with?

A) A single iteration of the algorithm B) A decision-making point or a step in the problem's progression C) The final solution to the problem D) The memory used by the algorithm

3. What does the 'principle of optimality' state in the context of dynamic programming?

A) An optimal policy has the property that whatever the initial state and initial decision are, the remaining decisions must constitute an optimal policy with respect to the state resulting from the first decision. B) The optimal solution is always found by making the locally best choice at each step. C) All subproblems must have unique solutions. D) The problem must be decomposable into independent subproblems.

4. Which type of problems are most suitable for dynamic programming?

A) Problems with non-overlapping subproblems B) Problems exhibiting optimal substructure and overlapping subproblems C) Problems solvable with a single greedy choice D) Problems that require brute-force enumeration of all possibilities

5. What is the primary difference between dynamic programming and recursion with memoization?

A) Dynamic programming solves subproblems in a top-down manner, while memoization is bottom-up. B) Memoization stores results of subproblems to avoid recomputation, while dynamic programming does not. C) Dynamic programming typically solves subproblems in a bottom-up manner, while recursion with memoization is top-down. D) There is no fundamental difference; they are essentially the same technique.

6. Consider the Fibonacci sequence. How can dynamic programming be used to compute F(n)?

A) By computing F(n-1) and F(n-2) recursively without storing intermediate results. B) By iteratively computing F(0), F(1), F(2), ..., F(n), storing each result. C) By using a divide and conquer approach that splits the problem into many unrelated subproblems. D) By approximating the value of F(n) using a function.

7. What is a 'state' in a dynamic programming problem?

A) The final answer to the problem. B) A unique configuration or representation of the subproblem being solved. C) A decision variable. D) The objective function.

8. In the context of dynamic programming, what is 'memoization'?

A) A technique to break down problems into smaller, independent parts. B) Storing the results of expensive function calls and returning the cached result when the same inputs occur again. C) The process of finding the minimum or maximum value of a function. D) A method for approximating solutions in continuous spaces.

9. Which of the following is NOT a characteristic of problems typically solved by dynamic programming?

A) Optimal substructure B) Overlapping subproblems C) Greedy choice property D) Sequential decision making

10. What is the 'curse of dimensionality' in dynamic programming?

A) The difficulty in finding the optimal substructure. B) The exponential increase in the number of states as the number of variables or dimensions increases, making computation infeasible. C) The requirement for a large amount of memory to store the results. D) The challenge of defining the state transition.

11. What does 'approximation in function space' generally refer to?

A) Finding the exact solution to a problem involving functions. B) Finding a function that is close to an optimal function or satisfies certain properties, often when exact solutions are difficult or impossible. C) Discretizing a continuous function into a finite set of points. D) Using dynamic programming to solve problems related to function optimization.

12. In approximation theory, what is a 'norm' used for?

A) To define the dimensionality of a function space. B) To measure the 'distance' or 'error' between two functions. C) To determine the convergence rate of an approximation method. D) To represent a function as a series of simpler functions.

13. Which of the following is a common goal in approximation in function space?

A) To find a function that exactly matches a given set of data points. B) To find a simpler function that closely approximates a more complex function or data. C) To prove the existence of a solution. D) To determine the uniqueness of a solution.

14. What is the Weierstrass Approximation Theorem fundamentally about?

A) That any continuous function on a closed interval can be approximated arbitrarily well by a polynomial. B) That dynamic programming can solve any continuous optimization problem. C) That the shortest path between two points is a straight line. D) That approximation methods always converge to the exact solution.

15. What is the 'best approximation' of a function f in a function space with respect to a given norm?

A) Any function that is close to f. B) A function g such that the norm of the difference ||f - g|| is minimized. C) A function that interpolates f at specific points. D) A function that satisfies a differential equation related to f.

16. What is 'interpolation' in the context of function approximation?

A) Finding a function that passes through a given set of points. B) Finding a function that minimizes the error over an entire interval. C) Simplifying a complex function. D) Finding the derivative of a function.

17. What is 'least squares approximation'?

A) Finding a function that minimizes the maximum error. B) Finding a function that minimizes the sum of the squares of the errors at given points. C) Finding a function that is exactly equal to the data at all points. D) Finding a function that minimizes the average error.

18. What is the role of basis functions in function approximation?

A) They define the space of functions from which the approximation is chosen. B) They are the exact solutions to the problem. C) They represent the errors in the approximation. D) They are used to define the norm of the function space.

19. Which of the following is a common type of basis function used in approximation?

A) Step functions B) Trigonometric polynomials C) Rational functions D) All of the above

20. What is 'function space' in mathematics?

A) The set of all possible input values for a function. B) The set of all functions that map from one set to another. C) The graphical representation of a function. D) The space where derivatives are calculated.

21. What is 'successive approximations'?

A) A method where a problem is solved by repeatedly applying a process, with each step bringing the solution closer to the true value. B) Solving multiple independent subproblems simultaneously. C) Finding the exact solution in a single step. D) Using a greedy strategy to find the best immediate result.

22. In the context of solving equations, what does the method of successive approximations (or fixed-point iteration) involve?

A) Guessing the solution and checking if it satisfies the equation. B) Rearranging the equation into the form x = g(x) and iterating x_{n+1} = g(x_n). C) Using calculus to find the roots of the equation. D) Discretizing the domain of the equation.

23. For the method of successive approximations to converge to a unique fixed point, what condition must the function g(x) typically satisfy?

A) g(x) must be a constant function. B) g(x) must be monotonically increasing. C) g(x) must be a contraction mapping (i.e., |g'(x)| < 1 in the relevant interval). D) g(x) must be differentiable everywhere.

24. Which type of problem is often solved using successive approximations?

A) Finding the maximum value of a convex function. B) Solving non-linear equations or systems of equations. C) Calculating definite integrals. D) Determining the determinant of a matrix.

25. What is an 'initial guess' in the method of successive approximations?

A) The exact solution to the problem. B) The first approximation (x_0) used to start the iterative process. C) The function g(x) used in the iteration. D) The convergence criterion.

26. What is a common stopping criterion for the method of successive approximations?

A) When the number of iterations reaches a predefined limit. B) When the difference between successive approximations (|x_{n+1} - x_n|) is smaller than a specified tolerance. C) When the function value g(x_n) equals x_n. D) All of the above.

27. How does successive approximations relate to dynamic programming?

A) They are fundamentally different techniques with no overlap. B) Dynamic programming can be viewed as a form of successive approximation where optimal policies are iteratively improved. C) Successive approximations are used to find the initial state in dynamic programming. D) Dynamic programming provides the function g(x) for successive approximations.

28. Consider the Bellman equation in dynamic programming. How are successive approximations used to solve it?

A) The Bellman equation itself is solved directly without iteration. B) The value function is iteratively updated using the Bellman equation until convergence. C) Successive approximations are used to define the state space. D) The optimal policy is approximated using a single step.

29. What is the primary advantage of using approximation methods in function space?

A) They always yield exact solutions. B) They can handle problems that are computationally intractable or have no exact analytical solution. C) They require less memory than exact methods. D) They guarantee faster convergence than iterative exact methods.

30. What does it mean for an approximation to be 'arbitrarily well'?

A) The approximation is good enough for most practical purposes. B) The error can be made smaller than any pre-assigned positive number. C) The approximation is exact at some points. D) The approximation converges quickly.

31. In the context of the Bellman equation V(s) = max_a [ R(s,a) + gamma * sum_{s'} P(s'|s,a) * V(s') ], what is the role of successive approximations?

A) To determine the initial state 's'. B) To iteratively update the value function V(s) until it converges to the optimal value function. C) To choose the optimal action 'a' in a single step. D) To define the transition probabilities P(s'|s,a).

32. What is the 'state-space' in dynamic programming?

A) The set of all possible decisions. B) The set of all possible configurations or situations that the system can be in. C) The objective function being optimized. D) The final optimal solution.

33. Which of the following is a common application of dynamic programming?

A) Shortest path problems (e.g., Dijkstra's, Bellman-Ford) B) Knapsack problem C) Longest common subsequence D) All of the above

34. What is the 'horizon' in a dynamic programming problem?

A) The number of states in the state-space. B) The number of stages or time periods over which decisions are made. C) The value of the objective function. D) The initial state.

35. What is a 'policy' in dynamic programming?

A) A single decision made at a specific stage. B) A rule that specifies the decision to be taken in each state. C) The overall objective function. D) The set of all possible states.

36. What does 'function approximation' aim to achieve?

A) To find a complex function that perfectly models a phenomenon. B) To find a simpler function that captures the essential characteristics of a more complex function or data. C) To eliminate all errors in a model. D) To prove the uniqueness of a mathematical function.

37. In the context of approximation in function space, what is 'regression'?

A) Finding a function that passes exactly through a given set of data points. B) Finding a function that best fits a set of data points in some average sense, without necessarily passing through any of them. C) Finding the maximum value of a function. D) Discretizing a continuous function.

38. What is a 'normed vector space'?

A) A vector space where each vector has a length or magnitude (norm). B) A vector space where operations are performed using norms. C) A vector space with a finite number of dimensions. D) A vector space that is also a field.

39. What is the Chebyshev approximation (or minimax approximation)?

A) Minimizing the sum of squared errors. B) Minimizing the maximum absolute error between the function and its approximation. C) Minimizing the integral of the absolute error. D) Minimizing the number of basis functions used.

40. What is the concept of 'discretization' in approximation?

A) Replacing a continuous variable or function with a finite set of discrete values or points. B) Finding the exact analytical solution. C) Using a single step to solve a problem. D) Increasing the complexity of a function.

41. How can dynamic programming be applied to approximate solutions in function space?

A) By treating the function itself as a state in a dynamic programming problem. B) By discretizing the function space and applying standard dynamic programming techniques. C) Dynamic programming is not applicable to function approximation. D) By using dynamic programming to find the optimal parameters of an approximating function.

42. What is the advantage of using 'successive approximations' over direct methods for solving certain equations?

A) Direct methods are always computationally infeasible. B) Successive approximations can handle problems where direct analytical solutions are difficult or impossible to obtain. C) Direct methods always converge faster. D) Successive approximations require fewer iterations.

43. In the context of approximation, what is an 'error bound'?

A) The exact error of the approximation. B) An upper limit on the magnitude of the error of the approximation. C) The number of iterations required for convergence. D) The difference between two successive approximations.

44. What is a 'spline' in the context of function approximation?

A) A single polynomial that approximates a function over an entire interval. B) A piecewise polynomial function that is smooth at the points where the pieces join (knots). C) A function that passes through all data points exactly. D) A method for solving differential equations.

45. How does the choice of norm affect the 'best approximation' in function space?

A) The choice of norm does not affect the best approximation. B) Different norms measure 'closeness' differently, leading to different best approximations. C) The norm determines the dimensionality of the function space. D) The norm is only relevant for convergence, not for the approximation itself.

46. What is the 'state-action value function' (Q-function) in reinforcement learning, which heavily relies on dynamic programming principles?

A) The expected return starting from state 's', taking action 'a', and following a particular policy thereafter. B) The maximum possible return from state 's'. C) The probability of transitioning to the next state. D) The immediate reward received for taking an action.

47. What is the Bellman equation for the Q-function, often solved using successive approximations?

A) Q(s,a) = R(s,a) + gamma * max_{a'} Q(s',a') B) V(s) = max_a [ R(s,a) + gamma * V(s') ] C) Q(s,a) = R(s,a) + gamma * sum_{s'} P(s'|s,a) * Q(s',a') D) Q(s,a) = R(s,a) + gamma * P(s'|s,a)

48. What is the 'value iteration' algorithm in dynamic programming?

A) An algorithm to find the optimal policy directly. B) An iterative method to compute the optimal value function by repeatedly applying the Bellman optimality equation. C) A method to approximate the state space. D) A technique for discretizing the action space.

49. What is 'policy iteration' in dynamic programming?

A) An algorithm that alternates between evaluating a policy and improving it. B) A method to find the optimal action in a single step. C) An approach to approximate the value function. D) A technique for discretizing the state space.

Dynamic programming, approximation in function space, successive approximations - Online Test

Test Results