# Homework 3 Solution

\$30.00

Category:

## Description

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

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.

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.

1

error: Content is protected !!