WorksheetsAdvanced Design Techniques
Total questions: 18
Worksheet time: 9mins
Which of the following is the correct definition of the optimal substructure of a problem?
A way to rearrange problem parameters so that the data of problem is represented in the shortest form possible
A set of all the subproblems that must be solved to construct a solution to the initial problem
A set of all the optimal solutions to a problem
Which of the following strategies can be used to solve a 0-1 knapsack problem effectively?
Brute force
Dynamic programming
Linear programming
O(n^2)
O(nW)
O(n)
O(n long W)
Is the solution to the knapsack problem unique?
yes
no
Any knapsack problem has many solutions
When does a problem have the optimal substructure?
When the problem solution can be optimally constructed from optimal solutions of its subproblems
When the data structures of the problem are well organized
When the fastest algorithm is used to solve the problem
Are subproblems less complex and smaller than the source problem when building substructures?
yes
No, there can be subproblems that have the same complexity as the source problem.
Are permutations of chars in source strings considered while detecting their LCS?
Yes
No
Why are an additional row and column used in a memorization table?
To use more memory
To make the solution algorithm more efficient
How much memory is used to memorize the solutions to subproblems?
O(m + n)
O(m -n)
O(mn)
O(m long n)
Which of the following describes the solution to the ALS problem?
The number of products that can be assembled in a given amount of time
A sequence of lines which must be chosen at each stage of assembly line
The minimum time it takes to assemble a product
Which of the following is the time complexity of solving the ALS problem if n is the number of stages in each line?
O(n)
O(n long n)
O(n^2)
What is a matrix chain multiplication problem?
Constructiion of a permutation of matrices that provides the matrices product of minimum sizes
Computation of a product of matrices by performing minimum elementary operations
Detection of whether given matrices can be multiplied or not
Which of the following is the main idea behind the greedy approach?
To make a random choice at each stage of an algorithm
To make the best choice at each stage of an algorithm
To choose the first suitable solution from the ones available
Is the greedy approach suitable for building heuristic algorithms?
The greedy approach is useless for building heuristic algorithms
Yes, the greedy approach allows you to build algorithms that find suitable solutions, but not necessarily the optimal solutions.
Which of the following is the core idea behind measuring information?
Information and probability are inversely related.
Information cannot be measured at all.
The higher the probability, the more information there is.
What is the information entropy?
The expected value of information distribution
The number of bits required to write the input of a problem
The probability of fast problem solving
Do any encoding schemes provide compression?
Yes, any encoding scheme provides compression for a given message.
No, only certain encoding schemes provide compression for a given message.
There exists an encoding scheme that provides compression for any message.
