Computer Science
A. K. Watson Hall, 432.1246
www.cs.yale.edu/
M.S., M.Phil., Ph.D.
Chair
Abraham Silberschatz
Director of Graduate Studies
Drew McDermott (508 AKW, 432.1283, drew.mcdermott@yale.edu)
Professors
Dana Angluin (on leave [Sp]), James Aspnes, Ronald Coifman (Mathematics), Julie Dorsey (on leave [F]), Stanley Eisenstat (on leave [Sp]), Joan Feigenbaum (on leave [Sp]), Michael Fischer (on leave [F]), David Gelernter, Paul Hudak, Ravindran Kannan (on leave), Drew McDermott (on leave [F]), A. Stephen Morse (Electrical Engineering), Vladimir Rokhlin, Holly Rushmeier, Martin Schultz, Zhong Shao, Abraham Silberschatz, Daniel Spielman, Steven Zucker
Associate Professors
Mark Gerstein (Molecular Biophysics & Biochemistry), Yorgis Makris (Electrical Engineering), Brian Scassellati (on leave [F]), Yang Richard Yang, Edmund Yeh (Electrical Engineering)
Assistant Professor
Michael Mahoney (Applied Mathematics)
Adjunct Professors
Gil Kalai, Willard Miranker
Senior Lecturer
Robert Dunne
Fields of Study
Artificial intelligence (vision, robotics, planning, computational neuroscience, knowledge representation, neural networks); programming languages (functional programming, parallel languages and architectures, programming environments, formal semantics, compilation techniques, modern computer architecture, type theory/systems, and meta-programming); systems (databases, operating systems, networks, software engineering); 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 Dell dual-processor PCs (running Linux or Windows/XP). Laboratory contains specialized equipment for graphics, 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) take six advanced courses in areas of general computer science; (3) successfully complete a research project in CPSC 690, 691, and submit a written report on it to the faculty; (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. To satisfy the distribution requirement (clause 2 above), the student must take one course in programming languages or systems, one programming-intensive course, two theory courses, and two in application areas. 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 Degree 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.
MW 1–2.15
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. Zhong Shao.
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 524bu, Parallel Programming Techniques. David Gelernter.
TTh 1–2.15
Software structures, architectures, and algorithms for parallel and distributed applications, focusing on coordination frameworks for asynchronous concurrency (on the code, that is, that creates and manages multiple processes and performs the inter-processes 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.
CPSC 525au, Theory of Distributed Systems. James Aspnes.
MWF 2.30–3.45
Models of asynchronous distributed computing systems. Fundamental concepts of a concurrency and synchronization, communication, reliability, topological and geometric constraints, time and space complexity, and distributed algorithms.
CPSC 530au, 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 531a, Fundamentals of Computer Music.]
CPSC 533b, Computer Networks. Yang Richard Yang.
MW 2.30–3.45
An introduction to the design, implementation, analysis, and evaluation of computer networks and their protocols. Topics include layered network architectures, applications, transport, congestion, routing, data link protocols, local area networks, performance analysis, multimedia networking, network security, and network management. Emphasis on protocols used on the Internet.
[CPSC 534au, 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.]
CPSC 540bu, Numerical Computation I. Vladimir Rokhlin.
MW 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 545b, Introduction to Data Mining. Martin Schultz.
TTh 2.30–3.45
A study of algorithms and systems that allow computers to find patterns and regularities in databases, to perform prediction and forecasting, and to improve their performance generally through interaction with data.
CPSC 562a, Graphs and Networks. Daniel Spielman.
TTh 2.30–3.45
A mathematical examination of graphs and their applications in the sciences. Families of graphs include social networks, small-world graphs, Internet graphs, planar graphs, well-shaped meshes, power-law graphs, and classic random graphs. Phenomena include connectivity, clustering, communication, ranking, and iterative processes.
CPSC 565b, Topics in Algorithms. James Aspnes.
MWF 11.30–12.25
Introduction to the fundamental tools used in approximation algorithms: linear, convex, and semi-definite programming; dynamic programming; and geometric tools. Recent progress in the design of approximation algorithms for graph problems, combinatorial problems, and other NP-hard optimization problems. Results on the hardness of approximation based on probabilistically checkable proofs.
[CPSC 567au, Cryptography and Computer Security.]
CPSC 568au, Introduction to Computational Complexity. Joan Feigenbaum.
TTh 1–2.15
Introduction to the theory of computational complexity. Basis complexity classes, including polynomial time, nondeterministic polynomial time, probabilistic polynomial space, logarithmic space, and nondeterministic logarithmic space. The roles of reductions, completeness, randomness, and interaction in the formal study of computation.
[CPSC 569bu, Randomized Algorithms.]
[CPSC 570au, Artificial Intelligence.]
CPSC 573b, Intelligent Robotics. Brian Scassellati.
MWF 10.30–11.20
An introduction to the construction of intelligent, autonomous systems. Sensory-motor coordination and task-based perception. Implementation techniques for behavior selection and arbitration, including behavior-based design, evolutionary design, dynamical systems, and hybrid deliberative-reactive systems. Situated learning and adaptive behavior.
CPSC 575b, Computational Vision and Biological Perception. Steven Zucker.
MW 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 577au, Neural Networks for Computing. Willard Miranker.
TTh 11.35–12.50
Artificial neural networks as a computational paradigm studied with application to problems in associative memory, learning, pattern recognition, perception, robotics, and other areas. Development of models for the dynamics of neurons and methods such as learning for designing neural networks. Concepts, designs, and methods compared and tested in software simulation. Brain and consciousness studies are optional topics.
CPSC 578bu, Computer Graphics. Holly Rushmeier.
TTh 1–2.15
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 579bu, Advanced Computer Graphics: Rendering Techniques. Holly Rushmeier.
MWF 2.30–3.45
An in-depth study of advanced algorithms and systems for rendering, modeling, and animation in computer graphics. Topics vary and may include relectance modeling, global ilumination, subdivision surfaces, NURBS, physically based fluids systems, and character animation.
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 CB&B 752b, 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
|
