Ask Question, Ask an Expert

+1-415-315-9853

info@mywordsolution.com

Ask Math Expert


Home >> Math

Q1) This problem is about determining when Strassen's Algorithm is faster than ordinary matrix multiplication, assuming that scalar addition and scalar multiplication take the same amount of time. Show all of your workings. Don't use the Master Method in this problem.

(i) describe why ordinary matrix multiplication of two n by n matrices involves 2n3-n2 calculations. (Multiplication+Addition).

(ii) In Strassen's Algorithm, T(n), the total number of calculations (Multiplication+Addition) involved in multiplying two n by n matrices satisfies T(n) = 7T(n/2 ) + 9/2n2 given T(1) = 1. Suppose n = 2m. By considering the transformation G(m) = T(2m) obtain a recursion equation for G(m) along with a condition on G(0).

(iii) Show that the solution to the recursion equation is G(m) = 7m+1- 6 *4m.

(iv) Hence show that T(n) = 7nlog27 -6n2.

(v) Determine the smallest value of m for which Strassen's Algorithm involves fewer calculations than ordinary matrix multiplication.

Q2) In this problem you will need to determine which of the 5 algorithms V to Z is quickest at solving a problem of input size n. The running time for each algorithm satisfies its own recursion equation given by:
Algorithm V: V (n) = 3V (n-1) + 4n with V (1) = 1
Algorithm W: W(n) = 3W(n-1) + 10n2 + 20n + 40 with W(1) = 1
Algorithm X: X(n) = 3X(n -1) + 3n with X(1) = 1
Algorithm Y: Y (n) = 5Y (n - 1) - 4Y (n- 2) + 6n - 12 with Y (1) = 1; Y (2) = 2
Algorithm Z: Z(n) = 8Z(n - 1) - 15Z(n - 2) + 2n with Z(1) = 1; Z(2) = 2

(i) Obtain a closed form solution for the running time for each algorithm.
(These should be derived by hand without using Maple).

(ii) Use Maple to plot a suitable function of the running time against n for each algorithm on the same graph to illustrate how the choice of the most efficient algorithm changes with n. (Plotting multiple graphs may help to illustrate your argument).

(iii) By considering the running time for algorithm Z, simplify this expression 5n - 5(3n) + 2n+3 mod 6 for n   1
(Just state the answer and say why - no need to prove anything)

Q3) The running times of algorithms J, K, L and M are given by

Algorithm J: J(n) = 3J(n/4 ) + n with J(1) = 1

Algorithm K: K(n) = 5K(n/2 ) + n2 with K(1) = 1

Algorithm L: L(n) = 6L(n/6 ) + n ln n with L(3) = 1

Algorithm M: M(n) = 2M(n/5 ) +M(n/3 ) + √n with M(1) = 1

(i) describe how algorithms K & M divide up a problem of size n.
(ii) Sketch a recursion tree for algorithm J.
(iii) Using the Master Method, determine the asymptotic running times for each of the algorithms J, K & L.
(iv) Prove the 3 results that you obtained in (iii) are upper bounds on the running times of algorithms J, K & L, using proof by induction.
(v) Consider algorithm M and suppose p > 0.5 such that M(n) = O(np).
(a) By seeking the tightest possible upper bound on M determine p.
(b) Using proof by induction show that M(n) <=cnp + d √n where c and d are chosen to make this upper bound as tight as possible.
(vi) Which of the algorithms J, K, L and M is asymptotically fastest?

Q4) This problem is about solving nonlinear equations. You should ignore repeated roots. You cannot use any of Maple's built in `solve' type commands.

(i) prepare a Maple procedure to numerically solve the coupled system of equations f(x; y) = 0 and g(x; y) = 0 with initial guesses x=x0 and y=y0 by extending the Newton-Raphson method to a system of 2 nonlinear equations.
(Use  nite di erences to evaluate the partial derivatives).

(ii) Using an initial guess of x0 = 1 and y0 = -1 test your procedure by obtaining one
solution, accurate to 5 decimal places, to this nonlinear system:
sin(5x) + 9- 3y2 = 0
e7y-4x + 6x- 8 = 0

Q5) In this problem you are going to prepare a Maple program to determine the centre and radius of the smallest circle that encloses a set of points.
(i) Create a set A of 20 points located in a two dimensional space. The x and y coordinates of each point should be randomly assigned such that |x| <=100 and |y| <=100.

(ii) Determine the maximum and minimum values of x and y over the points in A. Define x0 = 1/2(max(x) - min(x)) and y0 = 1/2(max(y)- min(y)).
(iii) find out the radius, r0, of a circle centred at the point (x0; y0) that encloses the set of points in A. Define dx = 1/10r0.

(iv) Redefine dx as dx=1:1. By considering the resulting radius for each of the points (x0- dx; y0), (x0, y0), (x0 + dx, y0), (x0, y0- dx) and (x0, y0 + dx) choose a new value of x0 and y0 to reduce the radius.
(If none of the four new points reduces the radius, then leave x0 and y0 unchanged.)

(v) Iterate step (iv) 30 times.

(vi) Plot the points in set A along with a circle centred at the point (x0, y0) of the appropriate radius on the same graph.

(vii) Discuss any problems associated with successively reducing the value of dx.

Math, Academics

  • Category:- Math
  • Reference No.:- M9897

Have any Question? 


Related Questions in Math

Let s d isin f be a bargaining game denote by x2nbsp gx1

Let (S, d) ∈ F be a bargaining game. Denote by x 2  = g(x 1 ) the equation defining the north-east boundary of S. Prove that if g is strictly concave and twice differentiable, then the point x∗ = N (S, d) is the only eff ...

Suppose we have a cyclic data-dependence graph with nodes a

Suppose we have a cyclic data-dependence graph with nodes a, b, c, and d. There are edges from a to b and from c to d with label h0; 1i and there are edges from b to c and from d to a with label h1; 1i. There are no othe ...

Let sc be a bargaining game and let td be the image of sc

Let (S,c) be a bargaining game, and let (T,d) be the image of (S,c) under the positive affine transformation x #→ ax + b on R2; that is, T = aS + b and d = ac + b. Prove that the set argmaxy∈T (y 1  - d 1 )(y 2  - d 2 ) ...

1 show that when you apply node splitting to a nonreducible

1. Show that when you apply node splitting to a nonreducible ow graph, and then perform T1-T2 reduction on the resulting split graph, you wind up with strictly fewer nodes than you started with. 2. What happens if you ap ...

Customers shopping at a particular supermarket spend a mean

Customers shopping at a particular supermarket spend a mean time shopping of 47 minutes,with a standard deviation of 11 minutes. Assuming a normal distribution, what is the probability that a randomly chosen customer wil ...

Part 1 discussion topic supply issues in health care

PART 1. Discussion Topic : Supply Issues in Health Care:   -Discussion responses should be at least 150 words, APA and cite appropriate reference. The special interest group theory states that the political venue can be ...

In 2013 devon and mandy were married and filling their

In 2013, Devon and Mandy were married and filling their taxes jointly. They had no dependent children and were claiming the standard deduction. Calculate their federal income tax for 2013 knowing that their adjusted gros ...

Amanda is selling an antique dining room furniture set

Amanda is selling an antique dining room furniture set through a broker. She wants to get $1200 for herself, but the broker gets 15% of the selling price as commission. What should the selling price be? A. $1380.00 B. $1 ...

A city currently has 128 street lights as part of a urban

A city currently has 128 street lights. As part of a urban renewal program, the city council has decided to install 2 additional street lights at the end of each week for the next 52 weeks. How many street lights will th ...

George mcginnis a marketer for wingate paper is jogging

George McGinnis, a marketer for Wingate Paper, is jogging with Tom Cagle. Tom is a long-time distributor for Wingate Paper and has a good relationship with the company and its owners. George asks Tom about the status of ...

  • 4,153,160 Questions Asked
  • 13,132 Experts
  • 2,558,936 Questions Answered

Ask Experts for help!!

Looking for Assignment Help?

Start excelling in your Courses, Get help with Assignment

Write us your full requirement for evaluation and you will receive response within 20 minutes turnaround time.

Ask Now Help with Problems, Get a Best Answer

WalMart Identification of theory and critical discussion

Drawing on the prescribed text and/or relevant academic literature, produce a paper which discusses the nature of group

Section onea in an atwood machine suppose two objects of

SECTION ONE (a) In an Atwood Machine, suppose two objects of unequal mass are hung vertically over a frictionless

Part 1you work in hr for a company that operates a factory

Part 1: You work in HR for a company that operates a factory manufacturing fiberglass. There are several hundred empl

Details on advanced accounting paperthis paper is intended

DETAILS ON ADVANCED ACCOUNTING PAPER This paper is intended for students to apply the theoretical knowledge around ac

Create a provider database and related reports and queries

Create a provider database and related reports and queries to capture contact information for potential PC component pro