ABC Book
T: Theory of computing
       
S-T pdf (504 KB): click pic
Preface A B C D E F G H I J K L M N O P Q R S T U V W X Y Z Pics

 
Teaching OO using Java
Calculational
logic
festive occasions
ABC book
CS Faculty over the years
CS@Cornell
The Triple-I Administration
How Bush Operated

 

 

T ’s for Computing —the Theory thereof.
Our first chair Hartmanis started it off.
Profs at Cornell helped push it aloft,
Like Constable, Kozen, and John E. Hopcroft.
But Theory is not simply what those profs do,
It’s a tool, a way of thinking for me and you.
When understanding and advance would appear very tough
Theory provides the path through the rough.

The year Juris Hartmanis became Chair of our new CS department, 1965, he published a paper with Richard Stearns that introduced a new field and gave it its name: Computational Complexity. That, together with John Hopcroft’s (joined in 1967) work in automata, formal languages, and algorithms and Bob Constable’s (1968) work in subrecursive function theory and logic and mathematical reasoning established Cornell as one of the best places for theoretical work in computing.

In the early days, most faculty in CS believed in the use of theory to make advances, when it made sense to do so —be it programming language design, semantics, operating systems, information retrieval, or numerical analysis— and this contributed to our long-lasting cohesiveness.

This understanding of the use of theory continues today. Look, for example, at Bart Selman, an AI guy, who worked with physicists to unearth phase transitions, like water freezing, in certain instances of the Satisfiability problem in computational complexity. In data mining, the science of networks, language-based security, mission critical systems —in these fields and more, our strengths can be traced to theoretical and practical people working side by side, or to people who refuse to be called “theoretical” or “practical” because they are both.

Our undergrad majors get a heavy dose of theory of computing, and it pays off. We continue to hear from those that go on to grad school in CS that others struggle with theory while they have no problem.