![subject](/tpl/images/cats/informatica.png)
Computers and Technology, 22.02.2021 19:50 naocarolina6
You are given a set S = {s1,s2,...,sn} of n distinct natural numbers such that 0 ≤ si ≤ 100n. Your task is to design an algorithm that takes as input S and a natural number N, and outputs True if the equation si + sj + sk = N has at least one solution, and return False otherwise. There is a simple solution that runs in O(n3) time, but I hope you improve that time using FFT.
Example: For N = 6 and S = {1,2,3,5,10} your design should output True since 1+2+3 = 6. For N = 20 and the same set S the answer should be True again since 5+5+10 = 20 (yes, you can have si = sj = sk!) but for N = 19 the answer is False since no three numbers add up to 19.
You can use FFT as a black box. Explicitly write the polynomials you will use as input for FFT and explain how you use the output to answer your problem. State and justify the running time of your algorithm.
![ansver](/tpl/images/cats/User.png)
Answers: 1
![](/tpl/images/ask_question.png)
![](/tpl/images/ask_question_mob.png)
Other questions on the subject: Computers and Technology
![image](/tpl/images/cats/informatica.png)
![image](/tpl/images/cats/informatica.png)
Computers and Technology, 23.06.2019 10:20, chonawilson4
Suppose there is a relation r(a, b, c) with a b+-tree index with search keys (a, b).1. what is the worst-case cost of finding records satisfying 10 < a < 50 using this index, in terms of the number of records n1, retrieved and the height h of the tree? 2. what is the worst-case cost of finding records satisfying 10 < a < 50 and 5 < b < 10 using this index, in terms of the number of records n2 that satisfy this selection, as well as n1 and h defined above? 3. under what conditions on n1 and n2, would the index be an efficient way of finding records satisfying the condition from part (2)?
Answers: 1
![image](/tpl/images/cats/informatica.png)
Computers and Technology, 24.06.2019 01:00, bellamyciana
What are two ways to access the options for scaling and page orientation? click the home tab, then click alignment, or click the file tab. click the file tab, then click print, or click the page layout tab. click the page layout tab, or click the review tab. click the review tab, or click the home tab?
Answers: 2
![image](/tpl/images/cats/informatica.png)
Computers and Technology, 24.06.2019 04:10, kris1920
Write a program that reads a set of floating-point values. ask the user to enter the values, then print • the average of the values. • the smallest of the values. • the largest of the values. • the range, that is the difference between the smallest and largest. of course, you may only prompt for the values once.
Answers: 3
You know the right answer?
You are given a set S = {s1,s2,...,sn} of n distinct natural numbers such that 0 ≤ si ≤ 100n. Yo...
Questions in other subjects:
![Konu](/tpl/images/cats/istoriya.png)
History, 31.03.2020 06:28
![Konu](/tpl/images/cats/mat.png)
![Konu](/tpl/images/cats/mat.png)
Mathematics, 31.03.2020 06:28
![Konu](/tpl/images/cats/mat.png)
![Konu](/tpl/images/cats/mat.png)
![Konu](/tpl/images/cats/mat.png)
Mathematics, 31.03.2020 06:29
![Konu](/tpl/images/cats/mat.png)
![Konu](/tpl/images/cats/informatica.png)
Computers and Technology, 31.03.2020 06:29
![Konu](/tpl/images/cats/mat.png)
Mathematics, 31.03.2020 06:43
![Konu](/tpl/images/cats/pravo.png)
Law, 31.03.2020 06:43