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 programming languages, including data representations, control regimes, code representations, and portability.
Prerequisite(s): COS226, COS320

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.

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(s): COS 318 or equivalent

Advanced methods of algorithmic design and analysis; data structures, network flows, and linear programming. Solution of linear problems: 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.

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.

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

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 equivalent and would like further exposure to computer graphics.

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.

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(s): COS 423 or equivalent

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.
Cross-listed as MOL551 (Department of Molecular Biology)

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; and 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.
Cross-listed as MOL557 (Department of Molecular Biology)

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.

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 ChurchNULLs Thesis, the complexity of analog computing, quantum computing, embedded computing in cellular automata, particle-based computing, soliton computing, and DNA computing.

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.

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.

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

Topics in computational complexity, the analysis of algorithms, and other areas of theoretical computer science.
Prerequisite(s): COS487 or equivalent

Research-oriented topics in the design and implementation of software systems. Specific topics are determined by the current literature and by student and faculty interest.
Prerequisite(s): COS226, COS318, COS320

Topics involving current research in computer science and applications in other fields. Click here to see recently taught topics.