For your reference:
𝑎, 𝑏, 𝑐 are constants and 𝑎 ≥ 1, 𝑏 > 1, and 𝑐 > 0
𝑓(𝑛) = 𝑂(𝑞(𝑛)) for some polynomial function 𝑞(𝑛).
Let ℎ(𝑛) = 𝑛
log𝑏 𝑎
Case 1: If 𝑓(𝑛)
ℎ(𝑛)
= 𝑂(𝑛
−𝜖
) for some 𝜖 > 0 then 𝑇(𝑛) = 𝜃(ℎ(𝑛))
Case 2: If 𝑓(𝑛)
ℎ(𝑛)
= 𝜃(log𝑘 𝑛) for some 𝑘 ≥ 0 then 𝑇(𝑛) = 𝜃(ℎ(𝑛) log𝑘+1 𝑛)
Case 3: If 𝑓(𝑛)
ℎ(𝑛)
= Ω(𝑛
𝜖
) for some 𝜖 > 0 and if 𝑎𝑓 (
𝑛
𝑏
) ≤ 𝑐𝑓(𝑛) for some constant 𝑐 ∈ (0,1) and
sufficiently large n, then 𝑇(𝑛) = 𝜃(𝑓(𝑛))
Solve the following recurrence relations. You must use the Master Theorem, if appropriate. Show your work.
This algorithm provides a solution to that checks to see if there is a path from start to end in a graph. The nodes
are integers in the range [0..n). The edges of the graph are stored in the Boolean array adjacencyMatrix, which is
in scope for the method.
Add code to the algorithm below to make it efficient. (25 points)
Give the worst case running time of an efficient solution, using big-O notation. Make your bounds as tight as
possible. (5 points)
boolean[][] adjacencyMatrix = new boolean[n][n];
// return true iff there is a path from start to end
boolean isConnected(int start, int end) {
return isConnected(start, end, n-1 );
}
// return true iff there is a path from start to end via intermediate nodes [0..via]
boolean isConnected(int start, int end, int via ){
if (via == -1) return adjacencyMatrix[start][end];
boolean retVal = isConnected(start,end,via-1 ) ||
(isConnected(start,via,via-1 ) &&
isConnected(via,end,via-1 ));
return retVal;
}
For the following problem, define: (40 points)
a. a problem structure (as an English definition, as we have done in the lecture and the last assignment)
b. a recurrence relation that recursively defines the solution to the problem in terms of solutions to smaller
sub-problems (and includes base case definition(s))
A three-smooth number is a number of the form 2
𝑖3
𝑗
for integers 𝑖,𝑗 ≥ 0. The sequence 1, 2, 3, 4, 6, 8, 9, 12, 16,
18, 24, 27, 32, 36, 48, 54, 64, 72, 81, and 96 shows the first 20 three-smooth numbers.
Determine if a positive integer k is three-smooth.
True False Puzzles (6 points each). Explain your reasoning.
True False A decision problem is decidable if it is possible to construct a Turing machine that, for all valid
input, will halt in a finite amount of time and produce the correct output.
Explanation:
True False It is possible to construct a correct algorithm that takes as input another program and
determines whether the program will output an even number for a given input.
Explanation:
True False If the Travelling Salesman Decision Problem can be solved in polynomial time, then the 0-1
Knapsack Decision Problem can be solved in polynomial time.
Explanation:
True False If the 0-1 Knapsack Decision Problem can be solved in polynomial time, then the Travelling
Salesman Decision Problem can be solved in polynomial time.
Explanation:
True False An efficient heap creation algorithm can create a max heap of integers from an array in O(n) time
in the worst case.
Explanation:
True False An efficient approach to finding the median value in an unsorted array will take O(n) time in the
average case.
Explanation:
True False Meta-heuristic optimization approaches, including local search, provide guarantees about the
quality of their solutions.
Explanation:
True False If a problem is NP-hard, it is undecidable.
Explanation:
Suppose that an exhaustive search algorithm considers all subsets of elements of an array of n elements. Provide a
tight (lower) bound for the running time of the algorithm using asymptotic notation. (4 points)
Suppose that an exhaustive search algorithm considers all permutations of an array of n elements. Provide a tight
(lower) bound for the running time of the algorithm using asymptotic notation. (4 points)
Suppose that you had 1 million 8-bit integers, which sorting algorithm would be fastest? (4 points)
Suppose that you had 1 million 32-bit integers, with 10 inversions, which sorting algorithm would be fastest? (4
points)
(12 points) Consider the digraph to the right. In
valid topological sorts of the graph:
- Which vertices can appear first in the
sort?
- Which vertices can appear second in the
sort?
- Which vertices can appear second-to-last in the sort?
- Which vertices can appear last in the sort?
Consider the following weighted, directed graph. The nodes listed in an order produced by one of the algorithms
that we studied. Identify the algorithm. (5 points each)
Notes:
For Dijkstra’s algorithm, TSP algorithm, Floyd-Warshall algorithm, and Prim’s algorithm, assume that the input
graph is the undirected graph produced by ignoring edge directions.
Write “None of the above” if none of the description match.
a) Bottom-Up Floyd-Warshall algorithm (order in which intermediate nodes are considered)
b) Breadth-first search (order in which nodes are visited starting at node 0, and we add neighbors of a node
to the queue in numerical order)
c) Depth-first search (order in which nodes are visited starting at node 0, and the neighbors of a node are
considered in numerical order)
d) Dijkstra’s algorithm (order in which destination nodes have their shortest paths calculated, with 0 as the
starting node.)
e) Prim’s Algorithm, starting at node 0, order in which a node is added to the tree
f) A list of the order in which nodes could be visited in the optimal Travelling Salesman Problem (TSP) tour
g) Topological sort