4. (6 pts) The following functions each determine if any two values in alist sum to...
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
4. (6 pts) The following functions each determine if any two values in alist sum to asum. As is shown in the notes, (a) write the complexity class of each statement on its right, where N is len (alist). (b) Write the full calculation that computes the complexity class for the entire function. (c) Simplify what you wrote in (b). def sums to 1 (alist, asum): for f in alist: for s in alist: if f+s == asum: def sums to 2 (alist, asum): aset = set (alist) for v in alist: return (f,s). return None (b) (b) (c) (c) if asum-v in aset return (v, asum-v) return None (d) For both functions, which takes longer: finding a solution or finding no solution? 4. (6 pts) The following functions each determine if any two values in alist sum to asum. As is shown in the notes, (a) write the complexity class of each statement on its right, where N is len (alist). (b) Write the full calculation that computes the complexity class for the entire function. (c) Simplify what you wrote in (b). def sums to 1 (alist, asum): for f in alist: for s in alist: if f+s == asum: def sums to 2 (alist, asum): aset = set (alist) for v in alist: return (f,s). return None (b) (b) (c) (c) if asum-v in aset return (v, asum-v) return None (d) For both functions, which takes longer: finding a solution or finding no solution?
Expert Answer:
Related Book For
Income Tax Fundamentals 2013
ISBN: 9781285586618
31st Edition
Authors: Gerald E. Whittenburg, Martha Altus Buller, Steven L Gill
Posted Date:
Students also viewed these programming questions
-
CANMNMM January of this year. (a) Each item will be held in a record. Describe all the data structures that must refer to these records to implement the required functionality. Describe all the...
-
QUIZ... Let D be a poset and let f : D D be a monotone function. (i) Give the definition of the least pre-fixed point, fix (f), of f. Show that fix (f) is a fixed point of f. [5 marks] (ii) Show that...
-
Which market segments are the most favorable for Hyundai card? Does the company do an effective job of targeting and reaching those segments? If so, How? If not, why not?
-
TELUS's financial statements are given in Appendix A at the end of this book. 1. TELUS has subsidiaries. What is TELUS's percentage of ownership? How can you tell? 2. TELUS reports long-term...
-
Terry Lloyd and Joan Lopez organized Read More Store as a corporation; each contributed $50,000 cash to start the business and received 4,000 shares of capital. The store completed its first year of...
-
In a contract dispute between a US company and a Canadian company, the contract itself referred to provisions of the Uniform Commercial Code. Do these references alone preempt the contract from being...
-
Beeler Furniture Company deposits all cash receipts each Wednesday and Friday in a night depository, after banking hours. The data required to reconcile the bank statement as of June 30 have been...
-
For each of the following matrices A Maxn (R), test A for diagonal- izability, and if A is diagonalizable, find an invertible matrix Q and a diagonal matrix D such that Q-1AQ = D. (a) (63) 2 1 3 (b)...
-
1. Since Mr. Snodgrass doesnt have any historical data, (only an estimate of the number of customers hell serve each month), which specific type of qualitative method is he using? What would be the...
-
What are the issues related to documentation in an audit context. 1.Choose recorded sales invoices and trace the corresponding shipping documents to verify the existence of goods shipped. 2.To test...
-
The Marketing Vice President (VP) has asked her team to propose qualitative and quantitative data collection strategies. She has decided to use qualitative and quantitative methods (i.e., a...
-
Japan is an oil importer. Japan's currency is the Japanese yen (JPY), but oil is priced in USD per barrel. If the Federal Reserve lowers interest rates in the United States and there is no change in...
-
A firm whose home currency is the Mexican Peso (MNX) is considering an investment in the United States. The investment is expected to produce after-tax United States dollar (USD) cash flows (in...
-
Review the marketing efforts of a small business with which you are familiar or use your business, if applicable. What marketing strategies and campaigns are they/you using? Share some examples of...
-
After the hurricane passed, the weatherman said that a total of 20 inches of rain fell over a 48-hour period. Assuming the rain fell at the same rate over the entire time period, how much rain fell...
-
Gas is escaping from a spherical balloon at the rate of 12 ft 3 /hr. At what rate (in feet per hour) is the radius of the balloon changing when the volume is 300 ft 3 ?
-
(a) Bright Sdn Bhd (BSB) is a tax resident manufacturing company in Johor, which involves in ceramic tiles. Currently, BSBs annual sales turnover has been forecasted to be around RM 300,000 for the...
-
Leslie is a single taxpayer who is under age 65 and in good health. For 2012, she has a salary of $23,000 and itemized deductions of $1,000. Leslie is entitled to one exemption on her tax return. a....
-
Carl and Jenny adopt a Russian orphan. The adoption takes 2 years and two trips to Russia and is final in 2012. They pay $6,000 in 2011 and $7,500 in 2012 of qualified adoption expenses, and have AGI...
-
a. Wilson filed his individual tax return on the original due date, but failed to pay $700 in taxes that were due with the return. If Wilson pays the taxes exactly 2 months late, calculate the amount...
-
Construct a stem-and-leaf plot of the poverty data discussed in Example 6. Approach We will use Minitab. The steps for constructing the graphs using Minitab or StatCrunch are given in the Technology...
-
Draw a dot plot for the number of arrivals at Wendys data from Table 8. Approach The smallest observation in the data set is 1 and the largest is 11. Write the numbers 1 through 11 horizontally. For...
-
The following data represent the number of grams of fat in breakfast meals offered at a local fast food restaurant. (a) construct a stem-and-leaf plot and (b) describe the shape of the distribution....
Study smarter with the SolutionInn App