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
Write a python program that requests a word (with lowercase letters) as input and translates the word into pig latin. The rules
solmaris [256]

Answer:ogbef

Explanation:

3 0
3 years ago
Read 2 more answers
Write a program that prompts the user to enter three words. The program will then sort the words in alphabetical order, and disp
Softa [21]

Answer:

#include <iostream>

#include<bits/stdc++.h>

using namespace std;

bool sorter(string a, string b)

{

   return a<b;

}

int main(){

   string wordList[3];

   string word;

   for (int i = 0; i < 3; i++){

       cout<< "Enter word: ";

       cin>> word;

       wordList[i] = word;

   }

   sort(wordList, wordList+3, sorter);

   for (int i = 0; i < 3; i++){

       cout<< wordList[i]<< "\n";

}

}

Explanation:

The C++ source code prompts the user for string words that are appended to the wordList array. The array is sorted with the sort() function from the C++ bits library. The finally for loop statement prints out the items in the array.

3 0
3 years ago
Can someone help me with python
pishuonlain [190]

Answer:

here

Explanation:

Python is an interpreted high-level general-purpose programming language. Its design philosophy emphasizes code readability with its use of significant indentation.

7 0
2 years ago
Inserting and deleting text is a basic editing task in word processing.<br><br> True or false
Katyanochek1 [597]
The answer should be true
3 0
2 years ago
Read 2 more answers
How to write a program that prompts the user to input two POSITIVE numbers — a dividend (numerator) and a divisor (denominator).
fomenos

Answer:

num1 = int(input("Numerator: "))

num2 = int(input("Denominator: "))

if num1 < 1 or num2<1:

     print("Input must be greater than 1")

else:

     print("Quotient: "+str(num1//num2))

     print("Remainder: "+str(num1%num2))

Explanation

The next two lines prompts the user for two numbers

<em>num1 = int(input("Numerator: "))</em>

<em>num2 = int(input("Denominator: "))</em>

The following if statement checks if one or both of the inputs is not positive

<em>if num1 < 1 or num2<1:</em>

<em>      print("Input must be greater than 1")-> If yes, the print statement is executed</em>

If otherwise, the quotient and remainder is printed

<em>else:</em>

<em>      print("Quotient: "+str(num1//num2))</em>

<em>      print("Remainder: "+str(num1%num2))</em>

<em />

3 0
3 years ago
Other questions:
  • April 107 90 29 31 66 0.344
    8·1 answer
  • )a___ is a complete binary tree such that each node in the tree contains a comparable object that us greater than or equal to th
    9·1 answer
  • How do i unblock website on my school computer
    7·2 answers
  • Which of the following economic systems leaves production decisions completely up to the producers?
    15·2 answers
  • In general, font size for software-generated presentation slides should be no smaller than __________ points.
    8·1 answer
  • Is your florida learners license number the same as the actual license number?
    14·2 answers
  • How to solve a program that accepts a number as input and prints just the decimal portion
    15·2 answers
  • Tornado Alley is located in the middle of the United States, extending from Texas up through the Dakotas. The above statement is
    6·1 answer
  • Please help with this
    8·1 answer
  • Write a Python program to find whether a given number (accept from the user) is positive
    11·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!