Consider a directed graph $G=(V,E)$ with negative edge weights, but no negative weight cycles. Let $|V| = 100$ and $|E| = 1000$. What is the maximum n...
Consider a set of 5 symbols $\{A, B, C, D, E\}$ with probabilities $0.35$, $0.25$, $0.20$, $0.15$, and $0.05$ respectively. If we construct an optimal...
Let $L_1$ and $L_2$ be two languages such that $L_1 \le_p L_2$ (that is, $L_1$ is polynomial-time reducible to $L_2$). Which of the following statemen...
We want to compute the optimal parenthesization of a matrix chain product $A_1 A_2 A_3 A_4$ with dimensions $10 \times 20$, $20 \times 30$, $30 \times...
Let $G=(V,E)$ be a connected, undirected graph with distinct edge weights. Let $e$ be the edge with the minimum weight in $G$. Which of the following ...
Suppose Dijkstra's single-source shortest path algorithm is run on a directed graph $G=(V,E)$ with source $s$. If some edge weights are negative, whic...
Let $N$ be the number of elements in an array. What is the worst-case number of comparisons required to sort this array using Heap Sort and Quick Sort...
In the Floyd-Warshall all-pairs shortest paths algorithm, let $d_{ij}^{(k)}$ be the weight of the shortest path from vertex $i$ to vertex $v_j$ for wh...