91Ó°ÊÓ

Give an algorithm for the following problem and determine its time complexity. Given a list of \(n\) distinct positive integers. partition the list into two sublists, each of size \(n / 2\), such that the difference between the sums of the integers in the two sublists is maximized. You may assume that \(n\) is a multiple of 2

Give a \(\Theta(n \text { lg } n)\) algorithm that computes the reminder when \(x^{n}\) is divided by \(p .\) For simplicity, you may assume that \(n\) is a power of 2 That is, \(n=2^{k}\) for some positive integer \(k\)

Explain in English what functions are in following sets. a. \(n^{O(1)}\) b. \(O\left(n^{O(1)}\right)\) c. \(O\left(O\left(n^{O(1)}\right)\right)\)

Show that the function \(f(n)=\left|n^{2} \sin n\right|\) is in neither \(O(n)\) nor \(\Omega(n)\)

Justify the correctness of the following statements assuming that \(f(n)\) and \(g(n)\) are asymptotically positive functions. a. \(f(n)+g(n) \in O(f(n)), g(n))\) b. \(f^{2}(n) \in \Omega(f(n))\) c. \(f(n)+o(f(n)) \in \Theta(f(n), \text { where of } o(f(n))\) means any function \\[g(n) \in o(f(n))\\]

Give an algorithm for the following problem, Given a list of \(n\) distinct positive integers, partition the list into two sublists, each of size \(n / 2,\) such that the difference between the sums of integers in the two sublists is minimized. Determine the time complexity of your algorithm. You may assume that \(n\) is a multiple of 2