May 29, 2008
Vol. 27 No. 17

current issue
archive / search
Chronicle RSS Feed

    Janos Simon, Professor in Computer Science and the Physical Sciences Collegiate Division

    Photo by Beth Rooney

    Janos Simon

    As an undergraduate in Brazil, Janos Simon took a calculus course from Abrahão de Morais, a distinguished but very busy astronomer brought in as a last-minute substitute. Lacking the normal preparation time, he often had to work out some of the proofs on the spot when teaching. “As it turned out, this became an extremely positive teaching method,” Simon said. “One could see how a great mind solves mathematical problems.”

    When teaching his undergraduate classes, Simon has sought to replicate this atmosphere of mathematical discovery in an organized fashion. The idea is to demonstrate the scientific process, not deliver a foregone result.

    “You don’t want students to go to class and become good note-takers,” said Simon, Professor in Computer Science and the Physical Sciences Collegiate Division. “You want them to become good thinkers and have them realize that this kind of thinking is really a lot of fun.”

    Simon elaborated on his approach to undergraduate instruction during a recent interview in his Ryerson Laboratory office, which overlooks the Main Quad. To him, the excitement of intellectual curiosity is vital.

    “Students learn by becoming enthusiastic about the subject matter,” he said. A good teacher should make students care about the subject, or “at least make them understand why somebody like me would be enthusiastic about it.”

    Simon teaches courses in formal languages, complexity theory and graph theory, which use mathematical models to study computation. “Some computations are hard, and we try to understand what makes them hard,” he said.

    In the field of computational complexity, one of his specialties, Simon asks what makes problems that appear to be very similar to have very different running times.

    He describes an example in which one is given a set of cities in an area with roads that connect pairs of cities. “There are two apparently similar questions: The first is, can you go through every road, in such a way that you never traverse the same road more than once? The second is, going through the existing roads, can you visit every city, never visiting any city more than once?

    Simon said there is a very efficient algorithm (essentially discovered in 1736 by mathematician Leonhard Euler) for the first question, while no fast algorithm is known for the second. Currently, the best algorithm that solves the problem exactly for 1,000 cities, running on the fastest computer, would take trillions times longer than the estimated age of the universe.

    Simon said it is not known whether there is a fast algorithm for the second problem, or whether all algorithms are prohibitively slow. “It turns out that this problem, whether there is a fast algorithm to answer our second questions, is the celebrated P vs. NP question,” Simon said. “It is a fundamental problem in Theoretical Computer Science, and there is a million-dollar prize for a correct solution. Unlike most big open problems of mathematics or physics, the statement of this question is easily explained to undergraduates.”

    Students become interested in studying Computer Science for another reason, Simon said. “Computational processes take place in many contexts other than computer programs: when children learn to speak a language, when a cell replicates its DNA, or when a person recognizes a friend on a photograph. Many biological phenomena are best understood as computational tasks.

    “The underlying process is a computational process. You can, and should, use techniques of computer science to study these phenomena. The courses I teach provide the mathematical foundations for many such techniques. So, naturally, our bright undergraduates become enthusiastic and enjoy these courses.”