Question 1Consider the following segment of an algorithm:i = 1Loop while (i Question 4Given the recurrence relations T(n) = ₁complexity in big-theta?A. 0(√n log10 √n)B. 0(n² log₂ n)C. 0(√n log₂n)D. (n¹og₂n)E. (n log₂ √n)Question 5Consider a Queue ADT with the following standard operations: create Queue () andenqueue (Queue Q, int x), and a Stack ADT with the similar standard operations: createStack(),pushStack (Stack s, int n), and popStack (Stack S, int x) have been created. With the followingalgorithm and data file:) = √2T (²) + √ñ and T(1)=1, what is the run-timeAlgorithm: DoSomething (String filename)Q1 = createQueue ()S1 = createStack()Open filenameloop (not end of file)read numberif (number not 0)elsepushStack (S1, number)popStack (S1, x)popStack (S1, x)loop (not empty S1)popStack (S1, x)enqueu (Q1, x)end loopend ifend loopThe data are 8, 30, 53, 14, 0, 66, 38, 19, 45, 29, 39, 7, 0, 29, 29, 8, 39, 18, 0What would be the contents of queue Q1 after the above-describe code is executedwith the associated data file input to the algorithm?A. 53, 30, 8, 39, 29, 45, 19, 38, 66, 39, 8, 29, 29B. 30, 8, 29, 45, 19, 38, 66, 8, 29, 29C. 53, 14, 19, 45, 29, 39, 7, 8, 39, 18D. 8, 30, 33, 38, 19, 45, 29, 29, 8E. 8, 30, 66, 38, 19, 45, 29, 29, 29,8

As per Bartleby Experts guidelines, the first three questions are answered for you. To get the…

Question 1 Consider the following segment of an algorithm: i = 1 Loop while (i < n) print("Hello World!") i - i * 3 Which one of the following options about the runtime R(n) is true? A. R(n) = 0(n³) B. R(n) = 0(log³n) C. R(n)= 0(3") D. R(n)= 0(log3 n) E. R(n) = 0(³√n) Question 2 Which of the following is NOT true? A. n2 € 0(n3) E B. log(n!) € O(n) C. log(n!) E (logn) D. 4¹ € 0(2) E. n² € (nlgn) Question 3 Suppose T is a binary search tree storing n entries. Which one of the following statements is true? A. Inserting into T is 0(1) in the best case and 0(log n) in the worst case. B. Inserting into T is 0(1) in the best case and 0(n) in the worst case. C. Inserting into T is 0(log n) in the best case and 0(log n) in the worst case. D. Inserting into T is 0(log n) in the best case and 0(n) in the worst case. E. Inserting into T is O(n) in the best case and 0(n) in the worst case.

Question 1 Consider the following segment of an algorithm: i = 1 Loop while (i < n) print("Hello World!") i - i * 3 Which one of the following options about the runtime R(n) is true? A. R(n) = 0(n³) B. R(n) = 0(log³n) C. R(n)= 0(3") D. R(n)= 0(log3 n) E. R(n) = 0(³√n) Question 2 Which of the following is NOT true? A. n2 € 0(n3) E B. log(n!) € O(n) C. log(n!) E (logn) D. 4¹ € 0(2) E. n² € (nlgn) Question 3 Suppose T is a binary search tree storing n entries. Which one of the following statements is true? A. Inserting into T is 0(1) in the best case and 0(log n) in the worst case. B. Inserting into T is 0(1) in the best case and 0(n) in the worst case. C. Inserting into T is 0(log n) in the best case and 0(log n) in the worst case. D. Inserting into T is 0(log n) in the best case and 0(n) in the worst case. E. Inserting into T is O(n) in the best case and 0(n) in the worst case.

C++ Programming: From Problem Analysis to Program Design

8th Edition

ISBN:9781337102087

Author:D. S. Malik

Publisher:D. S. Malik

Chapter15: Recursion

Section: Chapter Questions

Problem 18PE

See similar textbooks

Similar questions

Algorithm problem w/ recurrence: Frying pancakes: a small pan can only hold two pancakes at a time. Each pancake needs to be fried on both sides. Frying one side takes 1 minute, no matter how many pancakes are on the pan. Consider this recursive algorithm: If n <= 2, fry the pancakes or the two pancakes together on each side. If n > 2, fry any two pancakes together on each side and then apply the same process recursively to the remaining n-2 pancakes. a. Set up and solve the recurrence for the amount of time this algorithm needs to fry n pancakes. b. Explain why this algorithm does not fry the pancakes in the minimum time for all n > 0. c. Give a correct recursive algorithm that executes the task in the minimum amount of time. > I was not sure how to start this. I have had trouble with recurrence in the past. Also from the work that I did do, I didn't know how there could be a better algorithm. Thanks in advance
Determine how many times the innermost loop will be iterated when the following algorithm segment is implemented and run. (Assume that m, n, and p are positive integers.) for i:=1 to m for j :=1 to n for k = 1 to p [Statements in body of inner loop. None contain branching statements that lead outside the loop.] next k next j next i
Recursive algorithm always gives cleaner code with less cost. Group of answer choices True False
I want the algorithm for this question
Force Completion This test can be saved and resumed at any point until time has expired. The timer will continue to run if you leave the te Your answers are saved automatically. >Show Timer * Question Completion Status: QUESTION 1 Experience has shown that the best way to construct a program is from small pieces. This is called O bottom up O the whole is greater than the sum of the parts O divide and conquer O recursion approach. Click Save and Submit to save and submit. Click Save All Answers to save all answers. 25
Solve 8 Puzzle problems using A* algorithm. Write the complexity of the algorithm.
1. A certain computer algorithm executes four times as many operations when it is run with an input of size n as when it is run with an input of size n – 1. Here, n > 1 is an integer. When the algorithm is run with an input of size 1, it executes 12 operations. How many operations does the algorithm execute when it is run with an input of size 5? How many operations does the algorithm execute when it is run with an input of size n?
Recursion is an approach in which the solution to a particular problem depends on solutions to same size instances of the same problem. Select one: O True O False
Design a top-down algorithm (based on dynamic programming and recursion; i.e. memory function) for checking the existence of a winning strategy for the “Rocks” game. Hints: • Give it the name: RocksMF(n,m) where n,m are the number of rocks on the two piles • Use recursion to call the algorithm itself to solve smaller subproblems • Use a global variable for the two-dimensional table
Question 4 - Algorithm Design Imagine you are a treasure hunter standing at one side of the river. There are n (a positive integer) stones on the river. They are aligned on a straight line and at the nth stone, there is treasure waiting for you. Your target is to reach the nth stone. For each move, you have the choice of either walking (move one stone ahead) or leaping (move two stones ahead). Also, you are not allowed to travel backwards. Design an algorithm that calculates the number of ways (sequences of walks/leaps) that get you to the treasure stone. You should clearly explain the algorithm and demonstrate the correctness of the algorithm with a complete proof. Here is an example. For n = 1 5, there are 8 ways: Method 1: walk → walk → walk → walk → walk Method 2: walk → walk → walk → leap Method 3: walk → walk → leap → walk Method 4: walk → leap → walk → walk walk Method 5: leap → walk → walk → Method 6: leap → leap walk Method 7: leap → walk → leap Method 8: walk → leap leap
MazeSolver attempts to recursively traverse a Maze. The goal is to get from the * given starting position to the bottom right, following a path of 1’s. Arbitrary * constants are used to represent locations in the maze that have been TRIED * and that are part of the solution PATH.
ANALYSIS & DESIGN OF ALGORITHMS subject Three points P, Q, and R are said to be collinear if they are on a single line. To check whether the 3 points lie on the same line, we use the distance formula. If P, Q and R are three collinear points, then: Distance from P to Q + Distance from Q to R = Distance from P to R PQ + QR = PR The distance between two points (x1, y1) and (x2, y2) is given by Hence, we can easily find the distance between the points P, Q and R, with the help of this formula. Design an algorithm (pseudocode) to check whether three points are collinear. In your solution include the input and the output.