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 = 2k, 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 = 2d 1 for some d. Each node v of T is labeled with a real number xv. 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 xv is less than the label xw 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 xv 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
