Algorithm Problem

Analyze each of the following statements to indicate whether the statement is true or false, respectively.  If the statement is correct, briefly state why.  If the statement is wrong, correct it.  Please elaborate on your justification or correction, but be brief.  One-sentence explanations should suffice.

T    F For any asymptotically nonnegative function f (n). we have

f(n) + o( f (n)) = O( f (n)).

T    F By Case 2 of the Master Theorem, the solution to the recurrence

T (n) = 3T(n/3) + O(1g n) is T (n) =  (n 1g n).

T    F By reducing the problem of sorting to the problem of building a      heap, one can prove that building an n-element heap takes time  (n 1g n) in the worst case.

T    F The worst-case funning time of randomized quicksort on an array of length n is  (n2).

T    F The (1g n )th smallest number of n unsorted numbers can be determined in O (n) worst-case time.


T    F By carefully selecting the n keys to be stored in a hash table of size m  n with universal hashing, an adversary can make retrieval of one key take  (n) time.

T    F A binary search tree on n integer keys in the range from 1 to n2 can be constructed in O (n) worst-case time.

T    F the fastest disjoint-set union structure to date can be implemented such that each of m operations on n sets takes at most  (m, n) worst-case time, where  (m, n) is a functional inverse of Ackermann’s function.

T    F The problem of determining an optimal order for multiplying a chain of matrices can be solved by a greedy algorithm, since it displays the optimal substructure and overlapping subproblems properties.

T    F Kruskal’s algorithm for finding a minimum spanning tree of a weighted, undirected graph is an example of a dynamic programming algorithm.

T    F The topological sort of an arbitrary directed graph G = (V, E) can be computed in linear time.

T    F In O(E + V 1g V) time, Dijkstra’s algorithm with Fibonacci heap can be used to compute shortest paths from a source vertex to a other vertices in a graph G = (V, E) with nonnegative edge weight.

T    F The Bellman-Ford algorithm can be used to solve a special case linear programming in which each inequality has the form xi + xj aI j.

T    F The transitive closure of a directed graph G = (V,E) can be computed in O(V3) time by the Floyd-Warshall algorithm, which us dynamic programming and repeatedly squares the adjacency matrix of G.

T    F In a flow network G = (V, E) with capacity and flow functions c and f, it is always the case that cf (u, v) + cf (v, u) = c (u, v) + c(v, u) for all u, v  V.

T    F In O (V +E) time, a matching in a bipartite graph G = (V, E) can be tested to determine whether it is maximum.

T    F The depth of any n-input sorting network must be at least 21g n 21g e, where e = 2.718281828…is the base of the natural logarithm. (Hint: One level of a sorting network has at most n/2 comparators).

T    F a Wallace-tree multiplier for multiplying two n-bit numbers contains (n) bits.

T    F A prefix computation can be defined in terms of any binary operator.

See attached file for full problem description.

Attached file(s):

Analyze true or false.doc  View File