1) Write an algorithm that given an unsorted array returns whether an increasing subsequence of length
3 exists or not in the array. Your algorithm should run in O(n) time complexity and O(1) space
2) Consider the following multithreaded algorithm for performing pairwise multiplication on n-element
arrays A[1..n] and B[1..n], storing the multiplications in C[1..n]:
Analyze the work, span and parallelism of this algorithm.
3) Design a dynamic programming algorithm for the version of the knapsack problem in which there are
unlimited quantities of copies for each of the n item kinds given. Indicate the time efficiency of the