EMU math department blog

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.