(5 pts) (10 pts) 5. Sorting out complaints. A group of n students, all of whom...
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
(5 pts) (10 pts) 5. Sorting out complaints. A group of n students, all of whom have distinct heights, line up in a single-file line for a group photo. Any student who stands somewhere in front of a shorter student will conceal the shorter student, who will not appear in the picture. (The taller student need not be directly in front of the shorter one.) For this reason, each student makes one complaint to the photographer for each taller student in front of them. In this problem we are concerned with algorithms that determine the number of complaints that will be made. The input is an array A[1,...,n] of the students' heights, from the front of the line to the back. (So, A[1] is the height of the student in the very front, and A[n] is the height of the student in the very back.) The desired output is the total number of complaints. (Throughout this question, assume that two heights can be compared in constant time, independent of n.) (a) Describe briefly, clearly, and precisely (in English) a simple brute-force algorithm for this problem; do not give pseudocode. State, with brief justification, a (.) bound on its (worst-case) running time as a function of n. You do not need to give a formal proof. Solution: (b) Suppose that both the front half and back half of the line (i.e., the two halves of the array A) happen to be sorted in ascending order, though the line as a whole may not be. Describe clearly and precisely (in English or in pseudocode, as you prefer) an O(n)-time algorithm that outputs the number of complaints in this scenario, and briefly justify its correctness and running time. (5 pts) (10 pts) 5. Sorting out complaints. A group of n students, all of whom have distinct heights, line up in a single-file line for a group photo. Any student who stands somewhere in front of a shorter student will conceal the shorter student, who will not appear in the picture. (The taller student need not be directly in front of the shorter one.) For this reason, each student makes one complaint to the photographer for each taller student in front of them. In this problem we are concerned with algorithms that determine the number of complaints that will be made. The input is an array A[1,...,n] of the students' heights, from the front of the line to the back. (So, A[1] is the height of the student in the very front, and A[n] is the height of the student in the very back.) The desired output is the total number of complaints. (Throughout this question, assume that two heights can be compared in constant time, independent of n.) (a) Describe briefly, clearly, and precisely (in English) a simple brute-force algorithm for this problem; do not give pseudocode. State, with brief justification, a (.) bound on its (worst-case) running time as a function of n. You do not need to give a formal proof. Solution: (b) Suppose that both the front half and back half of the line (i.e., the two halves of the array A) happen to be sorted in ascending order, though the line as a whole may not be. Describe clearly and precisely (in English or in pseudocode, as you prefer) an O(n)-time algorithm that outputs the number of complaints in this scenario, and briefly justify its correctness and running time.
Expert Answer:
Related Book For
Posted Date:
Students also viewed these algorithms questions
-
Planning is one of the most important management functions in any business. A front office managers first step in planning should involve determine the departments goals. Planning also includes...
-
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...
-
4. Using Euler's method to solve following equation with time step of 1. dy = = 4t - 0.5y dt y(0)=2 You only need to write out three steps to get values of y(1), y(2), y(3). 5. Write your Euler's...
-
What is the principal benefit of nonqualified plans over other forms of savings?
-
The Leegin ruling seems to affirm the Supreme Courts current preference for free-market principles and reduced judicial intervention in business practice. Accordingly, more competition and better...
-
Consider the quadratic programming problem. min x+x s.t. 1x2 = 4. x1
-
You have a $2 million portfolio consisting of a $100,000 investment in each of 20 different stocks. The portfolio has a beta equal to 1.1. You are considering selling $100,000 worth of one stock...
-
The sun is 30 above the horizon. It makes a 60 m -long shadow of a tall tree. Part A How high is the tree? Express your answer in meters. h = Submit Request Answer t 0 ? m
-
In problem 8.16, a college chemistry instructor thinks the use of embedded tutors will improve the success rate in introductory chemistry courses. The instructor carried out a hypothesis test and...
-
Use the substitution x = 7 sint to evaluate the integral f49 - x dx. Note: Use C for an arbitrary constant. Screen Shot 2022-03-06 at 6.11.59 PM Search Use the substitution x = 5 sect to evaluate the...
-
Yumco is a subscription-based meal plate producer and seller. Customers can only buy the meal plates if they subscribe for the weekly plan, which includes 7 dinner plates (i.e., 1 dinner plate for...
-
Write a company analysis of Starbucks about expanding its product line breadth to super-food blended beverage/smoothies.
-
Find a nationally advertised product that uses both broadcast and print advertising. Collect (or describe) samples of the product's advertising from both the broadcast and print media. Briefly...
-
You have just been hired as a human resources co-coordinator at ABC Computers, a nonunionized company that manufactures and sells computer parts in Ontario. You have conducted interviews within the...
-
For 2022, Tennessee imposes taxes on: All adjusted revenues of fantasy sports contests offered by a fantasy sports operator to Tennessee consumers. Inheritance, calculated on the value of the...
-
FIXIT has been provided an offer to move product by RAILCAR, a RAIL brokerage that works closely with railroads to schedule shipments. RAILCAR also coordinate schedules with the railroads to improve...
-
Extend Algorithms 3.4 and 3.5 to include as output the first and second derivatives of the spline at the nodes.
-
Use Equation (2.1) to compute, in a hand of bridge, the conditional probability that East has 3 spades given that North and South have a combined total of 8 spades.
-
A total of 48 percent of the women and 37 percent of the men that took a certain quit smoking class remained nonsmokers for at least one year after completing the class. These people then attended a...
-
The probability of getting a head on a single toss of a coin is p. Suppose that A starts and continues to flip the coin until a tail shows up, at which point B starts flipping. Then B continues to...
-
The current weighted average cost of capital (WACC) for Van der Welde is 10%. The company announced a debt offering that raises the WACC to 13%. The most likely conclusion is that for Van der Welde:...
-
According to Modigliani and Millers Proposition II without taxes: A. the capital structure decision has no effect on the cost of equity. B. investment and the capital structure decisions are...
-
In April, several employees of Javatech, Inc., a computer hardware developer with 250 employees, started organizing the Javatech Employees Union (JEU). When Javatech refused to voluntarily recognize...
Study smarter with the SolutionInn App