Department of Computer Science

Chair

Larry L. Peterson

Associate Chair

Perry R. Cook

Director of Graduate Studies

Bernard Chazelle

Professor

Andrew W. Appel

Sanjeev Arora

Bernard Chazelle

Douglas W. Clark

Perry R. Cook

David P. Dobkin

Edward W. Felten

Brian W. Kernighan

Hisashi Kobayashi, also Electrical Engineering

Andrea S. LaPaugh

Kai Li

Larry L. Peterson

Jennifer Rexford

Robert E. Schapire

Robert Sedgewick

Kenneth Steiglitz

Robert E. Tarjan

Jaswinder Pal Singh

Associate Professor

David I. August

Adam Finkelstein

Thomas A. Funkhouser

Mona Singh

Assistant Professor

Boaz Barak

David M. Blei

Moses S. Charikar

Fei Fei Li

Vivek S. Pai

Szymon Rusinkiewicz

Olga G. Troyanskaya, also Lewis-Sigler Institute for Integrative Genomics

David Walker

Senior Lecturer

Kevin Wayne

Lecturer

Robert M. Dondero Jr.

Associated Faculty

Ingrid C. Daubechies, Mathematics

Hisashi Kobayashi, also Electrical Engineering

Paul Lansky, Music

Ruby Lee, Electrical Engineering

Margaret Martonosi, Electrical Engineering

Jeremiah P. Ostriker, Astrophysical Sciences

Paul Seymour, Mathematics

Robert J. Vanderbei, Operations Research and Financial Engineering

Wayne Wolf, Electrical Engineering

 

The Department of Computer Science accepts both beginning and advanced graduate students for study and research leading to the degree of Master of Engineering (M.Eng.) and Doctor of Philosophy (Ph.D.). These degree programs are sufficiently flexible to adapt to individual plans of study and research. For information more detailed than that given below on degree requirements and areas of research and instruction, students are asked to write to the Director of Graduate Studies, Department of Computer Science, Princeton University, Princeton, New Jersey 08540; or to send e-mail to gradinfo@cs.princeton.edu. Information about the faculty, graduate program, and course offerings is also available on the department Web site at www.cs.princeton.edu/academics/gradpgm.

Previous Preparation

Normally, a student accepted for graduate study is expected to have completed a bachelor’s or a master’s degree in science, engineering, or mathematics; a degree in computer science is not required.

Master of Engineering

Candidates fulfill the M.Eng. degree by successfully completing eight courses taken for a grade. At least four of the eight must be at the graduate level (numbered 500 or above). Only the following undergraduate courses may count toward the fulfillment of the M.Eng. requirements: COS 318, 320, 341, and all numbered courses between 400 and 499. (See the Undergraduate Announcement for descriptions of these courses.) One of the courses may be replaced by a master’s project. The M.Eng. requirements can be completed in one year by a full-time student. A qualified student with industrial support may complete the requirements in two years on a half-time basis. (For part-time study, please see page 163.) No financial aid is provided for M.Eng. students. M.Eng. candidates interested in the Ph.D. degree must follow normal procedures for admission to the Ph.D. program.

Doctor of Philosophy

In preparation for the general examination, the doctoral candidate, in consultation with a faculty adviser, develops an integrated program of study in one of the departmental areas of research. Such preparation usually requires two academic years for students entering with a bachelor’s degree, and one year for students entering with a master’s. Although there are no formal course requirements for the Ph.D., students normally prepare for the general examination by taking the appropriate courses. In particular, enough courses should be taken so that the necessary faculty judgment on continued candidacy can be made at the end of the first year.

Before a candidate may take the general examination, two requirements must be satisfied: one is a programming requirement that can be satisfied by completing a project that involves substantial programming (under the supervision of a faculty member) or by performing well in a course that involves substantial programming (these courses are COS 318, 320, 425, 426, 429, 461, and 526, plus any graduate-level courses approved by the director of graduate studies). The other is the successful completion of a competency requirement demonstrating basic knowledge of the areas of computer systems, software systems, and theory. Students are expected to have a minimum competence in each area. A reading list is provided that covers the material the faculty considers essential for minimum competence in each area.

The general examination consists of a research seminar prepared under the supervision of a faculty member, followed by an in-depth oral examination on the contents of the seminar and the associated general area of research. The seminar is open to the public, and at least three computer science faculty members must attend. Two are invited by the student; the other is selected by the director of graduate studies. Original research results do not have to be presented, but problems whose solution may lead to a thesis should be discussed. In many cases, the student’s thesis is in the same area as the research seminar, but this is not required.

Students qualify for the Master of Arts (M.A.) degree by successfully completing the programming competency and the three basic area competencies, and presenting an acceptable research seminar.

In preparation for the final public oral examination, the candidate participates in a preliminary public oral examination to be held at least six months prior to the expected completion date. It covers results to-date and planned research, and serves as a preliminary critique of the proposed dissertation. It is attended by the adviser, two dissertation readers, and two faculty members who serve on the final public oral examination committee, and it is open to the department.

The final public oral examination is taken after the candidate’s dissertation has been accepted, and is primarily a defense of the dissertation.

Teaching experience is considered to be a significant part of graduate education. All Ph.D. candidates are therefore required to assist with course instruction.

Areas of Graduate Study

There are major research programs in architecture and compilers for high-performance systems, artificial intelligence and machine learning, complexity, computational biology and bioinformatics, computational geometry, computer graphics, computer music, data structures and combinatorial algorithms, digital libraries, human-computer interface, information and scientific visualization, multimedia, networks and operating systems, nonstandard computation, parallel and distributed systems and applications, programming languages and environments, security and cryptography, and software for high-performance systems.

Dissertation topics are selected through an informal matching of student interests with faculty expertise. Course work is a major influence, but external speakers in a regular seminar series and student interactions are also important in this process.

Fellowships and Assistantships

A number of fellowships providing tuition and a stipend for Ph.D. candidates are available each year. These fellowships, which vary in amount and detailed provisions, are supported by endowed funds and grants from foundations and corporations. No financial aid is offered to students in the M.Eng. program.

Research assistantships are available for Ph.D. students who are prepared to enter one of the research programs conducted by the department. Such research often becomes the basis for the dissertation. Teaching assistantships are available to both entering and continuing Ph.D. students. The amount of work required is consistent with a full-time graduate course program. Stipends for assistantships are fixed, as indicated in the section on awards and financial assistance found at the beginning of this catalog. Continuing support is normally recommended on the basis of satisfactory performance by the student.

Equipment and Facilities

The computer science department is located in a state-of-the-art building that houses all of its activities, including classrooms, seminar rooms and lecture halls, teaching and research laboratories, and faculty and graduate student offices.

Computer hardware and software facilities are continuously being updated to include all of the latest technology. Students have access to a variety of different types of systems, including specialized equipment in research laboratories.

Courses

COS 503 Distributed Systems

Staff

Computer communications networks and their protocols; event ordering and synchronization; deadlocks; network operating systems and languages for distributed computing; distributed databases; fault tolerance and recovery strategies; and distributed office information systems and other applications. Prerequisite: COS 425 or the equivalent.

COS 510 Programming Languages

Staff

Fundamental concepts underlying all programming languages; semantic aspects, including binding times, visibility, retention, storage management, abstraction mechanisms, and extensibility; operational and denotational semantic specifications; and design and implementation issues, particularly for very high-level languages, including data representations, control regimes, code representations, and portability. Prerequisites: COS 226 and 320.

COS 511 Foundations of Machine Learning

Robert E. Schapire

Introduces the mathematical foundations of machine learning, including theoretical models of machine learning, and the design and analysis of learning algorithms. Topics include bounds on the number of random examples needed to learn; learning from nonrandom examples in the online learning model (for instance, for investment portfolio selection); how to boost the accuracy of a weak-learning algorithm; learning with queries; Fourier-based algorithms; and support-vector machines.

COS 518 Advanced Operating Systems

Staff

Survey of operating systems covering: early systems, virtual memory, protection, synchronization, process management, scheduling, input/output, file systems, virtual machines, performance analysis, software engineering, user interfaces, distributed systems, networks, current operating systems, and case studies. Survey of research papers from classic literature through contemporary research. Prerequisite: COS 318 or the equivalent.

COS 521 Advanced Algorithm Design

Staff

Advanced methods of algorithmic design and analysis: data structures, network flows, and linear programming. Solution of linear programs: Karmarkar and Ellipsoid algorithms. Probabilistic techniques. A selection of topics from online computation, approximation algorithms for NP-hard problems, number theoretic algorithms, geometric algorithms, and parallel computation.

COS 522 Computational Complexity

Staff

Introduction to research in computational complexity theory. Computational models: nondeterministic, alternating, and probabilistic machines. Boolean circuits. Complexity classes associated with these models: NP, Polynomial hierarchy, BPP, P/poly, etc. Complete problems. Interactive proof systems and probabilistically checkable proofs: IP=PSPACE and NP=PCP (log n, 1). Definitions of randomness. Pseudorandomness and derandomizations. Lower bounds for concrete models such as algebraic decision trees, bounded-depth circuits, and monotone circuits.

COS 525 Mathematical Analysis of Algorithms

Robert Sedgewick

Methods for determining the average-case performance of fundamental algorithms; ordinary and exponential generating functions, real asymptotics, complex asymptotics, singularity analysis, and Mellin transforms; and applications to the analysis of Quicksort, hashing, binary tree search, digital search, communication protocols, multidimensional search, set merging, and other combinatorial algorithms. The course is intended to survey the major approaches and applications, and to serve as an introduction to research in the field.

COS 526 Advanced Computer Graphics

Thomas A. Funkhouser

Advanced topics in computer graphics, with a focus on learning recent methods in rendering, modeling, and animation. Appropriate for students who have taken COS 426 or the equivalent and who would like further exposure to computer graphics.

COS 527 Probabilistic Algorithms

Staff

Construction and analysis of algorithms that solve various problems efficiently in a probabilistic sense; algorithms that work almost always and for almost all inputs; expected performance of heuristic algorithms; and fundamental limitations on probabilistic computations and other complexity issues. Prerequisites: COS 423, and familiarity with probability theory.

COS 528 Data Structures and Graph Algorithms

Robert E. Tarjan

Data structures and algorithms for graph and network problems, including disjoint set union, heaps, search trees, search on graphs, minimum spanning trees, shortest paths, network flows, and matchings. The intent of the course is to examine the most efficient algorithms known for a variety of combinatorial problems and to discover the principles underlying the design and analysis of these algorithms. The emphasis is on asymptotic worst-case and amortized analysis. Prerequisite: COS 423 or the equivalent.

COS 531 Computer Graphics: Rendering

Staff

Advanced topics in image synthesis. Topics to be covered include hidden surface and visibility algorithms, material properties and reflection models, the rendering equation, and techniques for global illumination calculations, including ray tracing and radiosity algorithms. Prerequisite: COS 426 or the equivalent.

COS 532 Computer Graphics: Modeling

Staff

Advanced topics in geometric modeling. Topics to be covered include methods for describing geometric primitives such as implicit surfaces and parametric patches, solid modeling and constructive solid geometry, boundary representations and topological representations, procedural models, and models appropriate for natural and biological shapes. Prerequisite: COS 426 or the equivalent.

COS 551 Introduction to Computational Molecular Biology (also MOL 551)

Mona Singh, Saeed Tavazoie

Introduction to basic computational methods used for problems arising in molecular biology. Topics include computational approaches to sequence similarity and alignment, phylogenic inference, gene recognition, gene expression analysis, structure prediction, and whole- and cross-genome analysis.

COS 557 Analysis and Visualization of Large-Scale Genomic Data Sets (also MOL 557)

Olga G. Troyanskaya

Introduces students to computational issues involved in analysis and display of large-scale biological data sets. Algorithms covered include clustering and machine-learning techniques for gene expression and proteomics data analysis, biological networks, joint learning from multiple data sources, and visualization issues for large-scale biological data sets. No prior knowledge of biology or bioinformatics is required; an introduction to bioinformatics and the nature of biological data is provided. In-depth knowledge of computer science is not required, but students should have some understanding of programming and computation.

COS 561 Advanced Computer Networks

Jennifer Rexford

Survey of computer networks, covering end-to-end principle, multiplexing, virtualization, packet switching vs. circuit switching, router design, network protocols, congestion control, Internet routing architecture, network measurement, network management, and overlay networks. Survey of research papers from classic literature through contemporary research.

COS 576 Nonstandard Computation

Kenneth Steiglitz

Examines the physical limits of computation and nonstandard ways to compute. Topics include conservative logic, reversible computation, the thermodynamics of computing, and the essential cost of erasure, Physical Church’s Thesis, the complexity of analog computing, quantum computing, embedded computing in cellular automata, particle-based computing, soliton computing, and DNA computing.

COS 579 Pervasive Information Systems (also ELE 579)

Perry R. Cook, Wayne Wolf

Study of the nature and design of advanced information appliances, particularly multimedia-rich systems.

COS 589 Extramural Summer Research Project

Staff

Summer research project designed in conjunction with the student’s adviser and an industrial, NGO, or government sponsor that will provide practical experience relevant to the student’s research area. Start date no earlier than June 1. A final paper is required. Students considering applying for this course should review the recommended guidelines before consulting their adviser and director of graduate studies.

COS 590 Extramural Research Internship

Bernard Chazelle

One-term full-time research internship at a host institution to perform scholarly research directly relevant to a student’s dissertation work. Research objectives are determined by the student’s adviser in consultation with the outside host. Monthly progress reports and a final paper are required. Enrollment is limited to post-generals students, for one semester and one time only. Participation will be considered exceptional.

COS 591, 592 Seminar in Computer Systems

Staff

Discussion and study of problems and research results of current interest in computer systems.

COS 593, 594 Advanced Topics in the Theory of Algorithms

Staff

Topics in computational complexity, the analysis of algorithms, and other areas of theoretical computer science. Prerequisite: COS 487 or the equivalent.

COS 595, 596 Advanced Topics in Software Systems

Staff

Research-oriented topics in the design and implementation of software systems. Areas include systems for the development of large programs, programming environments, special-purpose operating systems, workstation systems, document preparation, algorithm animation, code generation and optimization, debugging, automatic programming, and program generators. Specific topics are determined by the current literature and by student and faculty interest. Prerequisites: COS 226, 318, and 320.

COS 597, 598 Advanced Topics in Computer Science

Staff

Topics involving current research in computer science and applications in other fields.

Senior Courses of Interest

The following courses, listed in the Undergraduate Announcement, may be elected by graduate students for (M.Eng.) credit and/or general examination preparation if they have not had equivalent courses before entering the department’s graduate program.

Computer Science

318 Operating Systems

320 Compiling Techniques

341 Discrete Mathematics

402 Artificial Intelligence

423 Theory of Algorithms

425 Database and Information Management Systems

426 Computer Graphics

429 Computer Vision

432 Information Security

433 Cryptography

436 Human-Computer Interface Technology

441 Programming Languages

451 Computational Geometry

461 Computer Networks

462 Design of Very Large Scale Integrated (VLSI) Systems

463 Computer-Aided Design of Digital Systems

471 Computer Architecture and Organization

487 Theory of Computation

494 Special Topics in Artificial Intelligence

495, 496 Special Topics in Computer Science