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 (on leave [Sp]), Stanley Eisenstat (on leave [Sp]), Joan Feigenbaum (on leave), Michael Fischer (on leave [F]), David Gelernter (on leave [Sp]), Paul Hudak, Ravindran Kannan, Drew McDermott,
A. Stephen Morse (Electrical Engineering), Vladimir Rokhlin, Holly Rushmeier, Zhong Shao, Martin Schultz, Abraham Silberschatz, Steven Zucker

Associate Professor
James Aspnes

Assistant Professors
Mark Gerstein (Molecular Biophysics & Biochemistry), Arvind Krishnamurthy, Yorgis Makris (Electrical Engineering), Brian Scassellati (on leave [F]), Carsten Schürmann, Yang Richard Yang (on leave [F]), Edmund Yeh (Electrical Engineering)

Adjunct Professors
Gil Kalai, 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.  Carsten Schürmann.
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.  Abraham Silberschatz.
MW 1–2.15
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.  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 525au, Theory of Distributed Systems.]  

CPSC 528bu, Language-Based Security.  Zhong Shao.
MW 2.30–3.45
Survey of most promising LBS techniques and applications in building high-confidence embedded system software: proof-carrying code, certifying compilation and program transformation, typed intermediate and assembly languages, runtime checking and monitoring (software-based fault isolation, inclined reference monitors), high-confidence embedded operating systems and device drivers, and language support for verification of safety and liveness properties.

CPSC 529au, Functional Programming.  Paul Hudak.
MWF 10.30–11.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 530au, Formal Semantics.]  

CPSC 533b, Computer Networks.  Yang Richard Yang.
MW 2.30–3.45
An introduction to computer networks with emphasis on 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 534bu, Mobile Computing and Wireless Networking.]  

CPSC 537au, Introduction to Databases.  Abraham Silberschatz.
TTh 2.30–3.45
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.  Andreas Savvides.
TTh 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 540bu, 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.]  

CPSC 560bu, 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.]  

[CPSC 565au, Topics in Algorithms.]  

CPSC 567au, Cryptography and Computer Security.  Michael Fischer.
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 569au, Randomized Algorithms.  Ravindran Kannan.
TTh 1–2.15
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.
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.]  

CPSC 573b, Intelligent Robotics.  Brian Scassellati.
MWF 10.30–11.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.]  

CPSC 575b, Computational Vision and Biological Perception.  Steven Zucker.
MW 2.30–3.45
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 577au, Neural Networks for Computing.  Willard Miranker.
TTh 11.30–12.45
Artificial neural networks as a computational paradigm studied with application to problems in associative memory, learning, pattern recognition, perception, robotics, and other areas. Models for the dynamics of neurons and methods such as learning for designing neural networks are developed. Concepts, designs, and methods compared and tested in software simulation. Brain and consciousness studies are optional topics.

CPSC 578bu, Computer Graphics.  Holly Rushmeier.
MW 11.30–12.45
An introduction to the basic concepts of two- and three-dimensional computer graphics. Topics include affine and projective transformations, clipping and windowing, visual perception, scene modeling and animation, algorithms for visible surface determination, reflection models, illumination algorithms, and color theory. Assumes solid C or C++ programming skills and a basic knowledge of calculus and linear algebra.

CPSC 579au, Advanced Computer Graphics: Rendering Techniques.  Julie Dorsey, Holly Rushmeier.
TTh 1–2.15
A broad overview of the theory and practice of rendering. Topics include appearance capture and models; local and global illumination; surface reflection; lighting simulation algorithms; efficient rendering; image-based rendering; procedural approaches; and texture generation and rendering. Prerequisite: CPSC 478b.

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 752bu, Genomics and Bioinformatics.  Dieter Söll, Mark Gerstein, Michael Snyder.
MW 1–2.15
Genomics describes the determination of the nucleotide sequence and many further analyses to discover functional and structural information on all the genes of an organism. Topics include the methods and results of functional and structural gene analysis on a genome-wide scale as well as a discussion of the implications of this research. Bioinformatics describes the computational analysis of genomes and macromolecular structures on a large scale. Topics include sequence alignment, biological database design, geometric analysis of protein structure, and macromolecular simulation. Also MB&B 752bu, MCDB 752bu.

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