What is the recurrence relation used in Strassen’s algorithm?(a) 7T(n/2) + Theta(n^2)(b) 8T(n/2) + Theta(n^2)(c) 7T(n/2) + O(n^2)(d) 8T(n/2) + O(n^2)This question was addressed to me during an interview for a job.My enquiry is from Number Theory in division Number Theory of Data Structures & Algorithms II

What is the recurrence relation used in Strassen’s algorithm?(a) 7T(

1.	What is the recurrence relation used in Strassen’s algorithm?(a) 7T(n/2) + Theta(n^2)(b) 8T(n/2) + Theta(n^2)(c) 7T(n/2) + O(n^2)(d) 8T(n/2) + O(n^2)This question was addressed to me during an interview for a job.My enquiry is from Number Theory in division Number Theory of Data Structures & Algorithms II
Answer» Right choice is (a) 7T(n/2) + Theta(n^2) To explain: The recurrence RELATION used in STRASSEN’s algorithm is 7T(n/2) + Theta(n^2) since there are only 7 recursive MULTIPLICATIONS and Theta(n^2) scalar additions and subtractions involved for computing the product.

Discussion

No Comment Found

Related InterviewSolutions

Let A={1,2,3} B={2,3,4} C={1,3,5} D={2,3}. Find the cardinality of sum of all the sets.(a) 6(b) 5(c) 4(d) 7This question was posed to me by my school teacher while I was bunking the class.The origin of the question is Number Theory topic in portion Number Theory of Data Structures & Algorithms II
____________ is an arithmetic function that calculates the total number of positive integers less than or equal to some number n, that are relatively prime to n.(a) Euler’s phi function(b) Euler’s omega function(c) Cauchy’s totient function(d) Legrange’s functionI had been asked this question during an internship interview.The above asked question is from Number Theory topic in section Number Theory of Data Structures & Algorithms II
Using the inclusion-exclusion principle, find the number of integers from a set of 1-100 that are not divisible by 2, 3 and 5.(a) 22(b) 25(c) 26(d) 33I got this question in unit test.My question is taken from Number Theory in portion Number Theory of Data Structures & Algorithms II
Counting intersections can be done using the inclusion-exclusion principle only if it is combined with De Morgan’s laws of complementing.(a) true(b) falseThis question was posed to me in an online interview.The origin of the question is Number Theory topic in chapter Number Theory of Data Structures & Algorithms II
Which of the following statement is incorrect with respect to generalizing the solution using the inclusion-exclusion principle?(a) including cardinalities of sets(b) excluding cardinalities of pairwise intersections(c) excluding cardinalities of triple-wise intersections(d) excluding cardinalities of quadraple-wise intersectionsThe question was asked in an internship interview.This interesting question is from Number Theory in chapter Number Theory of Data Structures & Algorithms II
With reference to the given Venn diagram, what is the formula for computing |AUBUC| (where |x, y| represents intersection of sets x and y)?(a) |A U B U C|=|A|+|B|+|C|-|A,B|-|A,C|-|B,C|+|A, B,C|(b) |A, B,C|=|A|+|B|+|C|-|A U B|-|A U C|-|B U C|+|A U B U C|(c) |A, B,C|=|A|+|B|+|C|+|A,B|-|A,C|+|B,C|+|A U B U C|(d) |A U B U C|=|A|+|B|+|C| + |A,B| + |A,C| + |B,C|+|A, B,C|I have been asked this question at a job interview.Query is from Number Theory in section Number Theory of Data Structures & Algorithms II
According to inclusion-exclusion principle, a n-tuple wise intersection is included if n is even.(a) True(b) FalseThe question was asked in an interview.My doubt is from Number Theory in chapter Number Theory of Data Structures & Algorithms II
Who invented the concept of inclusion-exclusion principle?(a) Abraham de Moivre(b) Daniel Silva(c) J.J. Sylvester(d) SieveThis question was posed to me in my homework.This question is from Number Theory topic in portion Number Theory of Data Structures & Algorithms II
Which of the following is not an application of inclusion-exclusion principle?(a) Counting intersections(b) Graph coloring(c) Matching of bipartite graphs(d) Maximum flow problemI have been asked this question by my college director while I was bunking the class.This intriguing question originated from Number Theory in portion Number Theory of Data Structures & Algorithms II
____________ is one of the most useful principles of enumeration in combinationatorics and discrete probability.(a) Inclusion-exclusion principle(b) Quick search algorithm(c) Euclid’s algorithm(d) Set theoryThe question was asked in an interview for job.The above asked question is from Number Theory topic in division Number Theory of Data Structures & Algorithms II

Discussion

No Comment Found

Related InterviewSolutions

Reply to Comment