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), Stanley Eisenstat, Joan Feigenbaum, Michael Fischer, David Gelernter, Paul Hudak, Ravindran Kannan, Drew McDermott, Vladimir Rokhlin, Martin Schultz, Edward Tufte (Political Science), Steven Zucker

Associate Professors
James Aspnes, Peter Belhumeur (Electrical Engineering), Zhong Shao

Assistant Professors
Daniel Friendly (Electrical Engineering), Dana Henry (Electrical Engineering), Arvind Krishnamurthy, Yorgis Makris (Electrical Engineering), Carsten Schuermann

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 (not 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 521au, Compilers and Interpreters. Carsten Schuermann. Mon/Wed/Fri 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. Mon/Wed/Fri 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.
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 525au, Distributed Computing. James Aspnes. Mon/Wed/Fri 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 529bu, Functional Programming.

CPSC 530bu, Formal Semantics. Zhong Shao. Mon/Wed/Fri 11.30-12.20
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 537bu, Introduction to Databases. Mon/Wed/Fri 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. Daniel Friendly. Mon/Wed 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 540au, Numerical Computation I. Martin Schultz. Tues/Thurs 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 560bu, Theoretical Methods in Computer Science. Joan Feigenbaum. Tues/Thurs 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 567au, Cryptography and Computer Security. Michael Fischer. Mon/Wed/Fri 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 569bu, Randomized Algorithms.
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 570au, Artificial Intelligence. Drew McDermott. Mon/Wed/Fri 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 574b, Autonomous Systems.
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. Tues/Thurs 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 575bu.

CPSC 576bu, Computer Vision. Peter Belhumeur.
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. Also ENAS 914bu.

[CPSC 577au, Neural Networks.]

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