1

# Problem 6. (20 points) Texting. You are competing with your friends to type text messages on your...

## Question

###### Problem 6. (20 points) Texting. You are competing with your friends to type text messages on your... the pseudocode or precise description in words of the algorithm

Problem 6. (20 points) Texting. 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 ciccn, where c E 1,2,.. , k is the ith key to push omework 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. Example. Imagine the 9-digit numeric keypad where your thumbs start at a 7 and b 9, with input message cic2c3 589. The solution "left, right, left" would look like this: 0 Left/right thumbs start at 7/9 1. Left thumb moves from 7 to ci 5. Time dist(7, 5). Thumbs end at 5/9. 2. Right thumb moves from 9 to c2-8. Time- dist(9, 8). Thumbs end at 5/8. 3. Left thumb moves from 5 to c 9. Time dist(5, 9). Thumbs end at 9/8. Total time dist(7, 5) + dist(9, 8) + dist(5, 9)

#### Similar Solved Questions

##### A business for sale is being listed for \$500,000. Please for each the buyer and seller,...
A business for sale is being listed for \$500,000. Please for each the buyer and seller, list the most preferable and realistic ways this value would be split upon the various asset classifications listed by the IRS for a total value of \$500k from both the perspective of each the buyer and seller. Pl...
##### Hi! Would you be able to solve #3 problem using only a financial calculator ? Thanks...
Hi! Would you be able to solve #3 problem using only a financial calculator ? Thanks in advance for your time. + Fundamentals of Corporate Fin... e acTo 3mco | 300 | 400 ACTO Chapter 7 Problem 3QP Step 2 Step 3 Step 4 Step 3: Calculate the current price of bonds Present value of par va Current price...
##### 5, A Carnot heat engine has an efficiency of 40%. If the high temperature is raised...
5, A Carnot heat engine has an efficiency of 40%. If the high temperature is raised 10%, what is the new efficiency, keeping the same low temperature?...
##### Earth diameter is 13000 kilometers, globe diameter of0.5 meter, what is the globes scale as a ratio
earth diameter is 13000 kilometers, globe diameter of0.5 meter, what is the globes scale as a ratio. What distance on Earth would 1 cm on the globe represent?...
##### If sin x = -2/3 and x is in the third quadrant, how do you find the value of sin 2x?
If sin x = -2/3 and x is in the third quadrant, how do you find the value of sin 2x?...
##### Let X be a 4-dimensional random vector defined as X = [X1 correlation matrix X4' with...
Let X be a 4-dimensional random vector defined as X = [X1 correlation matrix X4' with expected value vector and X2 X3 E[X] =| | , 1 1 -1 0 Rx-10-11-1 0 0 0-1 1 Let Y be a 3-dimensional random vector with (a) Find a matrix A such that Y -AX. (b) Find the correlation matrix of Y, that is Ry (c) Fi...
##### Bond P is a premium bond with a coupon rate of 8.4 percent. Bond D is...
Bond P is a premium bond with a coupon rate of 8.4 percent. Bond D is a discount bond with a coupon rate of 4.4 percent. Both bonds make annual payments, have a YTM of 6.4 percent, have a par value of \$1,000, and have nine years to maturity. a. What is the current yield for Bond P? For Bond D? (Do n...
##### A gasoline mini-mart orders 24 copies of a monthly magazine. Depending on the cover story, demand...
A gasoline mini-mart orders 24 copies of a monthly magazine. Depending on the cover story, demand for the magazine varies. The mini-mart purchases the magazines for \$1.63 and sells them for \$3.78. Any magazines left over at the end of the month are donated to hospitals and other health care faciliti...
##### I seriously cannot figure this one out, im on attempt 13.. please help! Resources Ex Give...
i seriously cannot figure this one out, im on attempt 13.. please help! Resources Ex Give Up? Hint Check Answ on 7 of 14 > Attempt 1 One of the major classes of antibody molecules is immunoglobulin G (IgG). Treating IgG with papain protease cleaves the IgG molecule into two fragments, Fe and F...
##### Help S. Rowen, Inc. adds direct materials at the beginning of the process, while conversion costs...
Help S. Rowen, Inc. adds direct materials at the beginning of the process, while conversion costs are incurred uniformly throughout the process. At the beginning of the period, Work in Process Inventory was 50% complete. At the end of the period, Work in Process Inventory was 60% complete. Rowen, In...
##### Q 3: ABC Ltd., took a contract in 2018 for construction of a contract for Rs....
Q 3: ABC Ltd., took a contract in 2018 for construction of a contract for Rs. 500,000 estimation that the cost would be Rs. 460,000. At the end of the 2018, the company had received Rs. 180,000 being 90% of the work certified. Certain work not yet certified had cost of Rs. 5,000. Expenditures incurr...
##### Question 17 Given the following data: Normal distribution Mean 3 Standard deviation -1 Determine number of...
Question 17 Given the following data: Normal distribution Mean 3 Standard deviation -1 Determine number of samples out of 100 samples taken that fall within plus - minus 2 standard deviations...
##### 1. Entries for Notes Receivable Valley Designs issued a 90-day, 9% note for \$36,000, dated April...
1. Entries for Notes Receivable Valley Designs issued a 90-day, 9% note for \$36,000, dated April 19, to Bork Furniture Company on account. Assume 360 days in a year when computing the interest. a. Determine the due date of the note. b. Determine the maturity value of the note. \$ c1. Journalize the e...