WorksheetsF. Y. M. Tech. AA DP04020125101
Total questions: 20
Worksheet time: 10hrs 0mins
Backtracking is mainly used to solve problems that involve:
Sequential processing
Exhaustive search with constraints
Greedy selection
Dynamic programming
In backtracking, the process of abandoning a partial solution when it cannot be extended to a valid complete solution is called:
Forward checking
Pruning
Bounding
Optimization
The Graph Colouring Problem aims to:
Minimize the number of vertices
Assign colors to edges
Assign colors to vertices such that adjacent vertices have different colors
Maximize the number of colors
The minimum number of colors required to color a graph such that no two adjacent vertices have the same color is known as:
Clique number
Degree of graph
Chromatic number
Graph order
Constraint Satisfaction Problems (CSPs) consist of:
States, actions, and rewards
Variables, domains, and constraints
Vertices, edges, and weights
Nodes, keys, and pointers
Which of the following is an example of a Constraint Satisfaction Problem?
Shortest path problem
N-Queens problem
Minimum spanning tree
Binary search
Branch and Bound technique is primarily used for solving:
Feasibility problems
Optimization problems
Sorting problems
Searching problems
In Branch and Bound, the bound refers to:
Depth of the tree
Estimated best possible solution
Number of branches
Maximum recursion depth
Which traversal strategy is commonly used in Branch and Bound algorithms?
Breadth First Search
Depth First Search
Best First Search
Random Search
The main difference between Backtracking and Branch and Bound is that Branch and Bound:
Finds all feasible solutions
Uses bounding functions to eliminate suboptimal solutions
Uses recursion instead of iteration
. Does not require constraints
Probabilistic analysis of algorithms focuses on:
Worst-case running timeBest-case running time
Best-case running time
Expected running time
Memory usage
Indicator random variables are mainly used to:
Reduce space complexity
Simplify the calculation of expected values
Generate random numbers
Count recursive calls
The expected value of an indicator random variable is equal to:
0 or 1
Probability of the event occurring
Square of the probability
Always 1
The Hiring Problem is commonly used to illustrate:
Greedy strategy
Divide and conquer
Probabilistic analysis
Dynamic programming
Which of the following is a characteristic of randomized algorithms?
Always produce the same output
Do not use random numbers
Make random choices during execution
Cannot be analyzed mathematically
Monte Carlo algorithms are characterized by:
Guaranteed correctness with variable running time
Guaranteed running time with possible error in result
Deterministic behavior
. No use of probability
Las Vegas algorithms differ from Monte Carlo algorithms in that they:
Have fixed execution time
May produce incorrect results
Always produce correct results
Do not use randomness
Which of the following problems is commonly solved using Las Vegas algorithms?
Matrix multiplication
Sorting
Searching in a hash table
Randomized Quick Sort
In Randomized Quick Sort, randomness is introduced by:
Randomly selecting the pivot
Randomly selecting array size
Randomly swapping elements
Randomly choosing recursion depth
The expected time complexity of Randomized Quick Sort is:
A.
O(n)
O(n log n)
O(n²)
O(log n)
