Question 36
Which algorithm finds All-Pairs Shortest Paths in a graph with negative edge weights (but no negative cycles)?
Floyd-Warshall handles negative edge weights correctly in O($V^3)$ time as long as there are no negative weight cycles.
Which algorithm finds All-Pairs Shortest Paths in a graph with negative edge weights (but no negative cycles)?
Floyd-Warshall handles negative edge weights correctly in O($V^3)$ time as long as there are no negative weight cycles.
What is the worst-case search time complexity in a Skip List with N elements?
Skip Lists achieve O(log N) search time with high probability, but if coin flips produce a single level, search degenerates to O(N) linear scan.
Which traversal of a Binary Search Tree (BST) containing distinct keys produces the keys in strictly increasing order?
In-order traversal visits Left, Root, Right. For a BST with distinct keys, this produces the keys in strictly increasing order.
What is the time complexity of Kosaraju's algorithm for finding Strongly Connected Components (SCCs)?
Kosaraju's algorithm performs two DFS passes (one on G and one on reversed graph $G^{T})$ along with stack operations, running in O(V + E) time.
In a Min-Heap implemented as an array, what is the index of the left child of node at index i (0-based indexing)?
For 0-based array indexing in binary heaps, node i's left child is at 2i + 1 and right child is at 2i + 2.