1. True or False? For each of the statements below, determine whether it is True or False. Then, briefly explain your an
Posted: Thu Jul 14, 2022 2:18 pm
1. True or False?For each of the statements below, determine whether it is True orFalse. Then, briefly explain youranswers or provide counterexamples.a) Consider the Interval Scheduling Problem we discussed in theclass, where we want to maximize thenumber of compatible (i.e., non-overlapping) intervalsClaim: The latest-start-time-first algorithm is optimal for theabove problemClaim: The fewest-conflicts-first algorithm is optimal for theabove problem.b) Claim: An O(n2) algorithm always runs faster than an O(2n)algorithm.c) The solution to the recurrence T(n) = 2T(n/2) + log n is T(n) =O(n log n)d) Given any directed graph with (possibly negative) edge weights,the Bellman-Ford algorithmguarantees to find a shortest s à t path from a given source node sto a given destination node t.