all logarithms in this assignment are base 2, i.e. log f (n) log2 f (n). Note! Giving an algorithm means: describe the algorithm briefly in words, give high-level pseudocode, justify correctness, and analyze worst case running time.

1. [6 marks] Divide and Conquer/Binary Search. One popular way to rank researchers is by their h-index. A researchers h-index is the maximum integer k such that the researcher has at least k papers that have been cited at least k times each. Suppose a researcher X has written n papers and paper i has been cited ci times. Suppose you have these values sorted in an array C with c1 c2 . . . cn. Give a divide-and-conquer (variation of binary search) algorithm to find researcher Xs h-index. Describe the algorithm briefly in words, give detailed pseudocode, justify correctness, and analyze run-time. Your algorithm should run in time O(log n).

1. [6 marks] Divide and Conquer/Binary Search. One popular way to rank researchers is by their " h-index". A researcher's h-index is the maximum integer k such that the researcher has at least k papers that have been cited at least k times each. Suppose a researcher X has written n papers and paper i has been cited ci times. Suppose you have these values sorted in an array C with c1c2cn. Give a divide-and-conquer (variation of binary search) algorithm to find researcher X's h-index. Describe the algorithm briefly in words, give detailed pseudocode, justify correctness, and analyze run-time. Your algorithm should run in time O(logn)