What is the time complexity of radix sort?
- O(d * (n + b))
- O(log n)
- O(n log n)
- O(n^2)
The time complexity of radix sort is O(d * (n + b)), where 'd' is the number of digits in the input numbers, 'n' is the number of elements, and 'b' is the base of the numeric representation.
How does the stability of Insertion Sort make it suitable for certain applications?
- Ignores equal elements
- Maintains the relative order of equal elements
- Randomly shuffles equal elements
- Sorts equal elements based on a random key
The stability of Insertion Sort ensures that the relative order of equal elements is maintained. This property is crucial in applications where maintaining the original order of equivalent elements is necessary, such as sorting a database by multiple criteria without disturbing the existing order of records.
Suppose you are developing a video game where characters need to navigate through a complex environment. Discuss the advantages and limitations of using A* search for pathfinding in this scenario.
- Advantages are minimal, but limitations are significant
- Advantages include efficient pathfinding, but limitations may arise in dynamic environments
- Both advantages and limitations are minimal
- Both advantages and limitations are significant
A* search is advantageous in video game pathfinding due to its efficiency, but it may face limitations in dynamic environments where paths change frequently. Understanding these trade-offs is crucial for optimal pathfinding in a video game with characters navigating through a complex environment.
What is the role of augmenting paths in the Ford-Fulkerson algorithm?
- Augmenting paths are paths with negative capacities, allowing for flow reduction.
- Augmenting paths are paths with no residual capacity, indicating maximum flow has been reached.
- Augmenting paths are used to increase the flow in the network by pushing more flow through the existing edges.
- Augmenting paths determine the maximum flow in the network without modifying the existing flow values.
Augmenting paths play a crucial role in the Ford-Fulkerson algorithm by allowing the algorithm to iteratively increase the flow in the network. These paths are identified and used to augment the flow, making progress toward the maximum flow in the network.
Unlike stacks, queues follow the _______ principle and are used in scenarios like _______ management.
- FIFO (First-In-First-Out)
- LIFO (Last-In-First-Out)
- Priority
- Random
Unlike stacks, queues follow the FIFO (First-In-First-Out) principle. Queues are used in scenarios like job scheduling and task management, where tasks are processed in the order they arrive.
How does a hash table handle collisions?
- By ignoring collisions and overwriting existing values.
- By rearranging the elements in the table.
- By resizing the hash table to accommodate more elements.
- By using techniques such as chaining or open addressing to resolve conflicts.
Hash tables handle collisions by employing techniques such as chaining or open addressing. Chaining involves maintaining a linked list at each bucket to store colliding elements, while open addressing involves finding the next available slot in the table.
Multidimensional arrays are arrays of _______ arrays.
- Heterogeneous
- Homogeneous
- Linear
- Non-linear
Multidimensional arrays are arrays of homogeneous arrays, meaning that each element in the outer array points to another array of the same data type.
Reversing a linked list recursively involves changing the _______ of each node.
- Data
- Next pointer
- Previous pointer
- Value
Reversing a linked list recursively involves changing the previous pointer of each node. In each recursive call, the next pointer of each node is redirected to its previous node, gradually reversing the entire list.
In the context of strings, what does the term "edit" refer to in the Edit Distance algorithm?
- All of the above.
- Deleting characters from a string.
- Inserting characters into a string.
- Modifying characters in a string.
In the context of strings and the Edit Distance algorithm, the term "edit" refers to all three operations: deleting characters, inserting characters, and modifying characters in a string. These operations are used to transform one string into another.
Which shortest path algorithm is suitable for finding the shortest path from a single source vertex to all other vertices in a weighted graph with non-negative edge weights?
- Bellman-Ford Algorithm
- Dijkstra's Algorithm
- Floyd-Warshall Algorithm
- Prim's Algorithm
Dijkstra's Algorithm is suitable for finding the shortest path from a single source vertex to all other vertices in a weighted graph with non-negative edge weights. It uses a greedy approach, iteratively selecting the vertex with the smallest known distance to the source.