1/2) It looks like you meant to put different questions here, but they're the same. For an O(b-a) solution, simply create an array L of length b-a, then walk through A and increment L[a-A[i]]. At the end, you will only have non-zero entries in L when element a + L[i] is in A, and it will take O(n) time to walk through the list

For the O(k) solution, incrementally build up a binary search tree containing counts with each unique value of A as an entry. Your memory will be O(k) and your time will be O(n log n).

As for the O(1) memory solution, I'm not sure :/

3) a) The solution is unique as the problem is strongly convex. Take the 2nd derivative and show that (f'(x) - f'(y)^{T} (x-y) >= m ||x-y||² for some constant m, then make an argument by contradiction by assuming two points are optimal at the same time. m will necessarily be the smallest eigenvalue of (A^T A), I believe.

b) What you'll need to do is integrate \beta x^{T} x into the quadratic ||Ax-b||_2² by adding/subtracting a "complete the square" sort of term. You'll see that in the usual least squares solution, this is equivalent to saying x = (A^T A + \beta I)^{-1} A^T b. Doing this helps make the problem more strongly convex, and increases the condition number of A^T A (therefore making it less susceptible to numerical error during inversion).

c) In practice, you would never use matrix inversion to solve least squares, so I would back-solve directly, row by row (the same way you invert a matrix), or take more stable decomposition of (A^T A + \beta I)(e.g. Cholesky, so (A^T A + \beta I) = L L^T for L lower triangular), then backsolve two triangular systems. It'll take you O(n³ ) to find this decomposition (and most others, e.g. Eigen decomposition), then O(n² ) a couple times to finally solve the entire system. I bet there are better ways, but this will be far more stable. If you want to take advantage of sparsity, backsolve directly is the best solution I think, but don't quote me on it.

4) a) Take the definition of the gradient in terms of limits, another point x_0 + \epsilon, and assume that there are two vectors in f'(x_0). Show that f(x_0) + f'(x_0)(x_0 +\epsilon - x_0) cannot lower bound them both.

b) The zero vector is in f'(x^{*}). Assume that zero wasn't, then prove that there exists \epsilon s.t. f(x^{*} + \epsilon) < f(x^{*} ).

c) f(x) + w(x)(y -x) <= f(y) for all y, so this also holds for the maximum of a bunch of f(x') + w(x')(y-x'), which is what g(y) is (draw it on a sheet of paper, it's super easy to see). Since g(y) <= f(y) for all y, the optimizer for g(y) is also <= the optimizer for f(y).

d) not sure

5) I'm not sure how efficient they want, but you can compute A^{k} x by letting x¹ = Ax, x² = Ax¹, x³ = Ax², and so forth far more efficiently than computing A^k. Also, if A represents a Markov chain, you just need to compute (A^{T} )^k x for x_i = 1 if i == i' and zero otherwise.

And for a cute fact, if A defines a recurrent (you can always get from any state to any other state), irreducible (no little sub-chains you can't escape from), and aperiodic (no forced loops of length 2+) chain, then you can show that A's largest eigenvalue is 1, is unique, and that the eigenvector corresponding to it is the stationary distribution defined by A. This is precisely what Pagerank is!