1. Assume an n × n matrix A is given, containing only 1's and 0's, such that, in each row, all 1's come before all 0's. Give an O(n log n) algorithm to count all 1's in A.

2. Let A and B be two sequences of n integers each. Given an integer m, describe an O(n log n) algorithm to determine if there is an element a of A and an element b of B such that m = a + b.

3. Give a linear-time non-recursive algorithm for inorder traversal of a binary tree. (Hint: Use a stack.)