Homework 3 Solution




  1. 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.






  1. 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




lower   A[k]       upper:






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.







  1. 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.







  1. 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.








error: Content is protected !!