Computer Science

A. K. Watson Hall, 432.1246
M.S., M.Phil., Ph.D.

Chair
Paul Hudak

Director of Graduate Studies
Drew McDermott (508 AKW, 432.1283, drew.mcdermott@yale.edu)

Professors
Dana Angluin, Ronald Coifman (Mathematics), Julie Dorsey, Stanley Eisenstat, Joan Feigenbaum, Michael Fischer, David Gelernter, Paul Hudak, Ravindran Kannan, Drew McDermott, A. Stephen Morse (Electrical Engineering), Zhong Shao (on leave), Martin Schultz, Abraham Silberschatz, Steven Zucker

Associate Professor
James Aspnes (on leave)

Assistant Professors
Daniel Friendly (Electrical Engineering), Mark Gerstein (Molecular Biophysics & Biochemistry), Arvind Krishnamurthy, Yorgis Makris (Electrical Engineering), Brian Scassellati, Carsten Schürmann (on leave), Yang Richard Yang

Adjunct Professor
Willard Miranker

Lecturer
Robert Dunne

Fields of Study
Artificial intelligence (vision, robotics, planning, computational neuroscience, neural networks); programming languages and systems (functional programming, parallel languages and architectures, programming environments, formal semantics, software engineering, compilation techniques, modern computer architecture, theorem proving and proof assistants, type theory/systems, logical frameworks, and meta-programming); scientific computing (numerical linear and nonlinear algebra, numerical solution of partial differential equations, mathematical software, parallel algorithms); theory of computation (algorithms and data structures, complexity, distributive systems, learning, online algorithms, graph algorithms, geometric algorithms, fault tolerance, reliable communication, cryptography, security, and electronic commerce); and topics of discrete mathematics with application to computer science (combinatorics, graph theory, combinatorial optimization).

Research Facilities
The department operates a high-bandwidth, local-area computer network based mainly on distributed workstations and servers, with connections to worldwide networks. Workstations include Sun SPARCstations and Workstation PCs (NT and/or Linux). A vision laboratory contains specialized equipment for vision and robotics research. Various printers, including color printers, as well as image scanners, are also available. The primary educational facility consists of thirty-seven PC workstations supported by a large Intel PC server. This facility is used for courses and unsponsored research by computer science majors and first-year graduate students. Access to computing, through both the workstations and remote login facilities, is available to everyone in the department.

Special Admissions Requirements
Applicants for admission should have strong preparation in mathematics, engineering, or science. They should be competent in programming but need no computer science beyond that basic level. The GRE General Test and a pertinent Subject Test are required.

Special Requirements for the Ph.D. Degree
There is no foreign-language requirement. To be admitted to candidacy, a student must: (1) pass twelve courses (including CPSC 690 and CPSC 691) with at least two grades of Honors, the remainder at least High Pass, including three advanced courses in an area of specialization; (2) successfully complete a research project in CPSC 690, 691, and submit a written report on it to the faculty; (3) pass written comprehensive examinations covering basic material in the major subareas of computer science; (4) pass a qualifying examination in an area of specialization; (5) be accepted as a thesis student by a regular department faculty member; (6) serve as a teaching assistant for two terms; and (7) submit a written dissertation prospectus, with a tentative title for the dissertation. At least six courses and two parts of the comprehensive examination must be completed by the end of the first year, and the remainder of the first four requirements must normally be completed by the end of the second year. In order to gain teaching experience, all graduate students are required to serve as teaching assistants for two terms during their first three years of study. All requirements for admission to candidacy must be completed prior to the end of the third year.

Master's Degrees
M.Phil. See Graduate School requirements.

M.S. (en route to the Ph.D.). To qualify for the M.S., the student must pass eight courses at the 500 level or above from an approved list. An average grade of at least High Pass is required, with at least one grade of Honors.

Master's Degree Program. Students may also be admitted to a terminal master's degree program directly. The requirements are the same as for the M.S. en route to the Ph.D. This program is normally completed in one year, but a part-time program may be spread over as many as four years.

A brochure providing additional information about the department, faculty, courses, and facilities is available from the Graduate Coordinator, Department of Computer Science, Yale University, PO Box 208285, New Haven CT 06520-8285; e-mail, cs-admissions@cs.yale.edu.

Courses
CPSC 521au, Compilers and Interpreters. Zhong Shao. MWF 1.30–2.20
Compiler organization and implementation: lexical analysis, formal syntax specification, parsing techniques, execution environment, storage management, code generation and optimization, procedure linkage, and address binding. The effect of language-design decisions on compiler construction.

CPSC 522bu, Operating Systems. Arvind Krishnamurthy. MWF 1.30–2.20
The design and implementation of operating systems. Topics include synchronization, deadlocks, process management, storage management, file systems, security, protection, and networking.

[CPSC 524au, Parallel Programming Techniques.]

CPSC 525au, Theory of Distributed Systems. Arvind Krishnamurthy. MWF 11.30–12.20
Models of asynchronous distributed computing systems. Fundamental concepts of concurrency and synchronization, communication, reliability, topological and geometric constraints, time and space complexity, and distributed algorithms.

[CPSC 529au, Functional Programming.]

CPSC 53oau, Formal Semantics. Paul Hudak. TTh 1–2.15
Introduction to formal approaches to programming language design and implementation. Topics include the lambda-calculus, type theory, denotational semantics, type-directed compilation, higher-order modules, and application of formal methods to systems software and Internet programming.

[CPSC 533b, Computer Networks.]

CPSC 534bu, Mobile Computing and Wireless Networking. Yang Richard Yang. MW 2.30–3.45
An introduction to the principles of mobile computing and its enabling technologies. Topics include principles of mobile computing; wireless systems; information management; location-independent and location-dependent computing models; disconnected and weakly connected operation models; human-computer interactions; mobile applications and services; security; power management; and sensor networks.

CPSC 537au, Introduction to Databases. Abraham Silberschatz. MWF 10.30–11.20
An introduction to database systems. Data modeling. The relational model and the SQL query language. Relational database design, integrity constraints, functional dependencies, and natural forms. Object-oriented databases. Implementation of databases: file structures, indexing, query processing, transactions, concurrency control, recovery systems, and security.

CPSC 539bu, Computer Systems. Staff. MW 2.30–3.45
The organization of computer systems as hardware and software systems. Instruction-set architecture, assembly programming, computer arithmetic, data-path architecture and control, pipelining, memory hierarchy. Concepts illustrated by exploration of an instructional RISC microprocessor. Also ENAS 907bu.

CPSC 54obu, Numerical Computation I. Vladimir Rokhlin. TTh 2.30–3.45
Algorithms for numerical problems in the physical, biological, and social sciences: solution of linear and nonlinear systems of equations, interpolation and approximation of functions, numerical differentiation and integration, optimization.

[CPSC 555bu, Economics and Computation.]

CPSC 557au, Sensitive Information in a Wired World. Joan Feigenbaum. TTh 2.30–3.45
An examination of issues of ownership, control, privacy, and accuracy of the huge amount of sensitive information about people and organizations that is collected, stored, and used by today’s ubiquitous information systems. Readings in research papers that explore both the power and the limitations of existing privacy-enhancing technologies such as encryption and “trusted platforms.”

CPSC 56obu, Theoretical Methods in Computer Science. Ravindran Kannan. TTh 1–2.15
Basic topics in theoretical computer science: machine models; fundamental algorithms and their design, implementation, and analysis; data structures; the complexity of computation, communication, and data storage.

CPSC 564bu, Quantum Computing. Willard Miranker. TTh 11.30–12.45
A tutorial introduction to quantum mechanics and computer science in the context of quantum computation. Hardware (quantum gates and data representation) and algorithms (the quantum Fourier transform, the Shor factorization algorithm, and the Grover search algorithm) are described. Discussion of topics for research.

CPSC 521au, Compilers and Interpreters. Zhong Shao. MWF 1.30–2.20
Compiler organization and implementation: lexical analysis, formal syntax specification, parsing techniques, execution environment, storage management, code generation and optimization, procedure linkage, and address binding. The effect of language-design decisions on compiler construction.

[CPSC 524au, Parallel Programming Techniques.]

[CPSC 529au, Functional Programming.]

[CPSC 533b, Computer Networks.]

[CPSC 555bu, Economics and Computation.]

Next: East Asian Languages and Literatures