## Description

- Assume that all elements of A[1::n] are distinct and sorted, and x is in A. Each element of

A is equally likely to be in any position in the array. Please give the average case analysis of Algorithm BinarySearch (n = 2^{k}, k 2 N). The exact expression for the average number of comparisons T (n) is required.

- Given an integer array A[1::n] and two integers lower upper, design an algorithm using

divide-and-conquer method to count the number of ranges (i; j) (1 i j n) satisfying

j

X

lower A[k] upper:

k=i

Example:

Given A = [1; 1; 2], lower = 1, upper = 2, return 4.

The resulting four ranges are (1; 1), (3; 3), (2; 3) and (1; 3).

- Complete the implementation using pseudo code.

- Write a recurrence for the running time of the algorithm.

- Consider an n-node complete binary tree T, where n = 2
^{d}1 for some d. Each node v of T is labeled with a real number x_{v}. You may assume that the real numbers labeling the nodes are all distinct. A node v of T is a local minimum if the label x_{v}is less than the label x_{w}for all nodes w that are joined to v by an edge.

You are given such a complete binary tree T, but the labeling is only speci ed in the following implicit way: for each node v, you can determine the value x_{v} by probing the node v. Show how to nd a local minimum of T using only O(log n) probes to the nodes of T.

- We’ve mentioned fast matrix multiplication theory, Principal components and Singular Value Decomposition in the class(05DivideAndConquerII.pdf, page 16-25). Now survey and read the corresponding paper about DNN weight matrix approximation and acceleration(e.g. low-rank factorization). Is there any other method to accomplish the same goal. Describe your thinking and ideas. Write an essay about one page.

1