# Course Catalog

*This catalog is a list of courses that the department may offer in a given year. Not all courses in the catalog are offered every year.*

If you are looking for current course information:

-View the Registrar's course offerings page for courses offered this semester.

-Students and faculty can refer to the Undergraduate Announcement for the academic year undergraduate course information.

Undergraduate courses are in the 100 - 400 listing. Graduate courses are in the 400 - 500 listing.

If you are looking for current course information:

-View the Registrar's course offerings page for courses offered this semester.

-Students and faculty can refer to the Undergraduate Announcement for the academic year undergraduate course information.

Undergraduate courses are in the 100 - 400 listing. Graduate courses are in the 400 - 500 listing.

## COS487 - Theory of Computation (Fall)

Introduction to computability and complexity theory. Topics will include models of computation such as finite automata, pushdown automata, and Turing machines; decidability and decidability; computational complexity; P, NP, and NP completeness; others.

Cross-listed as MAT407 Department of Mathematics.

## COS488 - Introduction to Analytic Combinatorics (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.

Cross-listed as MAT474.

## COS495 - Special Topics in Computer Science (Spring)

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.

## COS496 - Special Topics in Computer Science (Fall)

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 .

## COS497 - 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.

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

## COS510 - Programming Languages

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

## COS511 - Theoretical Machine Learning

This course introduces theoretical machine learning, including mathematical models of machine learning, and the design and rigorous analysis of learning algorithms. Likely topics include: intro to statistical learning theory and bounds on the number of random examples needed to learn; learning in adversarial settings and the on-line learning model; using convex optimization to model and solve learning problems; learning with partial observability; recommendation systems and matrix learning; how to boost the accuracy of a weak learning algorithm; universal portfolio selection; learning in games.

## COS516 - Automated Reasoning about Software (Fall)

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

## COS518 - Advanced Computer Systems

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.

## COS521 - Advanced Algorithm Design

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.

## COS522 - Computational Complexity

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.

## COS525 - Mathematical Analysis of Algorithms

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.

## COS526 - Advanced Computer Graphics

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.

## COS527 - Probabilistic Algorithms

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.

## COS528 - Data Structures and Graph Algorithms

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.

## COS533 - Advanced Cryptography (Fall)

This course covers a selection of advanced topics in cryptography, including some or all of the following: fully homomorphic encryption, zero knowledge proofs, traitor tracing, identity-based encryption, private information retrieval, garbled circuits, secret sharing, multiparty computation, lattice-based cryptography, and elliptic curve-based cryptography.

## COS551 - Introduction to Computational Molecular Biology

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.

## COS557 - Analysis and Visualization of Large-Scale Genomic Data Sets

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.

## COS561 - Advanced Computer Networks

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.