Provide short answers to the following questions. (For running time provide as tight a bound as possible usingasymptotic notation. The algorithm universe is the one introduced in class.) a. What is the best-case running time of InsertionSort?
b. Is HeapSort stable?
c. Does MergeSort sort in-place?
d. Give the asymptotic solution ofT(n) =T(n/3) +n.(5)
e. Give the worst-case running time of RandomizedSelect.
f. Give the worst-case running time for building a MAX-HEAP with t lg t elements.
g. Name 2 dynamic programming algorithm.
h. Name 3 greedy algorithms that solve 3 different problems

:you areto design the controller for alight that functions both as an ordinary light and also as a motion activated light and alarm. a. if the manual switch s is on, then the light l is on. b. besides the manual switch, there is a motion detector, m1, which activatesthis light. c.if motion is detected but the light is on anyway because s is on, only then a secondoutput a, an alarm, is turned on. d. the disable switch, d, disables the motion activated light and alarmbut leaves manual control operation of the light using switch s.(i)read the problem statement and clearly identify the inputs and outputs for the circuit you are designing. (ii)create the truth table for this system; include the light, alarm, switch, disable, and the motion sensor.(iii)draw a schematic of this system.