1answer.
Ask question
Login Signup
Ask question
All categories
  • English
  • Mathematics
  • Social Studies
  • Business
  • History
  • Health
  • Geography
  • Biology
  • Physics
  • Chemistry
  • Computers and Technology
  • Arts
  • World Languages
  • Spanish
  • French
  • German
  • Advanced Placement (AP)
  • SAT
  • Medicine
  • Law
  • Engineering
NARA [144]
3 years ago
9

Suppose you wish to develop a matrix-multiplication algorithm that is asymptotically faster than Strassen’s algorithm. Your algo

rithm will use divide-and-conquer, dividing each matrix into pieces of size n/8 × n/8, and the divide and combine steps together will take Θ(n2) time. You need to determine how many subproblems your algorithm has to create in order to beat Strassen’s algorithm. If your algorithm creates a subproblems, what is the largest integer value of a for which your algorithm would be asymptotically faster than Strassen’s algorithm?
Computers and Technology
1 answer:
Kazeer [188]3 years ago
5 0

Answer:

The number of subproblems are given as T(n)=a*T(n/8)+\theta(n^2) while the value of T(n) to be less than S(n) is for 342.

Explanation:

The number of subproblems are given as

T(n)=a*T(n/8)+\theta(n^2)

Asymptotic running time for Strassen’s algorithm is S(n)=\theta(n^{log(7)})

Now, when a increases, number of subproblems determines the asymptotic running time of the problem and case 1 of master theorem applies. So, in worst case, asymptotic running time of the algorithm will be

T(n)=\theta(n^{logb(a)})=\theta(n^{log8(a)})=\theta(n^{log_{2}(a^{1/3})})

Now, for T(n) to be smaller than S(n)

n^{loga^{1/3}}

So,

log(a^{(1/3)})

So,

a=342

You might be interested in
Suppose that the following elements are added in the specified order to an empty binary search tree: Kirk, Spock, Scotty, McCoy,
patriot [66]

Answer:

Pre-order: Kirk, Chekov, Khaaaan, Spock, Scotty, McCoy, Sulu, Uhuru

In-order: Chekov, Khaaaan, Kirk, McCoy, Scotty, Spock, Sulu, Uhuru

Post-order: Khaaaan, Chekov, McCoy, Scotty, Sulu, Uhuru, Spock, Kirk

Explanation:

The binary search tree is described in the diagram below.

The pre-order traversal of the binary tree gets the root, then the left node and right node. The in-order traversal picks the left node, the root node, and then the right node while the post-order traversal of the binary tree follows the left node, right node, and then the root node.

6 0
3 years ago
Which of the following are examples of software? (Select all that apply)
olchik [2.2K]
Put a photo or something
8 0
2 years ago
Read 2 more answers
When you save a Notepad file for the first time, you must also A. print a copy for your records. B. give it a name. C. check the
Kruka [31]
Answer: Give it a name
3 0
3 years ago
Why would you use a custom filter?
Angelina_Jolie [31]

Answer:By specifying conditions, you can create custom filters that narrow down the data in the exact way that you want. You do this by building a filter. If you've ever queried data in a database, this will look familiar to you. Point to either Number Filters or Text Filters in the list.

Explanation:

5 0
3 years ago
Given a floating-point formal with a k-bit exponent and an n-bit (fraction, write formulas for the exponent E, significant M, th
ANEK [815]

Answer:

A) Describe the number 7.0 bit

The exponential value ( E ) = 2

while the significand value ( M ) = 1.112  ≈ 7/4

fractional value ( F )  = 0.112

And, numeric value of the quantity ( V )  = 7

The exponent bits will be represented  as :  100----01.

while The fraction bits will be represented  as : 1100---0.

<u>B) The largest odd integer that can be represented exactly </u>

The integer will have its exponential value ( E ) = n

hence the significand value ( M )

=  1.11------12 = 2 - 2-n

also the fractional value ( F ) =  

0.11------12 = 1 – 2-n

Also, Value, V = 2n+1 – 1

The exponent bits  will be represented  as follows:  n + 2k-1 – 1.

while The bit representation for the fraction will be as follows: 11---11.

<u>C) The reciprocal of the smallest positive normalized value </u>

The numerical value of the equity ( V ) = 22k-1-2

The exponential value ( E )  = 2k-1 – 2

While the significand value ( M )  = 1

also the fractional value ( F ) = 0

Hence The bit representation of the exponent will be represented as : 11---------101.

while The bit representation of the fraction will be represented as : 00-----00.

Explanation:

E = integer value of exponent

M = significand value

F = fractional value

V = numeric value of quantity

A) Describe the number 7.0 bit

The exponential value ( E ) = 2

while the significand value ( M ) = 1.112  ≈ 7/4

fractional value ( F )  = 0.112

And, numeric value of the quantity ( V )  = 7

The exponent bits will be represented  as :  100----01.

while The fraction bits will be represented  as : 1100---0.

<u>B) The largest odd integer that can be represented exactly </u>

The integer will have its exponential value ( E ) = n

hence the significand value ( M )

=  1.11------12 = 2 - 2-n

also the fractional value ( F ) =  

0.11------12 = 1 – 2-n

Also, Value, V = 2n+1 – 1

The exponent bits  will be represented  as follows:  n + 2k-1 – 1.

while The bit representation for the fraction will be as follows: 11---11.

<u>C) The reciprocal of the smallest positive normalized value </u>

The numerical value of the equity ( V ) = 22k-1-2

The exponential value ( E )  = 2k-1 – 2

While the significand value ( M )  = 1

also the fractional value ( F ) = 0

Hence The bit representation of the exponent will be represented as : 11---------101.

while The bit representation of the fraction will be represented as : 00-----00.

8 0
3 years ago
Other questions:
  • In the u.s.all financial institutions are required to conduct business at a physical location only
    9·1 answer
  • WHAT IS SQL AND HOW CAN YOU MEET THE DATA REQUIREMENTS ALSO MAINTAINING DATA INTEGRITY,AND LASTLY STATE THE FULL MEANING OF SQL
    11·1 answer
  • You can use the_______key if your cursor is at the end of the word. Use the______key if you place the cursor on the left side of
    11·1 answer
  • what evidence supports the claims that the Taj Mahal is a symbol of historical and cultural glory as well as an architectural ma
    8·1 answer
  • .A menu within a menu is called what? (nested menu ,submenu ,recursive menu ,formal list )
    12·1 answer
  • Will give brainliest!!<br> (Question 3)
    12·2 answers
  • What did do you do if you made a mistake on a computer?
    14·2 answers
  • Bruh my sister does bot understand what this means
    6·1 answer
  • You’re configuring a Web-based intranet application on the WebApp server, which is a domain member. Users authenticate to the We
    13·1 answer
  • Which of the following is a career that's indirectly linked to careers in web technologies?
    10·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!