Department of Computer Science - A.B.

Faculty

  • Chair

    • Jennifer L. Rexford
  • Director of Undergraduate Studies

    • Brian W. Kernighan
    • Jaswinder Singh
  • Director of Graduate Studies

    • Michael J. Freedman
    • Benjamin J. Raphael
  • Professor

    • Ryan P. Adams
    • Andrew W. Appel
    • Sanjeev Arora
    • David I. August
    • Mark Braverman
    • Bernard Chazelle
    • David P. Dobkin
    • Edward W. Felten
    • Adam Finkelstein
    • Michael J. Freedman
    • Thomas L. Griffiths
    • Aarti Gupta
    • Elad E. Hazan
    • Brian W. Kernighan
    • Kai Li
    • Margaret R. Martonosi
    • Benjamin J. Raphael
    • Ran Raz
    • Jennifer L. Rexford
    • Szymon M. Rusinkiewicz
    • Robert Sedgewick
    • H. Sebastian Seung
    • Yoram Singer
    • Jaswinder P. Singh
    • Mona Singh
    • Robert E. Tarjan
    • Olga G. Troyanskaya
    • David P. Walker
  • Associate Professor

    • Zeev Dvir
    • Barbara Engelhardt
    • Kyle A. Jamieson
    • Arvind Narayanan
  • Assistant Professor

    • Danqi Chen
    • Jia Deng
    • Felix Heide
    • Zachary Kincaid
    • Gillat Kol
    • Amit A. Levy
    • Wyatt A. Lloyd
    • Jonathan R. Mayer
    • Karthik Narasimhan
    • Olga Russakovsky
    • Seth M. Weinberg
    • Mark L. Zhandry
  • Lecturer with Rank of Professor

    • Robert E. Schapire
  • Senior Lecturer

    • Kevin Wayne
  • Lecturer

    • Ibrahim Albluwi
    • Robert M. Dondero
    • Robert S. Fish
    • Donna S. Gabai
    • Maia Ginsburg
    • Alan Kaplan
    • Daniel N. Leyzberg
    • Xiaoyan Li
    • Soohyun Niam Liao
    • Jeremie Lumbroso
    • Christopher M. Moretti
    • Soohyun Nam Liao
    • Iasonas Petras
  • Instructor

    • Sahil Singla

     

Program Information

Information and Departmental Plan of Study

The Department of Computer Science curriculum encourages students to learn fundamental concepts of the discipline and to become proficient in the use of advanced computer systems. The plan provides opportunities for study in software systems, algorithms and complexity, machine architecture, computer graphics, programming languages, machine learning, and other core areas of computer science. Most computer science students enjoy programming and are given ample opportunity to do so within the curriculum.

Information for First-Year Students. Students with a general interest in the sciences or engineering are encouraged to take COS 126 in the first year or in the first semester of the second year. This provides useful background for applications work in any science or engineering major and preserves the option of later electing a computer science major.

Prerequisites

The prerequisites for AB candidates are MAT 103, 104, and 202 or 204 or 217 ; COS 126; COS 217 and 226. Students should plan to take both 217 and 226 before the junior year. One or both of these are required prerequisites for all later computer science courses.

Departmental Requirements

Eight additional departmental courses at or above the 300 level must be elected to fulfill the departmental requirements.  These eight courses must include two each from the following three areas:

Theoretical computer science:
340 Reasoning about Computation
423 Theory of Algorithms
433 Cryptography
445 Networks, Economics and Computing
451 Computational Geometry
487 Theory of Computation
488 Introduction to Analytic Combinatorics
510* Programming Languages
511 Theoretical Machine Learning 
516* Reasoning About Software
533** Advanced Cryptography
*If a student takes COS 510  and COS 516 only one will count as a theory requirement.
**If a student takes COS 433 and COS 533 only one will count as as a theory requirement.

Systems:
306 Introduction to Logic Design (see ELE 206)
316 Principles of Computer System Design
318 Operating Systems
320 Compiling Techniques
333 Advanced Programming Techniques
375 Computer Architecture and Organization
418* Distributed Systems
425 Database and Information Management Systems
461** Computer Networks
463 Wireless Networks
475 Computer Architecture (see ELE 475)
518* Advanced Computer Systems
561**Advanced Computer Networks
*If a student takes COS 418 and COS 518 only one will count as a systems requirement.
**If a student takes COS 461 and COS 561 only one will count as a systems requirement. 

Applications:
314 (MUS 314) Computer and Electronic Music through Programming, Performance, and Composition 
323 Computing and Optimization for the Physical and Social Sciences (see ORF 363)
324 Introduction to Machine Learning
326 Functional Programming
343 Algorithms for Computational Biology
360 Computational Models of Cognition
401 Introduction to Machine Translation (see TRA 301)
402 Machine Learning and  Artificial Intelligence
424 Fundamentals of Machine Learning
426* Computer Graphics
429 Computer Vision
432 Information Security
436 Human-Computer Interface Technology 
455 Introduction to Genomics and Computational Molecular Biology (see MOL 455)
484 Natural Language Processing
485 Neural Networks
526* Advanced Computer Graphics
*If a student takes COS 426 and COS 526 only one will count as an applications requirement.

On occasion, certain courses at the 300-or-above level with sufficient computational content taught outside the Department of Computer Science may count as COS departmentals. For information on such courses, see the Department of Computer Science requirements webpage.

Students should consult with a computer science academic adviser on their course selections after they decide to become computer science concentrators. Academic advisers are listed on the Department of Computer Science webpage.

Independent Work

All A.B. concentrators engage in independent work supervised by a member of the department. A junior project normally involves the study and solution of specific problems in Computer Science. The goal may be the solution of a research question or the entrepreneurial design of an application.  Students may work within the context of a faculty research project.  It may require a significant programming effort,  or a theoretical study. The results of these efforts must be presented in two written reports and posters that correspond to the work undertaken in each of the terms. The senior thesis may be a study in greater depth of one of the subjects considered in junior independent work, or it may deal with another aspect of computer science and its application.

The department also offers a curriculum leading to the B.S.E. degree. The primary differences between the A.B. and the B.S.E. programs are in the general requirements for the degree programs, and the nature and extent of independent study

Senior Departmental Examination

An oral examination, consisting of a defense of the thesis research, will be held in late April or early May.

Integrated Science Sequence

An alternative path into the department is through the integrated science curriculum. ISC/CHM/COS/MOL/PHY 231-4 (a double course) can be taken in the first year and ISC/CHM/COS/MOL/PHY 235/6 can be taken in the sophomore year. These courses can be substituted for CHM 203/204, PHY 103/104 or 105/6, and COS 126 in the first year and MOL 214, 342, and 345 in the sophomore year. For full course descriptions and more information, see the integrated science website.

Interdisciplinary Studies

The pervasive nature of modern computing has introduced many interactions between computer science and other disciplines. Basic preparation in computer science is valuable for a broad variety of careers because of the central role played by the computer in society. Professionals who understand computers are far more effective in their work. In the past, a large amount of technical preparation was required before interesting applications could be considered; today's undergraduates are able to use computers to study important problems in other disciplines.

Some possible areas for interdisciplinary study are: mathematics, music, art, economics, electrical engineering, molecular biology, neurosciences, and linguistics.

Many Princeton undergraduates view their four years at Princeton as an opportunity to gain an education before immersing themselves in rigorous training for careers in law, business, or medicine. Computer science students are no exception. Through the choice of electives, students may create a specialized interdisciplinary program or a broad program with computer science as the core of pre-professional study. The former requires consultation with advisers in the related disciplines to determine what constitutes a reasonable cognate specialization, and the latter is constrained by the requirement of a coherent program of concentration.

Program in Applications of Computing. Students pursuing some other major field of study, but who are interested in the applications of computer science to that field, may wish to consider the Program in Applications of Computing.

Certificate Programs and a concentration in Computer Science.  Students often combine their concentration in Computer Science with participation in a certificate program, and have selected a wide variety of programs - from Ancient Roman Language and Culture to Entrepreneurship.  We highlight some interdisciplinary programs that involve computer science.  A complete list of certificate programs can be found in the 2019-2020 Undergraduate Announcement.

Program in Applied and Computational Mathematics

Program in Cognitive Science draws on psychology, philosophy, linguistics, neuroscience, and computer science to study how the mind works

Program in Engineering and Management Systems prepares students for careers in management, consulting or public policy.

Program in Entrepreneurship

Program in Finance

Program in Linguistics

Program in Music Performance

Program in Neuroscience is the study of the brain and draws from several disciplines, including computer science

Program in Quantitative and Computational Biology

Program in Robotics and Intelligent Systems

Program in Statistics and Machine Learning focuses on methods of data analysis

Program in Technology and Society includes an Information Technology track addressing societal concerns such as information security and privacy

 

Courses

COS 109 Computers in Our World (also
EGR 109
) Fall QR

Computers are all around us. How does this affect the world we live in? This course is a broad introduction to computing technology for humanities and social science students. Topics will be drawn from current issues and events, and will include discussion of how computers work, what programming is and why it is hard, how the Internet and the Web work, security and privacy. Two 90-minute lectures. Self-scheduled computer laboratory. Instructed by: B. Kernighan

COS 126 Computer Science: An Interdisciplinary Approach (also
EGR 126
) Fall/Spring QR

An introduction to computer science in the context of scientific, engineering, and commercial applications. The course will teach basic principles and practical issues, and will prepare students to use computers effectively for applications in computer science, physics, biology, chemistry, engineering, and other disciplines. Topics include: hardware and software systems; programming in Java; algorithms and data structures; fundamental principles of computation; and scientific computing, including simulation, optimization, and data analysis. No prior programming experience required. Video lectures, one or two classes, two preceptorials. Instructed by: R. Sedgewick

COS 217 Introduction to Programming Systems Fall/Spring QR

An introduction to computer organization and system software. The former includes topics such as processor and memory organization, input/output devices, and interrupt structures. The latter includes assemblers, loaders, libraries, and compilers. Programming assignments are implemented in assembly language and C using the UNIX operating system. Three lectures. Prerequisite: 126 or instructor's permission. Instructed by: J. Rexford

COS 226 Algorithms and Data Structures Fall/Spring QR

This course surveys the most important algorithms and data structures in use on computers today. Particular emphasis is given to algorithms for sorting, searching, and string processing. Fundamental algorithms in a number of other areas are covered as well, including geometric algorithms, graph algorithms, and some numerical algorithms. The course will concentrate on developing implementations, understanding their performance characteristics, and estimating their potential effectiveness in applications. Two online lectures, two class meetings, one precept. Instructed by: K. Wayne

COS 231 An Integrated, Quantitative Introduction to the Natural Sciences I (See ISC 231)

COS 232 An Integrated, Quantitative Introduction to the Natural Sciences I (See ISC 232)

COS 233 An Integrated, Quantitative Introduction to the Natural Sciences II (See ISC 233)

COS 234 An Integrated, Quantitative Introduction to the Natural Sciences II (See ISC 234)

COS 306 Contemporary Logic Design (See ELE 206)

COS 314 Computer and Electronic Music through Programming, Performance, and Composition (See MUS 314)

COS 318 Operating Systems Fall

A study of the design and analysis of operating systems. Topics include: processes, mutual exclusion, synchronization, semaphores, monitors, deadlock prevention and detection, memory management, virtual memory, processor scheduling, disk management, file systems, security, protection, distributed systems. Two 90-minute lectures. Prerequisites: 217 and 226 or instructor's permission. Instructed by: J. Singh

COS 320 Compiling Techniques Spring

The principal algorithms and concepts associated with translator systems. Topics include lexical analysis, syntactic analysis, parsing techniques, symbol table management, code generation and optimization, run time system design, implementation issues related to programming language design. Course will include a large-scale programming project utilizing the above topics. Three lectures. Prerequisites: 217 and 226 or instructor's permission. Instructed by: Z. Kincaid

COS 323 Computing and Optimization for the Physical and Social Sciences (See ORF 363)

COS 333 Advanced Programming Techniques Fall/Spring

The practice of programming. Emphasis is on the development of real programs, writing code but also assessing tradeoffs, choosing among design alternatives, debugging and testing, and improving performance. Issues include compatibility, robustness, and reliability, while meeting specifications. Students will have the opportunity to develop skills in these areas by working on their own code and in group projects. Two 90-minute lectures. Prerequisites: 217 and 226 (as corequisite). Instructed by: R. Dondero Jr., C. Moretti

COS 340 Reasoning about Computation Fall/Spring QR

An introduction to mathematical topics relevant to computer science. Combinatorics and probability will be covered in the context of computer science applications. The course will present a computer science approach to thinking and modeling through such topics as dealing with uncertainty in data and handling large data sets. Students will be introduced to fundamental concepts such as NP-completeness and cryptography that arise from the world view of efficient computation. Prerequisites COS 126 and 226 (or sufficient mathematical background), and MAT 202 or MAT 204 or MAT 217. COS 226 can be taken along with COS 340 in the same term. Instructed by: M. Braverman, R. Raz

COS 342 Introduction to Graph Theory (See MAT 375)

COS 351 Information Technology and Public Policy (See WWS 351)

COS 375 Computer Architecture and Organization (also
ELE 375
) Spring STN

An introduction to computer architecture and organization. Instruction set design; basic processor implementation techniques; performance measurement; caches and virtual memory; pipelined processor design; design trade-offs among cost, performance, and complexity. Two 90-minute classes, one self-scheduled hardware laboratory. Prerequisites: COS 217. Instructed by: D. August

COS 381 Networks: Friends, Money and Bytes (See ELE 381)

COS 396 Introduction to Quantum Computing (See ELE 396)

COS 397 Junior Independent Work (B.S.E. candidates only) Fall

Offered in the fall, juniors are provided with an opportunity to concentrate on a "state-of-the-art" project in computer science. Topics may be selected from suggestions by faculty members or proposed by the student. B.S.E. candidates only. Instructed by: D. Dobkin, R. Fish

COS 398 Junior Independent Work (B.S.E. candidates only) Spring

Offered in the spring, juniors are provided with an opportunity to concentrate on a "state-of-the-art" project in computer science. Topics may be selected from suggestions by faculty members or proposed by the student. B.S.E. candidates only. Instructed by: A. Finkelstein, R. Fish

COS 402 Machine Learning and Artificial Intelligence Not offered this year

This course will provide a basic introduction to the core principles, algorithms and techniques of modern artificial intelligence and machine learning research and practice. Main topics will include: 1. Problem solving using search, with applications to game playing 2. Probabilistic reasoning in the presence of uncertainty 3. Hidden Markov models and speech recognition 4. Markov decision processes and reinforcement learning 5. Machine learning using decision trees, neural nets and more. 6. Basic principles of mathematical optimization for learning. Prerequisites- COS 226 and COS 340 Instructed by: Staff

COS 423 Theory of Algorithms Spring

Design and analysis of efficient data structures and algorithms. General techniques for building and analyzing algorithms. Introduction to NP-completeness. Two 90-minute lectures. Prerequisites: 226 and 340 or instructor's permission. Instructed by: R. Tarjan

COS 424 Fundamentals of Machine Learning (also
SML 302
) Not offered this year

Computers have made it possible to collect vast amounts of data from a wide variety of sources. It is not always clear, however, how to use the data, and how to extract useful information from them. This problem is faced in a tremendous range of social, economic and scientific applications. The focus will be on some of the most useful approaches to the problem of analyzing large complex data sets, exploring both theoretical foundations and practical applications. Students will gain experience analyzing several types of data, including text, images, and biological data. Two 90-minute lectures. Prereq: MAT 202 and COS 126 or equivalent. Instructed by: Staff

COS 426 Computer Graphics Spring

The principles underlying the generation and display of graphical pictures by computer. Hardware and software systems for graphics. Topics include: hidden surface and hidden line elimination, line drawing, shading, half-toning, user interfaces for graphical input, and graphic system organization. Two 90-minute lectures. Prerequisites: 217 and 226. Instructed by: F. Heide

COS 429 Computer Vision Fall

An introduction to the concepts of 2D and 3D computer vision. Topics include low-level image processing methods such as filtering and edge detection; segmentation and clustering; optical flow and tracking; shape reconstruction from stereo, motion, texture, and shading. Throughout the course, there will also be examination of aspects of human vision and perception that guide and inspire computer vision techniques. Prerequisites: 217 and 226. Two 90-minute lectures. Instructed by: O. Russakovsky

COS 432 Information Security (also
ELE 432
) Fall/Spring

Security issues in computing, communications, and electronic commerce. Goals and vulnerabilities; legal and ethical issues; basic cryptology; private and authenticated communication; electronic commerce; software security; viruses and other malicious code; operating system protection; trusted systems design; network security; firewalls; policy, administration and procedures; auditing; physical security; disaster recovery; reliability; content protection; privacy. Prerequisites: 217 and 226. Two 90-minute lectures. Instructed by: E. Felten, P. Mittal

COS 433 Cryptography (also
MAT 473
) Spring

An introduction to modern cryptography with an emphasis on fundamental ideas. The course will survey both the basic information and complexity-theoretic concepts as well as their (often surprising and counter-intuitive) applications. Among the topics covered will be private key and public key encryption schemes, digital signatures, pseudorandom generators and functions, chosen ciphertext security; and time permitting, some advanced topics such as zero knowledge proofs, secret sharing, private information retrieval, and quantum cryptography. Prerequisites: 226 or permission of instructor. Two 90-minute lectures. Instructed by: M. Zhandry

COS 436 Human-Computer Interface Technology (also
ELE 469
) Not offered this year

Creating technologies that fit into people's everyday lives involves more than having technically sophisticated algorithms, systems, and infrastructure. It involves understanding how people think and behave and using this data to design user-facing interfaces that enhance and augment human capabilities. Introduction to the field of human-computer interaction and the tools, techniques, and principles that guide research on people. Design and implement user-facing systems that bring joy rather than frustrate the user and put these skills into practice in a group project involving the creation of an interactive system. Prerequisite COS 217. Instructed by: Staff

COS 448 Innovating Across Technology, Business, and Marketplaces (also
EGR 448
) Spring

This course introduces engineering students to the types of issues that are tackled by leading and innovative Chief Technology Officers: the technical visionaries and/or managers at companies who innovate at the boundaries of technology, business, and marketplaces by understanding all of these areas deeply. These individuals are true partners to the business leaders of the organization, not merely implementers of business goals. The focus will be on software technologies and businesses based on them. To use specific contexts, we will emphasize two complementary areas as examples: businesses based on cloud computing and on marketplaces. Instructed by: J. Singh

COS 451 Computational Geometry Fall

Introduction to basic concepts of geometric computing, illustrating the importance of this new field for computer graphics, solid modelling, robotics, databases, pattern recognition, and statistical analysis. Algorithms for geometric problems. Fundamental techniques, for example, convex hulls, Voronoi diagrams, intersection problems, multidimensional searching. Two 90-minute lectures. Prerequisites: 226 and 340 or 341, or equivalent. Instructed by: B. Chazelle

COS 455 Introduction to Genomics and Computational Molecular Biology (See QCB 455)

COS 461 Computer Networks Spring

This course studies computer networks and the services built on top of them. Topics include packet-switch and multi-access networks, routing and flow control, congestion control and quality-of-service, Internet protocols (IP, TCP, BGP), the client-server model and RPC, elements of distributed systems (naming, security, caching) and the design of network services (multimedia, peer-to-peer networks, file and Web servers, content distribution networks). Two lectures, one preceptorial. Prerequisite: 217. Instructed by: M. Freedman

COS 462 Design of Very Large-Scale Integrated (VLSI) Systems (See ELE 462)

COS 475 Computer Architecture (See ELE 475)

COS 487 Theory of Computation (also
MAT 407
) Fall

Studies the limits of computation by identifing tasks that are either inherently impossible to compute, or impossible to compute within the resources available. Introduces students to computability and decidability, Godel's incompleteness theorem, computational complexity, NP-completeness, and other notions of intractability.This course also surveys the status of the P versus NP question. Additional topics may include: interactive proofs, hardness of computing approximate solutions, cryptography, and quantum computation. Two lectures, one precept. Prerequisite: 340 or 341, or instructor's permission. Instructed by: G. Kol

COS 488 Introduction to Analytic Combinatorics (also
MAT 474
) Spring

Analytic Combinatorics aims to enable precise quantitative predictions of the properties of large combinatorial structures. The theory has emerged over recent decades as essential both for the scientific analysis of algorithms in computer science and for the study of scientific models in many other disciplines. This course combines motivation for the study of the field with an introduction to underlying techniques, by covering as applications the analysis of numerous fundamental algorithms from computer science. The second half of the course introduces Analytic Combinatorics, starting from basic principles. Instructed by: R. Sedgewick

COS 495 Special Topics in Computer Science Not offered this year

These courses cover one or more advanced topics in computer science. The courses are offered only when there is an opportunity to present material not included in the established curriculum; the subjects vary from term to term. Three classes. Instructed by: Staff

COS 496 Special Topics in Computer Science Not offered this year

These courses cover one or more advanced topics in computer science. The courses are offered only when there is an opportunity to present material not included in the established curriculum; the subjects vary from term to term. Three classes. Instructed by: Staff

COS 497 Senior Independent Work (B.S.E. candidates only) Fall

Offered in the fall, seniors are provided with an opportunity to concentrate on a "state-of-the-art" project in computer science. Topics may be selected from suggestions by faculty members or proposed by the student. B.S.E. candidates only. Instructed by: D. Dobkin, R. Fish

COS 498 Senior Independent Work (B.S.E. candidates only) Spring

Offered in the spring, seniors are provided with an opportunity to concentrate on a "state-of-the-art" project in computer science. Topics may be selected from suggestions by faculty members or proposed by the student. B.S.E. candidates only. Instructed by: A. Finkelstein, R. Fish