Radix sort is generally faster than comparison-based sorting algorithms for sorting _______ integers.
- Binary
- Large
- Prime
- Small
Radix sort is generally faster than comparison-based sorting algorithms for sorting small integers because it takes advantage of the fixed-size nature of integers and avoids comparisons.
How is the Knapsack Problem different from other optimization problems?
- It aims to minimize the number of selected items.
- It does not consider any constraints; it's about finding the absolute optimum.
- It focuses on maximizing the total value of selected items within certain constraints.
- It involves minimizing the total weight of selected items.
The Knapsack Problem is distinct as it specifically aims to maximize the total value of selected items within certain constraints, making it a constrained optimization problem. Other optimization problems may have different objectives or constraints.
Insertion Sort is a _______ sorting algorithm that builds the final sorted array one _______ at a time.
- Comparison, element
- Divide and conquer, subset
- Incremental, element
- Simple, pass
Insertion Sort is an incremental sorting algorithm that builds the final sorted array one element at a time. It iterates through the array, comparing and inserting elements in their correct positions.
Which traversal technique does DFS primarily employ when traversing a graph?
- Breadth-First Search (BFS)
- Level-Order Traversal
- Post-order Traversal
- Pre-order Traversal
DFS primarily employs Pre-order Traversal when traversing a graph. In Pre-order Traversal, the algorithm visits the root node, then recursively performs Pre-order Traversal on the left subtree and the right subtree.
In the LIS problem, "patience" refers to the ability to _______ and _______ sequences of numbers.
- Merge, combine
- Merge, divide
- Split, combine
- Split, merge
In the Longest Increasing Subsequence (LIS) problem, "patience" refers to the ability to split and combine sequences of numbers. The algorithm involves finding the longest increasing subsequence in a given sequence.
The patience sorting algorithm is a technique inspired by a card game called _______.
- Go Fish
- Poker
- Rummy
- Solitaire
The patience sorting algorithm is inspired by the card game Solitaire. In this algorithm, the process of sorting is similar to organizing a deck of cards in the game of Solitaire.
What is the time complexity of binary search on a sorted array?
- O(1)
- O(log n)
- O(n)
- O(n^2)
The time complexity of the binary search algorithm on a sorted array is O(log n), where 'n' is the number of elements in the array. This logarithmic time complexity makes binary search highly efficient for large datasets.
The effectiveness of the A* search algorithm heavily depends on the _______ function, which should be admissible and consistent.
- Heuristic, Evaluation
- Indexing, Searching
- Recursive, Iterative
- Sorting, Comparison
The effectiveness of the A* search algorithm heavily depends on the heuristic function, which should be admissible (never overestimates) and consistent. The heuristic guides the search towards the goal efficiently, influencing the algorithm's ability to find the optimal path in various applications.
Can Prim's and Kruskal's algorithms be used to find the shortest path between two vertices in a graph? Explain.
- No, neither Prim's nor Kruskal's algorithms can be used to find the shortest path.
- Only Kruskal's algorithm can find the shortest path, not Prim's.
- Only Prim's algorithm can find the shortest path, not Kruskal's.
- Yes, both algorithms can find the shortest path between two vertices in a graph.
Neither Prim's nor Kruskal's algorithms are designed to find the shortest path between two specific vertices. They are specifically used for finding minimum spanning trees, which may not necessarily correspond to the shortest path between two vertices. Additional algorithms like Dijkstra's or Bellman-Ford are more suitable for shortest path problems.
Consider a scenario where Quick Sort consistently selects the smallest or largest element as the pivot. How would this affect the algorithm's performance, and what adjustments could be made to address this issue?
- Quick Sort would remain unaffected as long as the array is randomly shuffled
- Quick Sort's performance would degrade to worst-case time complexity
- Quick Sort's performance would improve as it always selects an extreme pivot
- Quick Sort's performance would vary depending on the size of the array
Consistently selecting the smallest or largest element as the pivot in Quick Sort can lead to uneven partitions, causing the algorithm's performance to degrade to worst-case time complexity. To address this issue, adjustments such as choosing a pivot using a median-of-three strategy or random pivot selection can help improve partition balance and overall performance.