Success at 16

Using a sophisticated optimization algorithm, Natalie Nash, a 16-year-old high school junior from Pennsylvania, designed a software interface to help severely disabled users communicate significantly faster than is possible using currently available alternatives. In May, her project, which was Nash’s entry in the Intel Science and Engineering competition, wowed the three judges representing ACM, who awarded her the Association’s first prize.

"The project was both socially relevant—it was clear that it meant something to her—and it had some very impressive computer science pieces to it," says one of the judges, Robb Cutler, founding president of the Computer Science Teachers Association and a graduate student in computer science at Purdue University.

People who can’t speak use augmentative and alternative communication (AAC) devices that generate speech from users’ input. Those who can’t type, such as people with cerebral palsy, use AAC devices with a single switch through which they painstakingly make choices via an onscreen keyboard. The computer scans the AAC keyboard, highlighting one row at a time until the user activates the switch (by pressing a button, puffing, or blinking), and the device slowly zeroes in on the desired letter. "Sometimes it will take a good five minutes to type one sentence, and by that time everybody else in the conversation has moved on to another topic," Nash explains. "My project was designed to improve the speed of communication using this single-button method."

The first question Nash tackled was the fastest style of keyboard: the standard QWERTY keyboard; an AAC keyboard, which arranges the 26 letters in a 5×5 grid; or a standard ambiguous keyboard, which has more than one letter per key. Nash wrote a program to compare the three keyboards’ efficiency at processing the 20,000 most commonly spoken words in American English. Contrary to her hunch, the AAC keyboard was fastest even though the ambiguous keyboard requires traversing only nine keys instead of 26.

Knowing that the AAC keyboard reduces scanning steps by placing the most commonly used letters, such as A and E, at the top left, Nash suspected she could reduce scanning steps by rearranging the letters on an ambiguous keyboard. What’s more, all the devices use word prediction—guessing the entire word from partial input—which gave Nash an insight that helped her optimize the AAC keyboard. "It’s not necessarily the most common letters in the English language [that should be near the front], but the most common letters in the first part of the most common words, because rarely does the user have to type the actual whole word." G, for example, is very common because many words end in -ing, but users never have to enter the final g.

An exhaustive search of all possible keyboard arrangements would take forever, so Nash used the simulated annealing algorithm to find the optimal keyboard layout. "It actually turns out that I was correct. The ambiguous keyboard, when it was optimized, turned out to be a lot better than the other ones," says Nash, who calculated it is about 15% faster than an AAC keyboard.

Always interested in science, Nash got her first taste of computer programming as a third-grader participating in Carnegie Mellon University’s (CMU’s) C-MITES program for talented students. Soon enough, she was learning from her father, a CMU-educated programmer. By the time Nash could take computer science classes in high school, when she was a sophomore at Vincentian Academy, she was surprised by how much she already knew.

Although users would have to learn a new keyboard layout, an acquaintance with cerebral palsy told Nash the AAC community would embrace the new design. "Their main struggle is to be faster," says Nash, "and if it means memorizing a new keyboard, they would do it."

Back to Top