Walter J. Savitch
Prof Emeritus, Computer Science and Engineering
Complexity theory, formal language theory, computational linguistics, and the development of computer science education materials.
Professor Savitch is well know for his work in complexity theory, which includes the first example of a complete language, namely a language complete for the storage class log n. This fundamental work led directly to the now widespread interest in complete problems. Savitch's research interests include computational complexity of parallel programs, with an emphasis on automatically converting serial complexity bounds to parallel complexity bounds. He has also done important work on the theories of nondeterministic and parallel computation models. Savitch's recent interests have centered on formal and computational linguistics and on computer-science education. His work on formal models for computational linguistics includes projects on models for reduplication phenomena in natural language and the use of descriptive complexity in concept formation. He is the author of numerous textbooks, including "Java: An Introduction to Computer Science Programming" (Prentice-Hall, 2nd Edition, 2002); "Absolute C++" (Addison-Wesley, 2002) and "Problem Solving: The Object of Programming" (Addison-Wesley, various editions).
Walter Savitch joined the UCSD faculty in 1969, after receiving his Ph.D. in Mathematics from UC Berkeley that same year. He did his undergraduate work at the University of New Hampshire in Durham. Savitch served as director of the Interdisciplinary Ph.D. Program in Cognitive Science at UCSD for over ten years. He has served as a visiting researcher in the computer science departments of the University of Washington in Seattle, University of Cincinnati, and the University of Colorado in Boulder, and has been a visiting scholar at the Netherlands' Centrum voor Wiskunde en Informatica in Amsterdam.