Homework Answers
Let the query-time (in seconds) be represented by the formula :
where,
- c is a constant ("hidden" in the big-O notation)
- q is the number of queries run
- n is the input-size
For the first case,
- t1 = 2
- q1 = 5000
- n1 = 106
Thus,
For the second case,
- t2 = to be calculated
- q2 = 3000
- n2 = 108
Thus,
Dividing (2) by (1), we get
Add Answer to:
2) (5 pts) An algorithm answers a query on a database of n elements in O(vn)...
(25pts) You are given two sorted lists of size m and n. Give an O(log m...
(25pts) You are given two sorted lists of size m and n. Give an O(log m log n) time algorithm for computing the k-th smallest element in the union of the two lists Note that the only way you can access these values is through queries to the databases. Ina single query, you can specify a value k to one of the two databases, and the chosen database will return the k-th smallest value that it contains. Since queries are...
(20 points) Recall the following deterministic select algorithm: (a) Divide the n elements into groups of...
(20 points) Recall the following deterministic select algorithm:
(a) Divide the n elements into groups of size 5. So n/5 groups. (b)
Find the median of each group. (c) Find the median x of the n/5
medians by a recursive call to Select. (d) Call Partition with x as
the pivot. (e) Make a recursive call to Select either on the
smaller elements or larger elements (de- pending on the situation);
if the pivot is the answer we are done....
Suppose that an algorithm takes 30 seconds for an input of 224 elements (with some particular,...
Suppose that an algorithm takes 30 seconds for an input of 224 elements (with some particular, but unspecified speed in instructions per second). Estimate how long the same algorithm, running on the same hardware, would take if the input contained 230 elements, and that the algorithm's complexity function is: Big theta not Big O a) Big theta(N) b) Big theta (log N) c) Big theta (N log N) d) Big theta(N^2) Assume that the low-order terms of the complexity functions...
O: Naive algorithm coloring graphs: dild Engineering use the foll?2, is its complexity , vn) be...
O: Naive algorithm coloring graphs: dild Engineering use the foll?2, is its complexity , vn) be colored with k colors? We pseudo-code. What (2 Pts) naïve algorithm in pseu Naive Algorithm: 1. Try all possible ways of assigning k colors to the n verticesTry to color V1, V2, Vn With the colors 1,2,,k. 2. If a valid coloring is found then answer is yes. Otherwise, answer is no. Complexity: O(2)
help in design of algorithm answers with steps for study guide (2 points) Why shouldn't we...
help in design of algorithm
answers with steps for study guide
(2 points) Why shouldn't we measure time efficiency based on the number of seconds or milliseconds it takes the algorithm 1. to run? is the number of times the most important operation of the (2 points) The 2. algorithm occ Ccurs (3 points) Find the binary representation of the following numbers: 3. BINARY REPRESENTATION (in bits) NUMBER 777 14 684,739 4. (8 points) Write the input size metric and...
Suppose that, in a divide-and-conquer algorithm, we always divide an instance of size n of a...
Suppose that, in a divide-and-conquer algorithm, we always
divide an instance of size n of a problem into 5 sub-instances of
size n/3, and the dividing and combining steps take a time
in Θ(n n). Write a recurrence equation for the running time T
(n) , and solve the
equation for T (n)
2. Suppose that, in a divide-and-conquer algorithm, we always divide an instance of size n of a problem into 5 sub-instances of size n/3, and the dividing...
QUESTION 5 A program P takes time proportional to n log n where n is the...
QUESTION 5 A program P takes time proportional to n log n where n is the input size. If the program takes 4 seconds to process input of size 100,000,000, how many microseconds does it take to process input of size 10,000? QUESTION 6 algorithm An example of a graph problem that can be solved in polynomial time is (Hint: Starts with 'D' You're allowed to research this one online if you don't know it.)
True or false for each, and explain why (4 pts) The height of a binary tree is bounded by O(n2), where n is the size...
True or false for each, and explain why
(4 pts) The height of a binary tree is bounded by O(n2), where n is the size of the C. tree. d. (4 pts) dynamic array and O(1) time if L is a linked list. Given a list L of n > 2 elements, the following code takes O(n) time if L is a iterator i = L. iterator () i.next); i.next); i.remove ); binary tree T that has size n and...
Problem 2. (5 pts.) Algorithms A and B perform the same task. On input of size...
Problem 2. (5 pts.) Algorithms A and B perform the same task. On input of size n, algorithm A executes 10 n 2 steps, and algorithm B executes 100,000 steps. Find the value of n above which algorithm B is more efficient. Show your work.
2) In class we showed a Matrix algorithm for Fibonacci numbers: 1 112 1 0 n+1...
2) In class we showed a Matrix algorithm for Fibonacci numbers: 1 112 1 0 n+1 F (Note: No credit for an induction proof that this is true. I'm not asking that.) a) What is the running time for this algorithm? (3 pts.) b) Prove it. (9 pts.)
(25pts) You are given two sorted lists of size m and n. Give an O(log m log n) time algorithm for computing the k-th smallest element in the union of the two lists Note that the only way you can access these values is through queries to the databases. Ina single query, you can specify a value k to one of the two databases, and the chosen database will return the k-th smallest value that it contains. Since queries are...
(20 points) Recall the following deterministic select algorithm:
(a) Divide the n elements into groups of size 5. So n/5 groups. (b)
Find the median of each group. (c) Find the median x of the n/5
medians by a recursive call to Select. (d) Call Partition with x as
the pivot. (e) Make a recursive call to Select either on the
smaller elements or larger elements (de- pending on the situation);
if the pivot is the answer we are done....
O: Naive algorithm coloring graphs: dild Engineering use the foll?2, is its complexity , vn) be colored with k colors? We pseudo-code. What (2 Pts) naïve algorithm in pseu Naive Algorithm: 1. Try all possible ways of assigning k colors to the n verticesTry to color V1, V2, Vn With the colors 1,2,,k. 2. If a valid coloring is found then answer is yes. Otherwise, answer is no. Complexity: O(2)
help in design of algorithm
answers with steps for study guide
(2 points) Why shouldn't we measure time efficiency based on the number of seconds or milliseconds it takes the algorithm 1. to run? is the number of times the most important operation of the (2 points) The 2. algorithm occ Ccurs (3 points) Find the binary representation of the following numbers: 3. BINARY REPRESENTATION (in bits) NUMBER 777 14 684,739 4. (8 points) Write the input size metric and...
Suppose that, in a divide-and-conquer algorithm, we always
divide an instance of size n of a problem into 5 sub-instances of
size n/3, and the dividing and combining steps take a time
in Θ(n n). Write a recurrence equation for the running time T
(n) , and solve the
equation for T (n)
2. Suppose that, in a divide-and-conquer algorithm, we always divide an instance of size n of a problem into 5 sub-instances of size n/3, and the dividing...
QUESTION 5 A program P takes time proportional to n log n where n is the input size. If the program takes 4 seconds to process input of size 100,000,000, how many microseconds does it take to process input of size 10,000? QUESTION 6 algorithm An example of a graph problem that can be solved in polynomial time is (Hint: Starts with 'D' You're allowed to research this one online if you don't know it.)
True or false for each, and explain why
(4 pts) The height of a binary tree is bounded by O(n2), where n is the size of the C. tree. d. (4 pts) dynamic array and O(1) time if L is a linked list. Given a list L of n > 2 elements, the following code takes O(n) time if L is a iterator i = L. iterator () i.next); i.next); i.remove ); binary tree T that has size n and...
2) In class we showed a Matrix algorithm for Fibonacci numbers: 1 112 1 0 n+1 F (Note: No credit for an induction proof that this is true. I'm not asking that.) a) What is the running time for this algorithm? (3 pts.) b) Prove it. (9 pts.)
Most questions answered within 3 hours.
-
A Eucher Deck consists of 24 cards. In a four- player game, each
player is dealt...
asked 48 minutes ago -
This is a challenging question.
The titration of an impure sample of KHP found that 36.00...
asked 56 minutes ago -
1. Starting from rest, an automatic subway train is controlled
by a computer
that causes it’s...
asked 13 minutes ago -
Find and , the mean and standard deviation of the
sampling distribution of :
μ = 25,...
asked 13 minutes ago -
You place a block of
ice (mass of 3 kg) into a test chamber filled with...
asked 1 hour ago -
If a benzene ring has one -CF3 group as a
substituent, will the next substituent add...
asked 37 minutes ago -
CORPORATE FINANCE
STATEMENT: If the total risk of a stock is high you can
expect the...
asked 27 minutes ago -
Which of the following is true?
Select one:
a. The existence of generally accepted accounting principles...
asked 28 minutes ago -
What are the three characteristics of traditional "neighbor
ethics" that Jonas isolates, and in what respects...
asked 30 minutes ago -
According to the manufacturer of a certain candy, 9% of the
candy produced are red. If...
asked 31 minutes ago -
A rectangular block that is 0.6m wide, 0.6m long and 1.2m high
stands on a horizontal...
asked 38 minutes ago -
3. Assume that a mining company that produces ore sells its
product for $40 per ton....
asked 31 minutes ago