2. Consider the following procedure, which takes a list L, ts length n < and a...
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
2. Consider the following procedure, which takes a list L, ts length n< and a positive integer l as parameters function MYSTERY(L, n, l) for i from 1 to n - l + 1 do for j from i+ 1 to n-l+ 1 do matched-true for k from 0 to l - 1 do if Li+k Lj+k then matched-false end if end for if matched is still true then return (i, j) end if end for end for return reporting failure end function (a) Walk through this procedure with some examples (some promising samples might be L = [3, 1, 7, 2, 7, 2,5] with n = 7 and k = 2, or L = [1, 2, 3, 1, 2, 4, 2] with n = 6 and k = 3). What does it seem to do? When it returns an ordered pair, what information is it conveying? (b) What is the worst-case runtime of this algorithm, in big-O notation as a function of n and k? Explain your reasoning. 2. Consider the following procedure, which takes a list L, ts length n< and a positive integer l as parameters function MYSTERY(L, n, l) for i from 1 to n - l + 1 do for j from i+ 1 to n-l+ 1 do matched-true for k from 0 to l - 1 do if Li+k Lj+k then matched-false end if end for if matched is still true then return (i, j) end if end for end for return reporting failure end function (a) Walk through this procedure with some examples (some promising samples might be L = [3, 1, 7, 2, 7, 2,5] with n = 7 and k = 2, or L = [1, 2, 3, 1, 2, 4, 2] with n = 6 and k = 3). What does it seem to do? When it returns an ordered pair, what information is it conveying? (b) What is the worst-case runtime of this algorithm, in big-O notation as a function of n and k? Explain your reasoning.
Expert Answer:
Related Book For
Java An Introduction To Problem Solving And Programming
ISBN: 9780134462035
8th Edition
Authors: Walter Savitch
Posted Date:
Students also viewed these programming questions
-
Assignment 5: Hash Table implementation andconcordance There are three parts to this assignment. In the first two parts,you will complete the implementation of a hash map and aconcordance program. In...
-
You are required to write a Python program that will manage character (heroes and villain) information. Character (hero and villain) information will be stored in a text file that will be read in...
-
Calculate the pre-merger earnings per share for Admiral and Favorite and the pre-merger price-to-earnings (P/E) ratio for each company (based on the stated prices per share). Calculate the exchange...
-
Identify the accounts debited and credited to account for uncollectibles under (a) The allowance method, (b) The direct write-off method.
-
If the jobs displayed in Table 11.19 are processed using the earliest-due-date rule, a. What would be the lateness of job C?b. What would be the lateness of job E? c. What would be the tardiness of...
-
White Company can invest in one of two projects, TD1 or TD2. Each project requires an initial investment of $101,250 and produces the year-end cash inflows shown in the following table. Required 1....
-
Governmental Funds Statement of Revenues Expenditures and Changes in Fund Balance. You have recently started working as the controller for a small county. The county is preparing its financial...
-
What is a sampling distribution? Explain
-
Taxation of reorganizations & liquidations dividends ABC Corp (ABC) was formed 15 years ago by Able and Body (2 individuals). ABC uses the cash method of accounting and reports on a calendar year...
-
Using the Consolidated Statement of Cash Flows of this company, identify a decision the company would make concerning financing activities and investing activities. Was the cash flow positive or...
-
Describe the concept of project planning. In your response, focus upon: What is project planning and why is it important? Who is involved in the project planning process? What are some of the major...
-
Utilizing the STP model show how your business concept will divide the market into subgroups or segments to determine which segment should be pursued/targeted and finally decide how it should...
-
1. Explain how a brand's image is linked to a consumer's self concept. 2. Explain the concept of lifestyle. 3. How is the concept of psychographics different from lifestyle.
-
Your assignment is to develop the concept for a new business for this market space. For example, you may decide that thereought to be a business coordinating the sharing of lawn mowers. (You don't...
-
We have an undirected graph G = (V, E) with m = |E| and n = |V|. Let (x, y) be an edge in G. What is correct about the following statement? If T is a BFS tree of G, then the level of x and y differ...
-
Give journal entries for the issue of 1,50,000 debentures of Rs. 10 each under the following conditions : (i) Issues at par. (ii) Issued at 10% premium. (iii) Issued at 10% discount.
-
Making use of the tables of atomic masses, find the velocity with which the products of the reaction B10 (n, ) Li7 come apart; the reaction proceeds via interaction of very slow neutrons with...
-
Create a program that tests the class Merlin described in the previous exercise. Use the toString method to verify that a unique instance has been created. Previous exercise. Sometimes we would like...
-
Write a program that simulates a bouncing ball by computing its height in feet at each second as time passes on a simulated clock. At time zero, the ball begins at height zero and has an initial...
-
Write a program that reads a string from the keyboard and tests whether it contains a valid date. Display the date and a message that indicates whether it is valid. If it is not valid, also display a...
-
Describe a job in which you think an employee recognition program might be an effective means for changing and improving employee behaviour. Explain how you would design the program and how you would...
-
Describe a situation in which you think an employer could use organizational behaviour modification and an employee recognition program to improve or correct employee behaviour. Can you anticipate...
-
A supervisor in a textile factory observes that one of her employees is violating a safety rule that could result in severe injury. What combination of reinforcement, punishment, and extinction could...
Study smarter with the SolutionInn App