Elaine Rich

Senior Lecturer
The University of Texas at Austin
Taylor 3.126
ear@cs.utexas.edu
Office Hours (resuming when school starts): W 2:30 - 3:45 Taylor 3.126

 

 

 

Recent, Current and Upcoming Classes

My most recent project is a book entitled Automata, Computability and Complexity: Theory and Applications. It was published by Prentice-Hall in September, 2007. The theoretical underpinnings of computing form a standard part of almost every computer science curriculum. But the classic treatment of this material isolates it from the myriad ways in which the theory influences the design of modern hardware and software systems. My new book changes that.

The main part of the book is organized in the standard way: it begins with finite state machines and regular languages. Next it covers context-free languages and it contains an optional chapter on context-free parsing techniques. Then it introduces Turing machines (and several equivalent models of computation) and the question of undecidability. Finally, it considers the problem of practical computability by introducing time and space complexity classes. For more detail, see the Table of Contents.

Throughout the book there are links to applications of the key concepts. A substantial appendix describes many of those applications and pointers to the book's website describe others. Programming languages, compilers, networking, natural language processing, artificial intelligence, computational biology, security, and games are among the applications that are discussed.

Instructors who choose to use the book in their classes have access (through the Prentice-Hall site) to a collection of resources designed to make it easy to teach from the book. There is a complete set of Powerpoint slides, as well as answers to most of the problems in the book and a set of additional problems (most with solutions) that can be used for homeworks and exams.

 

 

 

I got a Ph.D. in CS in 1979 from CMU, with a dissertation, entitled Building and Exploiting User Models. In that work, I showed that stereotypes (models of groups of users who share common interests or characteristics) could be effectively exploited by a system (mine was named Grundy) that gives advice to people on things they might like. Grundy recommended novels to people, but the same ideas can be used to recommend everything from music to cars. Two papers, one in IJMMS and one in Cognitive Science, describe this work.

Grundy exploited relatively deep models, both of the books it knew and of its users. This meant that the models of the individual books had to be created by hand. And what about the models of each user? The goal, in designing Grundy, was to minimize the amount of interaction a user would have to have with Grundy in order to get going. To achieve that goal, Grundy used stereotypes, which could be triggered for a particular person just from a small set of words that the person provided as a simple self description. Grundy generated book recommendations by comparing its model of the current user to the models of the books it knew about. It chose the best match and generated a short description of the book, which emphasized the reasons it thought this user would like the book. Then it asked the user whether it liked the recommendation, and, if not, why not. Using that feedback, it updated both its stereotypes and its model of the current user.

Grundy's approach contrasts with the now common technique known as collaborative filtering. In this latter approach, the only thing that the system (for example, Amazon.com) knows about its books is who bought them. The only thing it knows about an individual is what books he or she has bought. It knows no reason why the person likes those particular books. But it does know thousands of other people who liked the same books and it knows which other books those people liked. So it can recommend new books to a current user without any deep model either of the user's preferences or of the books. Collaborative filtering systems substitute a massive, shallow database for Grundy's smaller, deeper one.

While at CMU, I also did a small project on the differences between men and women in their use of color terms. Not surprisingly, women, on average, use a wider array of color expressions than men do. See Sex-Related Colour Vocabulary for the details.

When I left CMU, I moved to Austin to teach in the Computer Sciences department at The University of Texas. The first thing that happened there was that I had to give up knitting (they really don't have winter in Texas), but I eventually found something even better (see below). In the mean time, I wrote an Artificial Intelligence text book, which later came out in a second edition coauthored with Kevin Knight. The first edition appeared as number 21 in a list of classic CS books published in the March issue of CACM.

 

 

In the mid 80's, a noble experiment called MCC was launched in Austin. The goal of MCC was to get more bang per buck out of industrial research dollars by bringing companies withoverlapping research needs together into a consortium that would conduct research and do tech transfer back to the sponsoring companies. Things didn't quite work out that way, but I spent several years at MCC working on natural language processing and on techniques for building intelligent human interfaces.

Now I'm back at UT, among other things teaching Automata Theory (CS341) and Artificial Intelligence (CS 343).

Quilting

Sometime in the post knitting void, soon after finishing the second AI book, I discovered quilting and got hooked. I can't talk about my quilting, though, without pictures. So if you've got the time to download some really nice photos, click on the quilt to visit my quilting page.

 

 

Expanding Your Horizons

In the early 1990's a small group of us formed a local nonprofit corporation,Tomorrow's Women in Science and Technology (TWIST). TWIST's goal has been to encourage girls and women to continue their education in math and science and to consider scientific and technical careers. TWIST's main activity was to organize Expanding Your Horizons workshops for middle school aged girls to try to keep them interested in math and science. We chose to target this age group because a large body of research shows that just at the start of adolescence, girls, for some reason, start tuning out tomath and science. EYH conferences bring the girls together for a day of fun, hands-on workshops that give them glimpses of all kinds of careers that rely on good backgrounds in science and math. In 2006, Girlstart took over responsibility for the Austin EYH program, which continues under their leadership and with sponsorship by the University of Texas College of Natural Sciences.

 

Links to Random Presentations I've Put on the Web

 

Last revised: June 10, 2008.