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

版权所有：留学生编程辅导网 2018 All Rights Reserved 联系方式：QQ:99515681 电子信箱：99515681@qq.com

免责声明：本站部分内容从网络整理而来，只供参考！如有版权问题可联系本站删除。