6. The input to this problem consists of an ordered list of n words. The length...
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
6. The input to this problem consists of an ordered list of n words. The length of the ith word is wi, that is the ith word takes up w; spaces. (For simplicity assume that there are no spaces between words.) The goal is to break this ordered list of words into lines; this is called a layout. Note that you cannot reorder the words. The length of a line is the sum of the lengths of the words on that line. The maximum line length is L. Assume that w; L for all i. No line may be longer than L, although it may be shorter. The penalty for having a line of length K < L is L - K. Consider the following greedy algorithm. For i = 1 to n Place the ith word on the current line if it fits else place the ith word on a new line (a) The overall penalty is defined to be the sum of the line penalties. The problem is to find a layout that minimizes the overall penalty. Prove of disprove that the above greedy algorithm correctly solves this problem. (b) The overall penalty is now defined to be the maximum of the line penalties. The problem is to find a layout that minimizes the overall penalty. Prove of disprove that the above greedy algorithm correctly solves this problem. 6. The input to this problem consists of an ordered list of n words. The length of the ith word is wi, that is the ith word takes up w; spaces. (For simplicity assume that there are no spaces between words.) The goal is to break this ordered list of words into lines; this is called a layout. Note that you cannot reorder the words. The length of a line is the sum of the lengths of the words on that line. The maximum line length is L. Assume that w; L for all i. No line may be longer than L, although it may be shorter. The penalty for having a line of length K < L is L - K. Consider the following greedy algorithm. For i = 1 to n Place the ith word on the current line if it fits else place the ith word on a new line (a) The overall penalty is defined to be the sum of the line penalties. The problem is to find a layout that minimizes the overall penalty. Prove of disprove that the above greedy algorithm correctly solves this problem. (b) The overall penalty is now defined to be the maximum of the line penalties. The problem is to find a layout that minimizes the overall penalty. Prove of disprove that the above greedy algorithm correctly solves this problem.
Expert Answer:
Related Book For
Posted Date:
Students also viewed these programming questions
-
An "Airplay" feature at Wohlers Hall has a malfunction on 30% of all lecture slides. Suppose malfunctions are independent (and each slide can either have no malfunctions or one malfunction). a) If 4...
-
How do socio-cognitive mechanisms, such as social identity theory and self-categorization theory, contribute to the formation and maintenance of organizational culture ?
-
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...
-
You work in the finance department of a telecommunications firm with a large direct sales force selling high- speed fiber optics access lines to companies wanting telephone and Internet access. Your...
-
What role should organizational stability play in the organizational change process?
-
How are structured, object-oriented, and agile methods similar? How are they different?
-
Effect of Bond Issuance A bond with a face value of $10,000 is issued at a discount of $800 on January 1, 2008. The face rate of interest on the bond is 7%. Required 1. Was the market rate at the...
-
Jazzy Cases manufactures several different styles of jewelry cases. Management estimates that during the first quarter of this year the company will operate at about 80% of normal capacity. Two...
-
1. Indicate the effect of the following on the operating cycle: Customers take longer to make the payment 2. Indicate the effect of the following on the operating cycle: Accounts payable goes up 3....
-
Gillian Shaw opened Shaws Carpet Cleaners on March 1. During March, the following transactions were completed. Mar. 1 Invested $10,000 cash in the business. 1 Purchased used truck for $6,000, paying...
-
As a social media manager, address how social media use during emergencies has evolved.
-
In a clinical trial of a drug intended to help people stop smoking, 132 subjects were treated with the drug for 13 weeks, and 19 subjects experienced abdominal pain. If someone claims that more than...
-
A company pays for utilities used during the current month. What is the journal entry this company needs to make? Debit Credit A company pays for utilities used during the current month. What is the...
-
Giving a test to a group of students, the grades and gender are summarized below A B C Total Male 7 9 15 31 Female 20 14 11 45 Total 27 23 26 76 If one student is chosen at random, Find the...
-
The "X"s on the principle axis represents the focal point of the lens. The distance from lens to the focal point is called the focal length (f). The focal length is equal in either side of the lens....
-
Could you please answer these questions step by step using the necessary formula or a finance calculator, if you're using the finance calculator, please let me know the inputs and what did you do....
-
10. En general, qu se esperara que ocurriera cuando seeliminan los subsidios cruzados con el uso del costeo basado enactividades (ABC)?A. Que los productos de menor volumen se determinarn c 1 answer
-
Southwestern Punch was made by Frutayuda, Inc. and sold in 12-ounce cans to benefit victims of Hurricane Zero. The mean number of ounces placed in a can by an automatic fill pump is 11.7 with a...
-
Identify the graph(s) with six edges. Use the figure shown. b a b a e F F F F d Graph S e Graph T e Graph U e Graph V Graph W
-
Name the edges in Graph \(T\). Use the figure shown. b a b a e F F F F d Graph S e Graph T e Graph U e Graph V Graph W
-
Identify any of the graphs that is a subgraph of Graph \(D\). Use the figure shown. Graph A S U Graph B S S pe 9 Graph C Graph D S
Study smarter with the SolutionInn App