Complete the 12 sentences below. Choose the best answer for each one.
1Before scoring each route, the program must traverse the ............... in depth-first order.
Wrong!
"graph" is correct because depth-first traversal applies to nodes and edges in a graph, not to a rule-of-thumb heuristic.
2To avoid recomputation, the recursive function ............... the results of previously solved subproblems.
Wrong!
"memoizes" is correct because storing results of previously solved subproblems is memoization.
3At every junction, the ............... algorithm selects the cheapest available edge without revisiting earlier decisions.
Wrong!
"greedy" is correct because making the locally best choice at each step defines a greedy algorithm.
4Once the lower bound exceeds the current best cost, the solver prunes that ............... of the search tree.
Wrong!
"branch" is correct because a search tree has branches that can be pruned when they cannot contain a better solution.
5Because the matrix is stored explicitly, the algorithm's ............... grows quadratically with the number of vertices.
Wrong!
"space complexity" is correct because the sentence refers to additional memory, not running time.
6Given identical input and initial state, a ............... algorithm always returns the same output.
Wrong!
"deterministic" is correct because the same input always produces the same output.
7During breadth-first search, the queue receives the ............... of the current node before the next layer is explored.
Wrong!
"successors" is correct because breadth-first search enqueues the nodes directly reachable from the current node.
8Dijkstra's method repeatedly ............... candidate paths from the priority queue in order of increasing tentative distance.
Wrong!
"dequeues" is correct because removing items from a queue or priority queue is dequeuing.
9The hash table resolves the ............... by chaining entries whose distinct keys produce the same hash value.
Wrong!
"collision" is correct because two different keys mapping to the same hash value create a hash collision.
10After every insertion, the ............... of the heap requires each parent to have priority at least as high as its children.
Wrong!
"invariant" is correct because a heap's parent-child ordering rule is a property maintained throughout operations.
11The ............... algorithm updates every vertex's estimate until no further improvement is possible.
Wrong!
"iterative" is correct because the algorithm repeats updates until a stopping condition is reached.
12For comparison-based sorting, the ............... bound proves that any solution must perform at least this many comparisons in the worst case.
Wrong!
"lower" is correct because a lower bound states that any algorithm must take at least a certain amount of work.
Exercise complete
0 out of 12
correct answers
Answers
- Before scoring each route, the program must traverse the graph in depth-first order.
- To avoid recomputation, the recursive function memoizes the results of previously solved subproblems.
- At every junction, the greedy algorithm selects the cheapest available edge without revisiting earlier decisions.
- Once the lower bound exceeds the current best cost, the solver prunes that branch of the search tree.
- Because the matrix is stored explicitly, the algorithm’s space complexity grows quadratically with the number of vertices.
- Given identical input and initial state, a deterministic algorithm always returns the same output.
- During breadth-first search, the queue receives the successors of the current node before the next layer is explored.
- Dijkstra’s method repeatedly dequeues candidate paths from the priority queue in order of increasing tentative distance.
- The hash table resolves the collision by chaining entries whose distinct keys produce the same hash value.
- After every insertion, the invariant of the heap requires each parent to have priority at least as high as its children.
- The iterative algorithm updates every vertex’s estimate until no further improvement is possible.
- For comparison-based sorting, the lower bound proves that any solution must perform at least this many comparisons in the worst case.