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, one three-hour laboratory.

Computers have brought the world to our fingertips. This course explores at a basic level the science "old and new" underlying this new computational universe: propositional logic of the ancient Greeks (microprocessors); quantum mechanics (silicon chips); network and system phenomena (Internet and search engines); computational intractability (secure encryption); and efficient algorithms (genomic sequencing). Ultimately, this study makes us look anew at ourselves: our genome; language; music; "knowledge"; and, above all, the mystery of our intelligence.
Cross-listed as EGR116
Prerequisite(s): Two 90-minute lectures, one three-hour laboratory.

An introduction to computer science in the context of scientific, engineering, and commercial applications. The goal of the course is to teach basic principles and practical issues, while at the same time preparing 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. Two lectures, two classes.

Introduction to programming systems, including modular programming, advanced program design, programming style, test, debugging and performance tuning; machine languages and assembly language; and use of system call services. Three lectures.
Prerequisite(s): 126 or instructor's permission.

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 lectures, one preceptorial.
Prerequisite(s): 126 or instructor's permission.

See ISC231-236

See LIN280

See ELE206 (Department of Electrical Engineering)
Departmental Track: Systems

See MUS314 (Department of Music)

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. (Systems Departmental) Two 90-minute lectures.
Departmental Track: Systems
Prerequisite(s): 217 and 226 or instructor's permission.

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.
Departmental Track: Systems
Prerequisite(s): 217 and 226 or instructor's permission.

Principles of scientific computation, driven by current applications in biology, physics, economics, engineering, etc. Topics include: simulation, integration of differential equations, iterative optimization algorithms, stability and accuracy issues. Students will pursue projects in a variety of fields, writing their own computer programs and also using higher-level tools such as Maple. Two 90-minute lectures.
Departmental Track: Applications
Prerequisite(s): 126 and MAT 104, or instructor's permission.

Capturing and transforming sound by computer for artistic purposes. Emphasis is on the studentNULLs own creative use of aural material from the real world, on providing a basic foundation in the signal processing theory and technique most useful for computer music, and on the interaction between the artistic and scientific aspects of the endeavor. Two 90-minute lectures, one preceptorial, one laboratory.
Departmental Track: Applications
Prerequisite(s): COS 217 and MAT 104.

An introduction to the principles of typed functional programming. Programming recursive functions over structured data types and informal reasoning by induction about the correctness of those functions. Functional algorithms and data structures. Principles of modular programming, type abstraction, representation invariants and representation independence. Parallel functional programming, algorithms and applications.
Departmental Track: Applications
Prerequisite(s): COS 226 or with permission of the instructor.

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.
Departmental Track: Systems
Prerequisite(s): 217 and 226 (as corequisite).

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 topics such 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.
Departmental Track: Theory
Prerequisite(s): COS 126 and MAT 200 or 202 or 204.

See MAT306 (Department of Mathematics)

See ELE375 (Department of Electrical Engineering)
Departmental Track: Systems

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.
Prerequisite(s): B.S.E. candidates only.

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.
Prerequisite(s): B.S.E. candidates only.

See TRA301 (Program in Translation and Intercultural Communication)
Departmental Track: Applications

The fundamental principles, algorithms and techniques of modern artificial intelligence research and practice. Likely topics include: problem solving using search, game playing, logical inference, probabilistic reasoning in the presence of uncertainty, hidden Markov models, speech recognition, Markov decision processes, machine learning. Two 90-minute lectures.
Departmental Track: Applications
Prerequisite(s): 226.

Design and analysis of efficient data structures and algorithms. General techniques for building and analyzing algorithms. Introduction to NP-completeness. Two 90-minute lectures.
Departmental Track: Theory
Prerequisite(s): 226 and 341 or instructor's permission.

Computers have made it possible, even easy, to collect vast amounts of data from a wide variety of sources. It is not always clear, however, how to use that data, and how to extract useful information from it. This problem is faced in a tremendous range of business and scientific applications. This course will focus on some of the most useful approaches to this broad problem, exploring both theoretical foundations and practical applications. Students will gain experience analyzing several kinds of data, including text, images and biological data. Topics will include classification, clustering, prediction, and dimensionality reduction.
Departmental Track: Applications
Prerequisite(s): MAT 202 and COS 126 or equivalent or permission of instructor.

Theoretical and practical aspects of database systems and systems for accessing and managing semi-structured information (e.g. Web information repositories). Topics include: relational and XML models, storage and indexing structures,query expression and evaluation, concurrency and transaction management, search effectiveness. Two 90-minute lectures.
Departmental Track: Systems
Prerequisite(s): 217 and 226.

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.
Departmental Track: Applications
Prerequisite(s): 217 and 226.

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. Two 90-minute lectures.
Departmental Track: Applications
Prerequisite(s): 217 and 226.

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. Two 90-minute lectures.
Departmental Track: Applications
Prerequisite(s): 217 and 226.

A rigorous introduction to modern cryptography. Emphasis will be placed on the fundamental cryptographic primitives of public-key encryption, digital signatures, pseudo-random number generation, and basic protocols. The course will discuss both the foundations of modern cryptography in computational complexity theory and the main conceptual applications of cryptographic primitives.
Cross-listed as MAT443 (Department of Mathematics) Two 90-minute lectures.
Departmental Track: Theory
Prerequisite(s): 226 and 341 recommended, but other interested students are encouraged to contact the instructor.

This course studies both classic techniques of indexing documents and searching text, and also new algorithms that exploit properties of the World Wide Web, digital libraries, and multimedia collections. There is significant emphasis on current methods employed by Web search engines, including methods of employing user profiles to enhance search results. Pragmatic issues of handling very large amounts of information that may be widely dispersed - caching, distributed storage, and networking technology - are also covered.
Departmental Track: Applications
Prerequisite(s): COS226

This course covers hardware, sensors, displays, software, signal processing, pattern recognition, real-time computing, systems, and architectures for human-computer interfacing. Labs supplement lectures and readings, and final group projects are executed and tested.
Cross-listed as ELE460 (Department of Electrical Engineering)
Departmental Track: Applications
Prerequisite(s): COS 217 or ELE 302.

How to design and analyze programming languages and how to use them effectively. Functional programming languages, object-oriented languages; type systems, abstraction mechanisms, operational semantics, safety and security guarantees. Implementation techniques such as object representations and garbage collection will also be covered. Three lectures.
Departmental Track: Theory

The goal of this course is to connect auction theory to real-world auctions. Basic results will be derived and illustrated with experiments in class and observations of behavior on the Internet. Topics include: current Internet auctions, Vickrey auctions, dominant strategies, equilibrium behavior, revenue equivalence, optimal auctions, multi-unit auctions, efficiency, mechanism design, risk aversion, spite, collusion, wars, fraud, ethical and legal considerations.
Departmental Track: Applications
Prerequisite(s): COS 226 and 217; or ECO 310; or instructor's permission.

Computation and other aspects of our lives are becoming increasingly intertwined. In this course we will study a variety of topics on the cusp between economics and computation. Topics to be covered include: games on networks, auctions, mechanism and market design, reputation, computational social choice. The aim of the course is two-fold: (1) to understand the game-theoretic issues behind systems involving computation such as online networks, and (2) to learn how algorithms and algorithmic thinking can help with designing better decision and allocation mechanisms in the offline world.
Departmental Track: Theory
Prerequisite(s): COS226, MAT 175 or MAT 202 or 204 or 217, or instructor's permission.

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.
Departmental Track: Theory
Prerequisite(s): 226 and 341, or equivalent.

See MOL455 (Department of Molecular Biology)
Departmental Track: Applications

This course studies computer networks and the services built on top of them. Topics include packetswitch 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 90-minute lectures.
Departmental Track: Systems
Prerequisite(s): 217.

See ELE462 (Department of Electrical Engineering)

See ELE463 (Department of Electrical Engineering)

See ELE475 (Department of Electrical Engineering)
Departmental Track: Systems

Formal models of computation: finite automata and Turing machines. Universality Theorem and the Church-Turing Thesis. Computability Theory ("What can or cannot be computed?") and Complexity Theory ("How efficient can a certain computation be?"). NP-completeness and PSPACE-completeness. An introduction to complexity issues in application areas such as robotics, graphics, compilers, and computer security.
Cross-listed as MAT447 (Department of Mathematics) Two 90-minute lectures.
Departmental Track: Theory
Prerequisite(s): 341 or instructor's permission.

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.
Departmental Track: Theory
Prerequisite(s): COS 226, 340

The study of theoretical and pragmatic aspects of one or two of the following topics: machine learning, intelligent scientific computation, qualitative physics, knowledge representation, nonmonotonic reasoning, or reasoning about uncertainty. Two 90-minute classes.
Prerequisite(s): 402 or instructor's permission.

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.

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.
Prerequisite(s): B.S.E. candidates only.

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.
Prerequisite(s): B.S.E. candidates only.

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.