Course Catalog

Recent advances have ushered in exciting developments in natural language processing (NLP), resulting in systems that can translate text, answer questions and even hold spoken conversations with us. This course will introduce students to the basics of NLP, covering standard frameworks for dealing with natural language as well as algorithms and techniques to solve various NLP problems, including recent deep learning approaches. Topics covered include language modeling, rep. learning, text classification, sequence tagging, syntactic parsing, and machine translation.

Studies the limits of computation by identifying 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.

Cross-listed as MAT407 Department of Mathematics.

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.

Cross-listed as MAT474.

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.

Cross-listed as EGR485.

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.

Complex networks arise through the analysis of complex systems in many areas of study. Well known areas include social network analysis (e.g. Facebook friends), text citation analysis (e.g. Wikipedia) and biological network analysis (e.g. protein-protein interactions). Complex networks can be distinguished from random networks and from regular networks, such as grids, which are often created by design for applications such as interconnecting computers. This course examines methods of analysis of complex networks and how this analysis can be applied to enhance our understanding of real-world systems.

Cross-listed as .

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.

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. The final choice must be approved by the faculty advisor.

Logic and formal reasoning about software, treating programs and programming languages as mathematical objects about which precise claims can be made. Basic concepts and techniques such as operational semantics and axiomatic semantics for specifying programming languages; structure, definition and properties of type systems; invariants and assertions for specifying programs. Use of automated tools such as interactive proof assistants, model checkers, and/or satisfiability-modulo-theories solvers. (Replaces COS 441 beginning AY2012-2013).

Can the mechanism of learning be automated and implemented by a machine? In this course we formally define and study various models that have been proposed for learning. The course presents and contrasts the statistical, computational and game-theoretic models for learning. Likely topics: intro to statistical learning theory and generalization; learning in adversarial settings on-line learning; analysis of convex and nonconvex optimization algorithms, using convex optimization to model and solve learning problems; learning with partial observability; boosting; reinforcement learning and control; introduction to theory of deep learning.

This course covers fundamental topics in probabilistic modeling and allows you to contribute to this important area of machine learning and apply it to your work. We learn how to model data arising from different fields and devise algorithms to learn the structure underlying these data for the purpose of prediction and decision making. We cover several model classes--including deep generative models--and several inference algorithms, including variational inference and Hamiltonian Monte Carlo. Finally, we cover evaluation methods for probabilistic modeling as well as tools to challenge our models' assumptions.

Cross-listed as 513 Center for Statistics and Machine Learning.

An introduction to algorithmic techniques for reasoning about software. Basic concepts in logic-based techniques including model checking, invariant generation, symbolic execution, and syntax-guided synthesis; automatic decision procedures in modern solvers for Boolean Satisfiability (SAT) and Satisfiability Modulo Theory (SMT); and their applications in automated verification, analysis, and synthesis of software. Emphasis on algorithms and automatic tools.

Cross-listed as 516 Department of Electrical and Computer Engineering.

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.

Gives a broad exposure to algorithmic design ideas of the past few decades, and brings students up to a level where they can understand research papers in algorithms. Although designed for computer science grads, it may be suitable for advanced undergrads and non-CS grads as well.

The course is thematically distinct from undergrad algorithms (such as COS 423) in its extensive use of ideas such as randomness, optimization and approximation, and high dimensional geometry, which are increasingly important in applications. It also introduces other concerns that arise today, such as dealing with uncertainty, big data sizes, and strategic (i.e., game-theoretic) behaviors. All necessary mathematical tools will be covered in class.

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.

Advanced topics in computer vision, with a focus ~n recent methods and current research. Topics include 3D vision, recognition, and the intersection of computer vision and other fields. Appropriate for students who have taken COS 429 or equivalent and would like further exposure to computer vision.

This course covers a selection of topics in cryptography, including some or all of the following: one-way functions, mathematical foundations of group-based and lattice-based cryptography, proof systems, multi-party computation, fully homomorphic encryption, obfuscation, and (post-)quantum cryptography. This course is intended to serve as an introduction to cryptography from the foundations up to present-day research.