Description

1 Problem 1 (12 points)
Given a list of n integers x1,…,xn (possibly negative), find the indices i,j ∈ [n] (i 6= j) such that xi · xj is maximized. Your algorithm must run in O(n) time.
2 Problem 2 (12 points)
Let S be an array of integers {S[1],S[2],…,S[n]} such that S[1] < S[2] < ··· < S[n]. Design an algorithm to determine whether there exists an index i such at S[i] = i. For example, in {−1,2}, S[2] = 2.
Your algorithm should work in O(logn) time. Prove the correctness of your algorithm.
3 Problem 3 (13 points)
We say a 3-tuple of positive real numbers (x1,x2,x3) is legal if a triangle can have sides of length x1,x2 and x3. Given a list of n positive real numbers {x1,…,xn}, count the number of unordered 3-tuples (xi,xj,xk) that are legal. For example, for the numbers {3,5,8,4,4}, (3,4,5) is a legal tuple while (4,4,8) is not.
1
4 Problem 4 (13 points)
You are given one unsorted integer array A of size n. You know that A is almost sorted, that is it contains at most m inversions, where inversion is a pair of indices (i,j) such that i < j and A[i] > A[j].
1. To sort array A you applied algorithm Insertion Sort. Prove that it will take at most O(n + m) steps.
2. What is a maximum possible number of inversions in the integer array of size n?
2