Q1. Let's consider a searching problem as follow: Input: A sequence of n numbers a1,a2,,an stored in array A[1:n] and a value x. Output: An index i such that x equals to A[i] or the special value NIL if x does not appear in A. To solve this problem, we write pseudocode for linear search, which scans through the array from the beginning to the end, looking for x. (1) Fill in the blanks of the pseudocode. LINEAR-SEARCH (A,n,x) i=1 while and if i=i+1 return NIL else return (2) A) How many elements of the input array must be examined on average? (assuming that the element being searched for is equally likely to be any element in the array) B) Using -notation, give the average-case running times of linear search. (3) A) How many elements of the input array need to be checked on the worst case? B) Using -notation, give the worst-case running times of linear search. Q2. Consider sorting n numbers stored in array A[1:n] by first finding the smallest element of A[1:n] and exchanging it with the element in A[1]. Then find the smallest element of A[2:n], and exchange it with A[2]. Then find the smallest element of A[3:n], and exchange it with A[3]. Continue in this manner for the first n1 elements of A. (1) Complete the below pseudocode to describe the above sorting procedure. (2) Why does it need to run for only the first n1 elements, rather than for all n elements? Explain it. (3) Using -notation, give the worst-case running time of this sort. Justify your answer. (*hint: you can sum up the number of comparisons within inner for loop at every cycle of outer for loop.) (4) Using -notation, give the best-case running time of this sort. Explain the reason. Q3. BubbleSort is a popular, but inefficient sorting algorithm. It works by repeatedly swapping adjacent elements that are out of order. The procedure BUBBLESORT sorts array A[1:n]. BUBBLESORT (A,n) 1234fori=1ton1forj=ndowntoi+1ifA[j] (2) Based on the result of (1), what is the worst-case running time of BUBBLESORT? (use -notation) Q4. Merge Sort. Using merge-sort Figure on page 14 of "02_Getting_started_2_2023Spring.pdf" slide as a model, illustrate the operation of merge sort on an array initially containing the sequence 3,41,52,26,38,57,9,49. Indicate the order of sequence (blue numbers on the slide). Q5. Let f(n) and g(n) be asymptotically positive functions. Choose True / False for the following conjectures. Justify your answer. (1) T. F. f(n)=O(g(n)) implies g(n)=O(f(n)). (2) T. F. f(n)=O(g(n)) implies g(n)=(f(n)).