## Department of Computer Science

### Faculty

Sanjeev Arora David August Moses S. Charikar Bernard Chazelle Douglas W. Clark David P. Dobkin Edward W. Felten, also Woodrow Wilson School Adam Finkelstein Thomas A. Funkhouser Brian W. Kernighan Andrea S. LaPaugh Kai Li Margaret R. Martonosi Larry L. Peterson Jennifer L. Rexford Robert E. Schapire Robert Sedgewick Jaswinder Pal Singh Mona Singh, also Lewis-Sigler Institute for Integrative Genomics Robert E. Tarjan
Vivek S. Pai Szymon M. Rusinkiewicz |
Zeev Dvir, also Mathematics Rebecca A. Fiebrink Michael J. Freedman Arvind Narayanan
Donna Gabai Maia Ginsburg Joshua Hug Shiva Kintali Xiaoyan Li Christopher Moretti David Pritchard
Leonid Kruglyak, Ecology and Evolutionary Biology, Lewis-Sigler Institute for Integrative Genomics Paul Lansky, Music Ruby B. Lee, Electrical Engineering Warren Powell, Operations Research and Financial Engineering Paul D. Seymour, Mathematics Daniel L. Trueman, Music Robert J. Vanderbei, Operations Research and Financial Engineering |

### Requirements

The Department of Computer Science accepts both beginning and advanced graduate students for study and research leading to the degree of Master of Science in Engineering (M.S.E.) and Doctor of Philosophy (Ph.D.). These degree programs are sufficiently flexible to adapt to individual plans of study and research.

**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 Science in Engineering (M.S.E.)
**

**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.

All non-native English speakers who have not received a university-level degree from a U.S. college or university must pass the University's mandatory English Language Program by the end of their first year of study. Incoming students will be tested upon arrival, and may be required to participate in further English study. Students who do not pass by the end of their first year will not be readmitted.

All students must fulfill the programming and competency requirements by the end of the second year, demonstrating minimum competence in four main areas of computer science: computer systems, software systems, intelligent computing, and theory.

In addition to the general exam, two requirements must be satisfied: breadth and programming. Students are expected to complete the breadth requirement by the end of the second year. In special circumstances, a student's adviser may request an additional year, provided that four of the six courses have been completed. The programming requirement must be completed by the end of the second year.

The programming requirement can be satisfied in either of two ways—through successful completion of a project that involves substantial programming (done under faculty supervision) or by taking a course and receiving a satisfactory grade (normally B+ or higher). Acceptable courses are COS 318, 320, 425, 426, 429, 461, 526, 561, or any approved graduate course. Taking only the course exam does not give programming credit.

The breadth requirement covers four main groups: computer systems, software systems, intelligent computing, and theory. A total of six courses are required; one from each group and one additional from two of the four groups. For courses offering a final exam, students may opt to just take the final. For courses without a final, students must take the course for a grade. Credit will not be given for both the introductory and advanced versions of the same course, i.e., 318/518; 375/475; 426/526; 461/561. Acting as a teaching assistant does not give credit for that course.

A grade of A- or higher will normally be expected for exams or courses. However, all grades will be reviewed by the faculty and a lower grade may be acceptable based on a student's total record.

Individual research areas may set additional requirements for their students; they may specify certain courses to be taken or may require that courses in excess of the departmental requirement be taken.

**General Examination
**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 oral tests the student's knowledge in a number of topics relevant to the student's research area. These topics are specified beforehand by an examining committee in consultation with the student. 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. The examining committee and the student agree upon a reading list for the exam. This document is to be made available to anyone present in the oral examination, and only questions pertaining to either the material described in the document or presented during the research seminar can be asked during the oral. 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.

**M.A. Requirements
**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.

**Final Public Oral Examination
**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 public.

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

**Teaching Requirements
**Teaching experience is considered to be a significant part of graduate education. All Ph.D. candidates are therefore required to assist with course instruction for the equivalent of two terms .

**Research Areas
**The following are major research areas: bioinformatics and computational biology; computer and network systems; graphics, vision, and sound; machine learning and computational perception; programming languages and security; and theory.

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.

**Interdisciplinary Programs
**Center for Information Technology Policy

Forging ties between technologists and public policy experts, the Center for Information Technology Policy at Princeton addresses societal issues, such as privacy and security, connected to advances in computer technology. Center participants are from Princeton departments such as computer science, economics, electrical engineering, operations research and financial engineering, sociology, and the Woodrow Wilson School of Public and International Affairs.

PICASso

The Program in Integrative Information, Computer and Application Sciences (PICASso) is a graduate training program in computational science. PICASso's goal is to train a new breed of researcher who is truly interdisciplinary. Such people do research in the area between application and computer sciences, understanding both deeply enough to make contributions in each area. They also serve as bridges between communities, bringing people together and interfacing their languages and research. This is increasingly critical in a world with ever more interdisciplinary scientific needs. The PICASso vision is accomplished by providing integrative research and education training in all stages of the computational pipeline, from applications through models and methods to scalable parallel and distributed computing, storage, and visualization. In addition to weekly seminar series where students learn about computationally oriented research occurring in many different disciplines, we offer full courses spanning a range of computational topics, as well as shorter hands-on mini-courses focusing on practical skills such as parallel programming and scientific visualization.

PACM

The Program in Applied and Computational Mathematics (PACM) offers a select group of highly qualified students the opportunity to obtain a thorough knowledge of branches of mathematics indispensable for science and engineering applications, including numerical analysis and other computational methods. PACM runs a graduate program and an undergraduate certificate program.

QCB

The Program in Quantitative and Computational Biology (QCB), administered by the Lewis-Sigler Institute for Integrative Genomics , is intended to facilitate graduate education at Princeton at the interface of biology and the more quantitative sciences and computation. This is meant to include, among others, the fields of genomics, biophysics, computational neurobiology, systems biology, population biology and quantitative genetics, molecular evolution, computational biology, and microbial interactions, all of which are already of interest to faculty in the collaborating departments and the institute. Ph.D. degrees will be offered by the collaborating academic departments with some indication of the interdisciplinary nature of the thesis.

**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. M.S.E. candidates are normally self-funded, but may be offered teaching assistantships, if qualified.

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. Continuing support is normally recommended on the basis of satisfactory performance by the student.

### Courses

**Computer Science
**

**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: 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: 226 and 320.

**COS 511 Theoretical Machine Learning**

Staff

Course 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 non-random examples in the on-line learning model (i.e., 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, case studies. Survey of research papers from classic literature through contemporary research. Prerequisite: COS 318 or 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 on-line 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**

Staff

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. It 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**

Staff

Advanced topics in computer graphics, with focus on learning recent methods in rendering, modeling, and animation. Appropriate for students who have taken COS426 (or 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: 423 and familiarity with probability theory.

**COS 528 Data Structures and Graph Algorithms**

Staff

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: 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: 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: 426 or the equivalent.

**COS 551/MOL 551 Introduction to Genomics and Computational Molecular Biology**

Staff

Introduction to basic computational and genomic methods for analysis of biological systems. Topics include: sequence similarity and alignment, phylogenic inference, gene recognition, gene expression analysis, transcriptional networks, structure prediction, functional genomics and proteomics. This is primarily a graduate-level course; interested undergraduates will require permission from instructors.

**COS 557/MOL 557 Analysis & Visualization of Large-Scale Genomic Data Sets**

Staff

Introduces students to computational issues involved in analysis and display of large-scale biological data sets. Algorithms covered will 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 will be 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**

Staff

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**

Staff

Course 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, DNA computing.

**COS 579/ELE 579 Pervasive Information Systems**

Staff

Devices and systems that provide information anywhere, anytime. Goals of pervasive information: business, entertainment, government, etc. Components of pervasive information systems: low power electronics, audio/video, networking, etc. Human/computer interaction. Geographically distributed systems.

**COS 580/ELE 580 Advanced Topics in Computer Engineering**

Staff

Selected research topics in computer engineering. Emphasis is on new results and emerging areas. (More detailed outlines are contained in the booklet

*Course Outlines*, issued by the department each year.)

**COS 589 Extramural Summer Research Project**

Staff

Summer research project designed in conjunction with the student's advisor 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.

**COS 590 Extramural Research Internship**

Staff

One-term full time research internship at a host institution to perform scholarly research directly relevant to a student's dissertation work. Research objectives will be determined by the student's advisor in consultation with the outside host. Monthly progress reports and a final paper are required. Enrollment is limited to post-generals students. Students will be permitted to enroll in this one-semester course at most twice. 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

Covers recent developments in approximation algorithms. Examines a variety of different techniques: rounding solutions to linear programming relaxations, the primal-dual method, local search and semidefinite programming. Recent results on a variety of optimization problems will be chosen as illustrative examples.

**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: 226, 318, 320.

**COS 597/598 Advanced Topics in Computer Science**

Staff

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