Explanation of Solution
The following
Pseudocode:
Input: Two integer arrays “a[]” and “b[]” of size “n”.
Size of Input: The size specifies the number “n” of array entries.
Output: The condition is “true” of each element of “a[]” is also an element of “b[]” otherwise, it display “false”.
The following is the pseudocode for given data,
Boolean Contains =true
int i=0
While Contains && i<n do
Contains=Linearsearch(a[i],b)
i++;
End while
Print Contains
Explanation:
- In the given code, set the Boolean variable “Contains” is equal to “true”.
- Execute the while loop if the condition is true,
- The condition must be “i” less than “n” and the variable “Contains” must be “true”.
- If it is true, then it calls for Linearsearch() function.
- Increment the value of “i”.
- Thus, the while loop is executed until the condition satisfies and then finally it print the Boolean value either “True” or “False”.
Pseudocode for LinearSearch:
Input: An integer “X” and an array “b[]” of size “n”.
Size of input: The size specifies the number “n” of array entries.
Output: It returns true if “X” contains in “b[]”, otherwise “false”.
The following is the pseudocode for linear search,
Boolean LinSearch(int x, int[] b)
Begin
int k=0;
Boolean found =false;
While !found && k<n do
if(X==b[k])
found =true;
else
K++
End If
End While
Return found
End LinSearch
Explanation:
- The given code performs the linear search algorithm concept which process to find an item in an array...
Want to see the full answer?
Check out a sample textbook solutionChapter 16 Solutions
Starting Out with Java: From Control Structures through Data Structures (4th Edition) (What's New in Computer Science)
- How can i find the number of paths possible for 0 toN stairs when the user may jumps 1 ,2 & 3 stairs at a time. Take the n from the user. Please solve this in linear time in Java programming language.arrow_forwardImagine that you have a problem P that you know is N P-complete. For this problem you have two algorithms to solve it. For each algorithm, some problem instances of P run in polynomial time and others run in exponential time (there are lots of heuristic-based algorithms for real N P-complete problems with this behavior). You can’t tell beforehand for any given problem instance whether it will run in polynomial or exponential time on either algorithm. However, you do know that for every problem instance, at least one of the two algorithms will solve it in polynomial time. (a) What should you do? (b) What is the running time of your solution? 564 Chap. 17 Limits to Computation (c) What does it say about the question of P = N P if the conditions described in this problem existed?arrow_forwardI needed the algorithm for G whose length is even. You can read it in the last line of the question. I don't know where the divisible by 5 part came from. Please solve the question again.arrow_forward
- Consider the problem of counting, in a given text, the number of substrings that start with an A and end with a B. For example, there are four such substrings in CABAAXBYA.a. Design a brute-force algorithm for this problem and determine its efficiency class.b. Design a more efficient algorithm for this problem with complexity O (n)arrow_forwardUsing an array (python), you have to get the first and last object and place them at the end of the list. For example, QWERTY will be WERTQY. What is the worst case time complexity? Show the equation and Big-O notation.arrow_forwardUsing an array (python), you have to get the first and last object and place them at the end of the list. For example, 12345 will be 23415. What is the worst case time complexity? Show the equation and Big-O notation.arrow_forward
- The Knapsack Problem is a famous computer science problem that is defined as follows: imagine you are carrying a knapsack with capacity to hold a total of weight C. You are selecting among n items with values A={a_1, a_2, ... , a_n} and associated weights W={w_1, w_2, ... , w_n}. Here the weights and values are all positive (but not necessarily unique). You wish to maximize the total value of the items you select not exceeding the given weight capacity, i.e. maximize sum_{a in A} such that sum_{w in W} <= C. Please note that you can only select your items once. a) We can reformulate this as a 2D bottom-up dynamic programming problem as follows. Define T_{i,j} as the highest possible value sum considering items 1 through i and total weight capacity j (j <= C). What is the base case i.e. T_{0,j} for all j and T_{i,0} for all i?, and What is the loop statement?arrow_forwardYou are the TA for the FCP course in environment engineering. You are given the midsem and endsem marks for the N Students in the course. A student P is said to dominate a student Q, if the midsem and endsem marks of P are both greater than the respective midsem and endsem marks of Q. Design an efficient algorithm for finding all the students that are not dominated by any other student in the class. Analyse the time complexity as wellarrow_forwardI need help with this pleasearrow_forward
- We have two input arrays, an array A with n elements, and an array B with m elements, where m > n. There may be duplicate elements. We want to decide if every element of B is an element of A. a. Describe a brute-force algorithm. What is the worst-case time complexity? b. Describe an algorithm to solve this problem in O(m log n) worst case time. (Hint: You may apply instance simplification.)arrow_forwardWrite an algorithm called MatrixRowMultiple(A[0…n – 1, 0… n – 1]) which takes an n x n matrix A and outputs if true, if each element in the first row is twice the value of the corresponding element of row 2. Otherwise, it returns false. (ii) Determine the worst case complexity of the algorithm which you have developed.arrow_forwardGiven is a strictly increasing function, f(x). Strictly increasing meaning: f(x)< f(x+1). (Refer to the example graph of functions for a visualization.) Now, define an algorithm that finds the smallest positive integer, n, at which the function, f(n), becomes positive. The things left to do is to: Describe the algorithm you came up with and make it O(log n).arrow_forward
- Database System ConceptsComputer ScienceISBN:9780078022159Author:Abraham Silberschatz Professor, Henry F. Korth, S. SudarshanPublisher:McGraw-Hill EducationStarting Out with Python (4th Edition)Computer ScienceISBN:9780134444321Author:Tony GaddisPublisher:PEARSONDigital Fundamentals (11th Edition)Computer ScienceISBN:9780132737968Author:Thomas L. FloydPublisher:PEARSON
- C How to Program (8th Edition)Computer ScienceISBN:9780133976892Author:Paul J. Deitel, Harvey DeitelPublisher:PEARSONDatabase Systems: Design, Implementation, & Manag...Computer ScienceISBN:9781337627900Author:Carlos Coronel, Steven MorrisPublisher:Cengage LearningProgrammable Logic ControllersComputer ScienceISBN:9780073373843Author:Frank D. PetruzellaPublisher:McGraw-Hill Education