Pseudo code

In all the algorithms, always explain (more precisely try to prove) the correctness of your algorithm

You Always Must analyze the running time of any algorithm.

The time complexity should be as small as possible.

A correct algorithm with large complexity, may not get full credit.

Dont write programs for your solutions. Use Pseudo Code

Question 1: Let A and B be two sorted arrays of n elements each (thus A + B has 2 n elements in total). Give an algorithm that finds the median of A B. This is a number that is larger equal that half the elements, and is strictly smaller than half of the elements. Remark: For simplicity assume that every value appears at most once in A B. Example: A =< 2, 7, 19, 22 > B =< 6, 17, 24, 25 > The number 17 is at least as large as < 2, 6, 7, 17 > and smaller than < 19, 22, 24, 25 >