Your lecturer is a funny guy; given an unsorted list of integer numbers of n elements,...
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
Your lecturer is a funny guy; given an unsorted list of integer numbers of n elements, and to find the largest number in the list, he will first initialize a variable, let's say max, to the smallest possible number an integer can be, and randomly select an element (a number) from the unsorted list. Check if this number is greater than the variable max. If it is, he will set the variable max to the number. Next, he will discard the number from the list and create a new list. The new list now has n - 1 elements. He will continue with the same process on the n-1 elements list until the unsorted list has no more element. When this happens, the variable max will contain the largest number in the list. (a) Write in pseudocode a recursive implementation of the described algorithm. (b) Analyse the asymptotic complexity of the algorithm. Give the worst-case, average- case and best-case running time in terms of 8 notation. Justify your answer. Your lecturer is a funny guy; given an unsorted list of integer numbers of n elements, and to find the largest number in the list, he will first initialize a variable, let's say max, to the smallest possible number an integer can be, and randomly select an element (a number) from the unsorted list. Check if this number is greater than the variable max. If it is, he will set the variable max to the number. Next, he will discard the number from the list and create a new list. The new list now has n - 1 elements. He will continue with the same process on the n-1 elements list until the unsorted list has no more element. When this happens, the variable max will contain the largest number in the list. (a) Write in pseudocode a recursive implementation of the described algorithm. (b) Analyse the asymptotic complexity of the algorithm. Give the worst-case, average- case and best-case running time in terms of 8 notation. Justify your answer.
Expert Answer:
Answer rating: 100% (QA)
a Heres a pseudocode for a recursive implementation of the given algorithm function findMaxnumbers c... View the full answer
Related Book For
Data Structures and Algorithm Analysis in Java
ISBN: 978-0132576277
3rd edition
Authors: Mark A. Weiss
Posted Date:
Students also viewed these algorithms questions
-
The P-value is=? The following table lists results from an experiment designed to test the ability of dogs to use their extraordinary sense of smell to detect malaria in samples of children's socks...
-
can someone solve this Modern workstations typically have memory systems that incorporate two or three levels of caching. Explain why they are designed like this. [4 marks] In order to investigate...
-
) Consider integer division of one two's-complement binary number by another. Programming languages may vary in the result when one argument is negative. What differing conventions might they be...
-
(a) By what percentage does your rest mass increase when you climb 30 m to the top of a ten-story building? Are you aware of this increase? Explain. (b) By how many grams does the mass of a 120-g...
-
(a) Of the 25-1 = 24 = 16 compositions of 5, determine how many start with (i) 1. (ii) 2. (iii) 3. (iv) 4. (v) 5. (b) Provide a combinatorial proof for the result in part (a) of Exercise 2.
-
Ambassador - your score is 14 points out of 25 Advocate - your score is 18 out of 25 People Mover - your score is 15 out of 25 Truth-Seeker - your score 19 out of 25 Creative builder - your score is...
-
At year end, Riverside Corporation announced that it would change its inventory valuation method from last-in, first-out (LIFO) to first-in, first-out (FIFO). The company also disclosed that the...
-
Assume that Timekiller, Inc., manufactures a new electronic game console. The current standard costs sheet for a game console follows: Direct materials, ? kilograms at $4 per kilogram . . . . $ ? per...
-
From the following four statements which two are true? I) payment of long-term debt creates a cash outflow in cash flows from financing activities II) interest received creates a cash outflow in cash...
-
The set of mobile gaming apps in which the number of monthly users was greater than 12 million. Use the following table, which shows the number of monthly users, in millions, for the 10 most used...
-
2. Orange Company owns 90% of the voting stock of Purple, Inc. Orange Company is deemed to control Purple, Inc. During 2018, Orange Company sold land costing $1,500,000 to Purple, Inc. for...
-
In order to protect domestic jobs, country Alpha places a tariff on imported goods from country Bravo. a) What happens to the price of Alpha's imported goods from Bravo? What happens to the quantity...
-
How does self-interest impact the marketing process? How could marketers convince an audience to support funding for after-school program services that they do not use? Provide an example of an...
-
Bims Corporation uses the weighted-average method in its process costing system. The Assembly Department started the month with 6,000 units in its beginning work in process inventory that were 90%...
-
For this activity you are going to research Canada's current (or as current as possible) Consumer Price Index (CPI) and also provide information about how the price of various items has changed over...
-
Design a database to automate the intake process for an estate planning attorney. The current process is based on capturing information in the attached form which every client completes....
-
Based on the Indian Bollywood movie The Tashkent Files Case Analysis Template Read the case you are assigned. Review the case analysis PowerPoint posted on Blackboard. Use the case analysis template...
-
What key concerns must functional tactics address in marketing? Finance? POM? Personnel?
-
Using Stirling's formula, N! (N/e)N 2N, give a precise estimate for log(N!).
-
Write a program that lists all files in a directory and their sizes. Mimic the routine in the online code.
-
If all the edges in a graph have weights between 1 and |E|, how fast can the minimum spanning tree be computed?
-
Which core job characteristic promotes job satisfaction for nurses? A. Rigid rules. B. Autonomy in decision making. C. Hierarchical decision making. D. Lack of communication with physicians.
-
According to Herzberg, a nurse is apt to leave a job if: A. Interpersonal relationships with coworkers are bad. B. Opportunities for promotion are rare. C. Achievements are not recognized. D. No...
-
Which employee is most likely to be a representative of Generation X? A. Mary, who has worked at the hospital for 10 years and would not think of quitting. B. Sue, who is motivated by money and will...
Study smarter with the SolutionInn App