You are competing with your friends to type text messages on your smartphone as quickly as...
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
You are competing with your friends to type text messages on your smartphone as quickly as possible. Here are the rules: you use two thumbs for texting and they start out on the bottom left and bottom right keys of the keyboard. To type a character, you move either thumb from its current key to the key you need to press, and it takes time equal to the distance between the keys. You can assume the following: The keyboard has keys labeled {1,2,..., k} and there is a function dist (i,j) to calculate the distance between two keys i and j. (To visualize this, you may want to imagine the digits 1 through 9 arranged on a standard numeric keypad). ⚫ Your left thumb starts on key a, and your right thumb starts on key b. (For example, on the 9-digit numeric keypad, a = 7 is the bottom left key, and b = 9 is the bottom right key.) You can press any key with either thumb ⚫ Both thumbs can rest on the same key if necessary The characters to by typed are c₁C2 Cn, where c; E {1, 2,..., k} is the ith key to push Homework 4 3 Design an algorithm that finds the fastest way to type the message. In other words, your algorithm needs to decide which thumb to use to type each character, and it should minimize the total distance moved by your two thumbs. Try to use O(nk2) time. You are competing with your friends to type text messages on your smartphone as quickly as possible. Here are the rules: you use two thumbs for texting and they start out on the bottom left and bottom right keys of the keyboard. To type a character, you move either thumb from its current key to the key you need to press, and it takes time equal to the distance between the keys. You can assume the following: The keyboard has keys labeled {1,2,..., k} and there is a function dist (i,j) to calculate the distance between two keys i and j. (To visualize this, you may want to imagine the digits 1 through 9 arranged on a standard numeric keypad). ⚫ Your left thumb starts on key a, and your right thumb starts on key b. (For example, on the 9-digit numeric keypad, a = 7 is the bottom left key, and b = 9 is the bottom right key.) You can press any key with either thumb ⚫ Both thumbs can rest on the same key if necessary The characters to by typed are c₁C2 Cn, where c; E {1, 2,..., k} is the ith key to push Homework 4 3 Design an algorithm that finds the fastest way to type the message. In other words, your algorithm needs to decide which thumb to use to type each character, and it should minimize the total distance moved by your two thumbs. Try to use O(nk2) time.
Expert Answer:
Answer rating: 100% (QA)
To design an algorithm that finds the fastest way to type the message with a complexity of Onk we can use dynamic programming Lets define a function d... View the full answer
Related Book For
Posted Date:
Students also viewed these programming questions
-
"internet radios" for streaming audio, and personal video recorders and players. Describe design and evaluation processes that could be used by a start-up company to improve the usability of such...
-
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...
-
A manager found the following information for his company: Profit margin = 0.08 and total asset turnover = 1.85. Given that the total assets of the company is $200 million, the total liabilities is...
-
The controller of Willson Company has computed quality costs as a percentage of sales for the past five years (2009 was the first year the company implemented a quality improvement program). This...
-
To construct a loop that works correctly, you should initialize a loop control ____________. a. Condition b. Constant c. Structure d. Variable
-
The Howell Corporation has the following account balances (in millions): Prepare an income statement and a supporting schedule of cost of goods manufactured for the year ended December 31, 2017. (For...
-
Tailgator Company produces four versions of its model J7-21 bicycle seat. The four versions have different shapes, but their processing operations and production costs are identical. During July, the...
-
Two large charged sheets are placed a distance D apart. The top sheet has uniform sur- face charge density + while the bottom sheet has uniform charge density -20. The sheets are large compared to...
-
Theme: Meaning of leadership Find at least two external sources related to your theme upon which you can draw for your explanation. Then make a post with the following: Explain the theme Cite sources...
-
List three reasons firms work hard to achieve market leadership.
-
Describe the purpose of a mission statement.
-
Describe the characteristics of a mature industry. What is the primary opportunity for new firms in a mature industry?
-
Describe what is meant by the term core strategy and why it is important.
-
What is a geographic expansion strategy, and what are the keys to implementing a successful geographic expansion strategy for an entrepreneurial firm?
-
Imagine you have completed a stakeholder analysis and you identify a high power, high interest stakeholder with strong objections to change, even though the stakeholder agrees that the identified...
-
A researcher reports a significant two-way between-subjects ANOVA, F(3, 40) = 2.96. State the decision to retain or reject the null hypothesis for this test.
-
Some argue that globalization has gone too far. Others argue that globalization, despite its imperfections, makes the world better. What are the ethical dilemmas in each position? What do you think?
-
The California Public Employees Retirement System (CalPERS) is one of the worlds largest pension funds and one of the earliest to divest stocks of firms that did not meet its ESG criteria. For...
-
As a CEO, you are concerned that your firm and the industry in your country are being devastated by foreign imports. Trade lawyers suggest that you file an antidumping case against leading foreign...
-
What are the purposes of the international capital market?
-
A strong US dollar makes imports cheaper for American consumers, but it also makes American exports less competitive and more expensive on the global market. What are the implications of a strong and...
-
You are the senior accountant for a business that regularly imports spare parts for a range of your products from overseas suppliers. You have been instructed by the CEO to look at ways you can save...
Study smarter with the SolutionInn App