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)
- Imagine a collection of nuts and bolts that are all together in one pile on a table. Describe, in pseudocode, how you would find all matching pairs of nuts and bolts. You need to find one solution for each of the problem-solving approaches given below. For each of your solution, determine how many comparisons of pairs of nuts and bolts you might have to make in the best- and worst- case scenario. You can assume that there are complete pairs, no single nuts or bolts, and that for each bolt, there is exactly one nut that fits. Describe a solution to the nuts and bolts problem (in pseudocode) using a Divide and Conquer Approach.arrow_forwardConsider a maze represented by a matrix of m rows and n columns with obstacles (see the figure below). A cell with a value = -1 is an obstacle that cannot be overcome. The goal is to start from cell [0, 0] and reach the last cell [m-1, n-1]. This may be possible by taking several paths. Count the number of these paths. The movement is allowed from cells (i+ 1, j) and (i, j+ 1) only. -1 -1 Provide two solutions, one iterative and one recursive to the above problem.arrow_forwardImplement an algorithm backtracking for the Knight's tour PROBLEM, starting from one of the corner. Enter the time in seconds and present the solution.arrow_forward
- Imagine 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_forwardConsider 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_forwardWe can specify the PageRank algorithm's convergence threshold using proc networks. This figure has to be positive. Default value is 1E-9. When the difference between the PageRank scores of the current iteration and the previous iteration is less than or equal to the tolerance set, the PageRank algorithm ceases iterating. We can use the PAGERANKTOLERANCE= parameter to specify the convergence tolerance. Write The example code demonstrates how to calculate PageRank centrality using a proc network built on a directed graph with unweighted links.arrow_forward
- A graph is a collection of vertices and edges G(V, E). A weighted graph has weights (numbers, etc.) on every edge. A multigraph can have more than one edges between any vertices. Explain why a person should use a weighted graph instead of a multigraph. Give examples. An adjacency matrix might be a better choice for speeding up a program, however, it consumes huge memory for large graphs. How this situation can be improved? What programming constructs better suit graph representation? Explain with examplearrow_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_forwardYou are given a collection of n bolts of different widths and n corresponding nuts. You are allowed to try a nut and bolt together, from which you can determine whether the nut is larger than the bolt, smaller than the bolt, or matches the bolt exactly. However, there is no way to compare two nuts together or two bolts together. The problem is to match each bolt to each nut. Design an algorithm for this problem with Θ(n log n) average-case complexity (in terms of nut-bolt comparisons). Explain why your algorithm has Θ(n log n) average case complexity.arrow_forward
- Imagine there are N teams competing in a tournament, and that each team plays each of the other teams once. If a tournament were to take place, it should be demonstrated (using an example) that every team would lose to at least one other team in the tournament.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_forwardYou are given a collection of n bolts of different widths and n corresponding nuts. You are allowed to try a nut and bolt together, from which you can determine whether the nut is larger than the bolt, smaller than the bolt, or matches the bolt exactly. However, there is no way to compare two nuts together or two bolts together. The problem is to match each bolt to each nut. Design an algorithm for this problem with Θ(n log n) average-case complexity (in terms of nut-bolt comparisons). Explain why your algorithm has Θ(n log n) average-case complexity. You may use any result without explicitly solving recurrence equations.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