Computer Science

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

Chair
Paul Hudak (on leave)

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

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

Associate Professors
James Aspnes, Zhong Shao

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

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 or 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 521a^u, 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 522b^u, 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 524a^u, Parallel Programming Techniques. Arvind Krishnamurthy. MWF 11.30–12.20
Software structures, architectures, and algorithms for parallel and distributed applications, focusing on coordination frameworks for asynchronous concurrency (on the code that creates and manages multiple processes and performs the interprocess communication necessary to create integrated ensembles). Coordination languages and program-development environments. The fast-changing WAN-software picture. Parallel and distributed programming exercises on LANs. (Taught in alternate years.)

[CPSC 525a^u, Distributed Computing.]

CPSC 529a^u, Functional Programming. Carsten Schürmann. MWF 9.30–10.20
Methods for synthesizing functional programs from formal specifications and verifying correctness properties of programs. Topics include higher-order functions, pattern matching, abstract algebraic datatypes, polymorphic types, advanced typing issues such as type classes and higher-order modules, lazy/eager evaluation, equational reasoning, and realization of effects via continuations and monads. The functional languages Haskell and/or ML are used in the course. (Taught in alternate years.)

[CPSC 530^u, Formal Semantics.]

CPSC 533b, Computer Networks. Yang Richard Yang. MWF 9.30–10.20
An introduction to computer networks with emphasis in the Internet. Topics include network and protocol architectures; communication and switching techniques; link layer and local area networks; performance analysis; network layer and routing; multimedia and integrated services; flow and congestion control; and network security. (Not taught every year.)

CPSC 537b^u, Introduction to Databases. Michael Fischer. 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 539b^u, Computer Systems. Daniel Friendly. 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 907b^u.

CPSC 540a^u, Numerical Computation I. Martin Schultz. TTh 1–2.15
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 555b^u, Economics and Computation. Joan Feigenbaum. TTh 2.30–3.45
A mathematically rigorous investigation of the interplay of economic theory and computer science with an emphasis on the relationship of incentive-compatibility and algorithmic efficiency. Particular attention is paid to the formulation and solution of mechanism-design problems that are relevant to data networking and Internet-based commerce. Suitable for advanced undergraduates and beginning graduate students. Familiarity with basic microeconomics and game theory is desirable but not required. (Not taught every year.)

CPSC 560b^u, Theoretical Methods in Computer Science. Rene Peralta. TTh 2.30–3.45
This course offers an introduction to the main areas of theoretical computer science and provides a theoretical background for research in computer science. Topics from three areas: (1) complexity theory: review of machine models (Turing and RAM machines), basic complexity classes (polynomiality, nondeterminism, randomization, parallel models), measures of complexity (computational, communicational, informational); (2) algorithms and their analysis (fundamental algorithms in graph theory, number theory, sorting, and searching); (3) data structures and their role in the efficient implementation of algorithms.

CPSC 567a^u, Cryptography and Computer Security. Rene Peralta. MWF 10.30–11.20
A survey of such private and public key cryptographic techniques as DES, RSA, and zero-knowledge proofs, and their application to problems of maintaining privacy and security in computer networks. The main focus is on technology, but the course also considers such societal issues as balancing individual privacy concerns against the needs of law enforcement, vulnerability of societal institutions to electronic attack, export regulations and international competitiveness, and development of secure information systems.

CPSC 569a^u, Randomized Algorithms. Ravindran Kannan. TTh 10.30–11.45
Beginning with an introduction to tools from probability theory including some inequalities like Chernoff bounds, the course covers randomized algorithms from several areas; graph algorithms, algorithms in algebra, approximate counting, probabilistically checkable proofs, and matrix algorithms. (Not taught every year.)

CPSC 570a^u, Artificial Intelligence. Brian Scassellati. MWF 2.30–3.20
An introduction to artificial intelligence research, focusing on reasoning and perception. Topics include knowledge representation, predicate calculus, temporal reasoning, vision, robotics, planning, and learning.

CPSC 572a, AI Programming Techniques. Drew McDermott. MWF 10.30–11.20

CPSC 573b, Intelligent Robotics. Brian Scassellati. MWF 11.30–12.20
An introduction to the basic principles of building a purposeful autonomous robotic system, with an emphasis on human-machine interaction and cognitive modeling. (Not taught every year.)

CPSC 574b, Autonomous Systems. Drew McDermott. MWF 2.30–3.20
The basic principles of building a purposeful autonomous robotic system. Lectures cover the theory and practice of control systems, sensors, representation of the environment, and planning. Students construct a simulated autonomous system, and are given the opportunity to work with a real mobile robot. (Taught in alternate years.)

CPSC 575b, Computational Vision and Biological Perception. Steven Zucker. TTh 1–2.15
An overview of computational vision with a biological emphasis. Suitable as an introduction to biological perception for computer science and engineering students, as well as an introduction to computational vision for mathematics, psychology, and physiology students. Also ENAS 575b^u.

CPSC 576b^u, Computer Vision.
Computational accounts of visual perception: image formation, image transformations, line and curve extraction, segmentation, shape, stereo, motion, texture, and model-based object recognition. A review of relevant mathematical tools, algorithms, and results from studies of human vision.

CPSC 577a^u, Neural Networks. Willard Miranker. TTh 11.30–12.45

CPSC 690a or b, Independent Project I.
By arrangement with faculty.

CPSC 691a or b, Independent Project II.
By arrangement with faculty.

CPSC 692a or b, Independent Project.
Individual research for students in the M.S. program. Requires a faculty supervisor and the permission of the director of graduate studies.

CPSC 820a or b, Directed Readings in Programming Languages and Systems.
By arrangement with faculty.

CPSC 840a or b, Directed Readings in Numerical Analysis.
By arrangement with faculty.

CPSC 860a or b, Directed Readings in Theory.
By arrangement with faculty.

CPSC 870a or b, Directed Readings in Artificial Intelligence.
By arrangement with faculty.

Next: East Asian Languages and Literatures