Define a pure, recursive function argmax that takes two arguments: a function f that maps a...
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
Define a pure, recursive function argmax that takes two arguments: a function f that maps a value in set A to a number, and a nonempty list xs of values in set A. It returns an element xin xs for which (f x) is as large as possible. You may assume f is pure, i.e., it always produces the same result for the same argument. Assuming f takes constant time, argmax should be O(n) in the length of xs. There are many ways to make the asymptotic complexity of argmax worse than O(n), but two common ways are computing the length of the xs argument in each recursive step and computing f(x) more than once for each value x. Examples: (define (square x) (* x x)) (argmax square '(1 2 -10)) => -10 Hint: The specification of argmax states that xs is non-empty. Exploit this fact. You may want to use a let expression, but first try to implement your solution without let. Once you having a working solution that you understand, you may see an opportunity to use let to avoid recomputing a value. Bonus: If you're up for a real challenge, write an implementation of argmax that calls f the fewest number of times possible. In general, argmax only needs to call f at most once for each item in xs. There is one case where argmax can get away without calling f at all. If we take advantage of the fact that f is pure, then for some inputs we can do even better, but accomplishing this is quite tricky. If you can write an argmax that calls f at most once for each item in xs, it is worth 5 bonus points. Define a pure, recursive function argmax that takes two arguments: a function f that maps a value in set A to a number, and a nonempty list xs of values in set A. It returns an element xin xs for which (f x) is as large as possible. You may assume f is pure, i.e., it always produces the same result for the same argument. Assuming f takes constant time, argmax should be O(n) in the length of xs. There are many ways to make the asymptotic complexity of argmax worse than O(n), but two common ways are computing the length of the xs argument in each recursive step and computing f(x) more than once for each value x. Examples: (define (square x) (* x x)) (argmax square '(1 2 -10)) => -10 Hint: The specification of argmax states that xs is non-empty. Exploit this fact. You may want to use a let expression, but first try to implement your solution without let. Once you having a working solution that you understand, you may see an opportunity to use let to avoid recomputing a value. Bonus: If you're up for a real challenge, write an implementation of argmax that calls f the fewest number of times possible. In general, argmax only needs to call f at most once for each item in xs. There is one case where argmax can get away without calling f at all. If we take advantage of the fact that f is pure, then for some inputs we can do even better, but accomplishing this is quite tricky. If you can write an argmax that calls f at most once for each item in xs, it is worth 5 bonus points.
Expert Answer:
Answer rating: 100% (QA)
Heres a pure recursive implementation of the argmax function that meets the requirements scheme define argmax f xs if null cdr xs car xs let maxsofar ... View the full answer
Related Book For
Data Structures And Algorithms In C++
ISBN: 9780470383278
2nd Edition
Authors: Michael T. Goodrich, Roberto Tamassia, David M. Mount
Posted Date:
Students also viewed these algorithms questions
-
Let A, B be sets. Define: (a) the Cartesian product (A B) (b) the set of relations R between A and B (c) the identity relation A on the set A [3 marks] Suppose S, T are relations between A and B, and...
-
Design a Java class that represents a cache with a fixed size. It should support operations like add, retrieve, and remove, and it should evict the least recently used item when it reaches capacity.
-
The objective of this problem is to design and develop a program for Huffman coding algorithm. The discrete source has an alphabet X = {x1, x2, x3, x4, x5, x6, x7, x8, x9} with corresponding...
-
Various concepts of distance are used in international business. Define and explain at least five concepts of distance, and discuss how each might affect bilateral foreign direct investment (FDI)...
-
Two sinusoidal waves, identical except for phase, travel in the same direction along a string, producing a net wave y'(x, t) = (3.0 mm) sin (20x 4.0t + 0.820 rad), with x in meters and t in seconds....
-
Derive \(C_{p}-C_{v}=R\), with usual notations.
-
The appropriate method of amortizing a premium or discount on issuance of bonds is the effective interest method. Required 1. What is the effective interest method of amortization and how is it...
-
Name four characteristics of Force?
-
Spelling Basketball Company manufactures basketballs that retail for $ 15 each. The capacity of the current company allows them to only manufacture 1,000,000 basketballs every year, and they are able...
-
Research the top management of the organization Maroc telecom and detail the strategies that they advocated to help grow the company. As many companies had problems starting around 2020 pandemic...
-
Leadership theories in healthcare organizations optimizes the effectiveness of leadership. Explain the statement.
-
Critically analyse the role of leadership in promoting effectiveness in education.
-
Explore the Link between Emotional Intelligence and Cross-Cultural Leadership Effectiveness Global corporations operate in an environment characterized by crosscultural differences. This exploratory...
-
Briefly explain the meaning of the following terms: (i) Ideal standard costs (ii) Attainable standard costs The management accountant of Bridgetown Ltd is finding it difficult to cope with increasing...
-
Top Top Ten Sdn. Bhd. is a leading manufacturer of disposable rubber gloves and provide high quality gloves at the efficient low cost. The demand for this commodity has been growing throughout the...
-
A superior criticized a sales manager for selling high-revenue, low-profit items instead of lower-revenue but higher-profit items. The sales manager responded, My income is based on commissions that...
-
Implement a program that can input an expression in postfix notation (see Exercise C-5.8) and output its value. Data from in Exercise C-5.8 Postfix notation is an unambiguous way of writing an...
-
Illustrate the performance of the selection-sort algorithm on the following input sequence: (22,15,36,44,10,3,9,13,29,25).
-
Describe a set of operations for an ordered dictionary ADT that would correspond to the functions of the ordered map ADT. Be sure to define the meaning of the functions so that they can deal with the...
-
Determine whether each of the following statements is true or false: Management accountants are now more often looked upon as internal business advisors rather than bean counters recording historical...
-
Determine whether each of the following statements is true or false: Management accountants should be technically proficient, but they dont need strong oral and written communication skills.
-
Determine whether each of the following statements is true or false: The Sarbanes-Oxley Act of 2002 (SOX) imposes stricter requirements for financial reporting and internal controls and stricter...
Study smarter with the SolutionInn App