Do you know that the keyboard we are using now is one of the slowest permutation? In the 18th centry, *Christopher Latham Sholes* developed the QWERTY layout to reduce the likelihood of jamming. However, key lever jams are never a problem now with the development of computers. But the QWETRY layout still remains using until today.

This task tries to figure out the best keyboard design format, based on typing in Finnish. (Different language also have different preference combination)The keyboard is defined as a 3*11 grid, and only considering alphabet, not punctuation.

The material provided includes:

- bigram_frequencies.mat: a MATLAB table. The value in the cell bigram_frequencies(i,j) gives you the probability that letter i is followed by letter j.
- compute_avg_wpm.m: a MATBLAB function that computes for a given layout the average typing performance achievable with that layout (think of it as a performance score). The performance is given in words per minute, where one word is defined to have 5 characters.

Note: This is the objective function that you need to optimize. - predict_MT.m: a MATBLAB function that takes two keys and predicts the time it takes to move from one key to the other, based on a Fitts’ Law model. The keys are specified by their linear index as described above.

The materials can be downloaded here: 2_2_Optimization

The task is to implement an optimization method that explores the huge amount of different keyboard layouts and finds one that maximizes the objective function given by

compute_avg_wpm.m.

My Design:

I used Greedy Search [2] method for implementing. My final result is: ‘_xgjloukpcq_zOvsaiAhb__wdretnmyf_’, and wpm = 39.0745.

Method:

- Finding max_key(1) with highest accuracy (maximize max_chance = sum(data(:,i)) ), put it in the middle of the grid ( treat the grid as a 3*11 matrix, put it at matrix(2,6) ).
- Finding max_key(2) with the highest accuracy of appearing before or after max_key(1) (maximize temp_max_chance = data(i,k) + data(k,i) ), put it beside max_key(1) ( put it at matrix(2,7) )
- Finding max_key(i) with the highest accuracy of appearing before or after max_key(1) – max_key(i-1) (maximize temp_max_chance = sum (data(i,j) + data(j,i)) ), put it closest to the previous keys. See figure 3:

Reference:

[1] Computer Keyboard, Wikipedia. http://en.wikipedia.org/wiki/Computer_keyboard

[2] Greedy search. http://en.wikipedia.org/wiki/Greedy_algorithm