EMU math department blog

Last semester I wrote about Emacs Psychiatrist, a cute computer program that tries to have “intelligent” conversations with the user. If you talk to the program for several minutes, you quickly discover that it is not so intelligent. Can a more complicated computer program behave better? In computer science we use Turing test to test weather a computer program achieved any intelligence. The idea is very simple—if you cannot tell what a computer program produces from what a human produces, then we say this computer program achieved a certain level of human intelligence.

Here is a toy Turing test I got from www.cs4fn.org. One of the following two sentences is produced by a computer program. Can you tell which one it is?

1. What’s fast and wiry?… An aircraft hanger!
2. What’s green and bounces?… A spring cabbage!

CS 101/102 “Introduction to Computers” is offered every semester as an introductory course to non-majors. The title of the course is kind of misleading. We will probably have the name changed to “Introduction to Computer Science” instead.

Many people have flawed images for CS in their minds. In fact CS is much more exciting and fun than what most people think. In this course we intend to introduce to students various areas of computer science, such as artificial intelligence, computer graphics, databases, computer network, and more. These are areas which have great influences on every aspect of our daily lives. If you want to know how people make 3-D animation movies, or how an iRobot vacuum does its job, or how your financial information is stored and processed, take this course in the future.

Wondering around in Washington zoo last summer, I suddenly saw the name “EMU”. “How does EMU have anything to do with Washington zoo?” I was suprised, “Is the biology department running a joint project with the zoo?”. Looking carefully, I realized that it was EMU the bird, the largest bird native to Australia.

Out of curiosity, I googled the term “EMU” to find out who Google thinks deserves this name the most. Google uses a PageRank algorithm (a more detailed description here) to rank their search results. It is one of the core algorithms that make the Google search engine popular. To my delight, currently we are the number two link in Google research results, beating Eastern Michigan University, EMU the bird, and lots of others.

See you next semester.

Nathan Swatrentruber, Annette Lolchoki, and Paul Rutt did a nice little project in my software engineering class this semester. They worked on finding a solution to improve or replace the current EMU web survey software. According to EMU institutional research, the current software lacks many functionality and survey management features.

The group set up a private wiki page to collaborate. After studying and comparing a dozen popular commercial web survey software, the group concluded that it would be better to adopt one of the commercial software than improving what EMU is using. In their final presentation, available online in Google Docs format, they made their recommendations for several price ranges.

Donald Knuth is one of the computer scientists I admire. He has been called the father of algorithm analysis. His multi-volume books, The Art of Computer Programming, were first published in 1968 and still considered must-have in a theoretical computer scientist’s bookshelf. He is the creator of the Tex computer typesetting system, which I used to write all my research papers. He won the Turing award, the most prestigious award in computer science, in 1974. We even set up a prize named after him, the Knuth Prize.

As a Christian, Knuth appreciated the richness and depth of the Bible. Once when he led a Bible class at his church, he decided to use a “scientific approach” to study the Bible. In science, stratified sampling is an effective way to gain knowledge about complicated things. The idea is as follows: a large body of information can be comprehended reasonably well by studying more or less random portions of the data. In order to have a pretty good understanding about the Bible within a reasonably short amount of time, Knuth chose to study carefully and thoroughly Chapter 3, verse 16 of every book in the Bible. The reason he selected this particular verse is because of the great popularity of John 3:16.

His Bible class was a huge success at the church. Knuth found that almost every verse, not just John 3:16, is fascinating and full of historical and spiritual insights. His experience was so inspiring that he decided to write a book about it — 3:16 Bible Texts Illuminated. I enjoy reading this book very much. You may check out this book from EMU library.

His “God and Computers” lectures at MIT in 1999 turned into another book — Things a Computer Scientist Rarely Talks About. It is not available in EMU library, but you may drop by my office to browse through my personal copy.

Graph theory is one of the topics in discrete mathematics. It is also important for a CS major to know some graph theory since many real-life problems concerning computer networks and computer circuit design are in fact problems in graph theory.

A planar graph is a graph that can be drawn on a piece of paper without any edge crossing. It is especially important in areas of computer engineering such as VLSI design. Determining whether a given graph is planar is not hard, but finding the planar drawing of a planar graph can be quite time consuming — check out the planarity game. It took me about five minutes to finish the first three levels, then the game gets more challenging…

Eliezer Hernandez (Senior, CS major), Michael Showatter (Sophomore, Math Ed major) and I formed a team called “EMU” to compete for the netflix prize.

Netflix offers one million dollar for an algorithm which is able to improve the performance of their current movie recommendation algorithm by 10%. They use the RMSE score to measure the performance of an algorithm. Any algorithm that produces a RMSE score of lower than or equal to 0.8563 will win.

We have tried out some simple approaches. We have lowered our RMSE score from the original 1.7686 to 1.0536 (Good job! Eliezer and Michael.). The team of researchers from AT&T labs has the current best score 0.8705. For now we are trying to understand and implement their ideas. We should be able to spend more time on it during the winter break.

I have to say the chance for us to win the prize is slim. The important thing is not to win the money but the valuable experiences one gains along the way. Plus, it is a nice feeling to compete with teams all around the world, probably from every top university. And if we do win, we promise to donate at least half of the money to help build the new science center :-).

In the future I would like to see more math/cs students exhibiting such enthusiasm and energy.

Stephen Wolfram is a famous theoretical physicist, mathematician, and computer scientist. He is the inventor of Mathematica. His ground-breaking book, A New Kind of Science, presents a new way, other than traditional mathematics, to model and understand the complexity of nature. I will write about this book in a future post. Today I would like to talk about the simplest Turing machine.

For a long time computer scientists are puzzled with the question, “Can we simplify the structure of a computer as much as possible and still retain all the computing power of a computer?” In another words, “What is the simplest theoretical computer, or Turing machine?” Turing machine is a theoretical computational model. Although it can do all the computing tasks a modern computer does, it will take a much longer time to do it. In reality people will never build and use a Turing machine.

Wolfram is interested in finding the simplest Turing machine. On May 14, 2007, Wolfram announced a $25,000 prize for a proof of whether a 2-state, 3-color Turing machine is the simplest Turing machine. Amazingly, the prize was won only five months later by Alex Smith–a 20-year-old undergraduate from Birmingham, UK. I guess sometimes it just takes courage and a reasonable math training to solve an open problem posted by one of the world’s most well-known scientists.

Read detailed stories from Nature, Scientific American, and Wolfram’s blog.

As we get into the second half of the semester and the winter is coming, you may feel a little bit down occasionally. What can you do to keep your spirit up? You may register a free session at EMU counseling service, or you may try to have a computer program be your counselor.

Emacs is one of computer programmer’s favorite text editors. It comes with a cute program called Emacs Psychiatrist. This program was designed using ideas in Artificial Intelligence to behave like a human Psychiatrist. To talk to Emacs Psychiatrist, go to V drive, go to the folder V:\Zhang\emacs-21.3\bin, and double click the file “emacs.exe”. Emacs Psychiatrist is the last item under the help menu. Remember to press the Enter key twice each time when you finish talking.

Pedagogy Technician

The Pedagogy Technician will be responsible for generating reports using Excel, Ouickbase and the CDT. The ideal intern will be a strong team player while working in a fast paced environment with many diverse teams. Other requirements include being able to learn technology quickly, attentive to detail, self-motivated and the ability to follow complex instructions while working on numerous projects.

Send resumes or questions to Katelynn McGinnis, HR Assistant, (540)236-5497, kmcginnis@rosettastone.com.