1.Write an algorithm in pseudocode for each description of the input and output. (a) Input: a1, a2,...,an, a sequence of numbers, where n 1 n, the length of the sequence. Output: "True" if the sequence is nondecreasing and "False" otherwise. A sequence of numbers is nondecreasing if each number is at least as large as the one before. (b) Input: a1, a2,...,an, a sequence of numbers, where n 1 n, the length of the sequence. Output: "True" if there are two consecutive numbers in the sequence that are the same and "False" otherwise. (c) Input: a1, a2,...,an, a sequence of numbers, where n 1 n, the length of the sequence. Output: "True" if there are any two numbers in the sequence whose sum is 0 and "False" otherwise. (d) Input: a1, a2,...,an, a sequence of numbers, where n 1 n, the length of the sequence. Output: "True" if there are any three numbers in the sequence that form a Pythagorean triple. The numbers x, y, and z are a Pythagorean triple if x2 + y2 = z2. (e) Input: a1, a2,...,an, a sequence of distinct numbers, where n 2 n, the length of the sequence. Output: The second smallest number in the sequence. Q.2 Characterize the rate of growth of each function f below by giving a function g such thatf = (g). The function g should be one of the functions in the table of common functions (Table 7.2.2). (c) f(n) = 2n + 3n (d) f(n) = 7(log log n) + 3(log n) + 12n (e) f(n) = 9(n log n) + 5(log log n) + 5 (f) f(n) = nlog37 n (g) f(n) = n21 + (1.1)n (h) f(n) = 23n + n3 2 Table 7.2.2: Common functions in algorithmic complexity. Function Name (1) Constant (log log n) Log log (log n) Logarithmic (n) Linear (n log n) n log n (n2) Quadratic (n3) Cubic (nk), k 1 Polynomial (cn), c > 1 Exponential (n!) Factorial Q3. Proving negative results on the growth of functions. (a) f(n) = n/100. Prove that it is not true that f = O(n)O(n). (b) f(n) = n(3/2). Prove that it is not true that f = (n2). Q4. Relationships between bounds on the growth rate of functions. (a) Let f be a function whose domain is R+. Show that if f = O(n), then f = O(n2). (b) Let f be a function whose domain is R+. Show that if f = O(n), then it is not true thatf = (n2). Q5. Q6