True (t) or false (f)? Beware of guessing incorrect answer a.[t f] A graph G = (

Question

True (t) or false (f)? Beware of guessing incorrect answer a.[t f] A graph G = (V, E) with |E| = |V| 1 is a tree. b. [t f] Merge sort is an 'in-place' sorting algorithm. c. [t f] In worst case, Mergesort runs asymptotically faster than Quicksort. d. [t f] In worst case, Counting Sort can be forced to run Ohm(n^3) by choosing suitable input data. e. [t f] There is a good greedy algorithm for the fractional Knapsack Problem. f. [t f] In an undirected graph, cross edges returned by DFS indicate cycles. g. [t f] If the comparator input wires of a comparison network have depth d_x and d_y, than the comparator output wires have depth min(d_x, d_y) + 1. h. [t f] Johnsons' algorithm solves the APSP Problem asymptotically faster than Dijkstra (using a Fibonacci Heap) applied to every vertex. i. [t f] Huffman codes are an example of a greedy algorithm j. [t f] Radix sort is stable. k. [t f] In worst case, R-Select runs in theta(n). l. [t f] In worst case, Strassen's fast matrix multiplication algorithm runs in theta(n^log_7 2).

Explanation / Answer

a) True

b) True

c) False

Quick sort is faster than Merge sort

d) False

Worst case for counting sort is O(n2)

e) True

The method is good for solving fractional knapsack problem

f) True

we can detect cycles from the cross edges in Depth First Search

g) True

h) False

Dijikshtra's algorithm is faster than Johnsons algorithm

i) True

j) True

Radix sort is fast and stable.

k) False

The worst case of R-select is O(n2)

l) True

The Strassens algorithm runs in O(n ln 7)

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.