Courses are generally scheduled from 5 to 7 p.m. or from 7 to 9 p.m.; however, honors courses (intended primarily for full-time Ph.D. students) are held during afternoon hours.

For courses requiring programming, students may use the Courant Institute’s computing facilities.

Detailed course descriptions may be accessed each semester from the “Courses” links on the department’s Web site.

PREPARATORY ACCELERATED COURSE (PAC)

Applicants to the master’s programs who have insufficient background in computer science but are otherwise admissible are referred to PAC. These two courses (part one, which is offered in the fall, and part two, in the spring) are designed to fulfill the minimum prerequisites for beginning a master’s program in computer science or information systems. Those admitted to the M.S. program with the requirement to complete PAC are considered M.S. degree students while they are enrolled in PAC courses, although the credits for the courses do not count toward the M.S. degree.

Applicants should apply for their ultimate degree objective rather than for PAC, even if they expect to be required to take these courses.

Intensive Introduction to Graduate Study in Computer Science I (PAC I)
G22.1133  Prerequisite: programming experience in any language. 4 points.
An accelerated introduction to the fundamental concepts of computer science for students who lack a formal background in the field. Topics include algorithm design and program develop- ment; data types; control structures; subprograms and parameter passing; recursion; data structures; searching and sorting; dynamic storage allocation and pointers; abstract data types, such as stacks, queues, lists, and tree structures; generic packages; and an introduction to the principles of object-oriented programming. Concepts are implemented using the Ada programming language as a representative modern high-level imperative language, emphasizing packages as a means to develop skills in effective software design and development. Students should expect an average of 12-16 hours of programming and related course work per week.

Intensive Introduction to Graduate Study in Computer Science II (PAC II)
G22.1144  Prerequisite: G22.1133 or departmental permission. 4 points.
Builds directly on the foundation developed in PAC I and extends this two ways: down, to the level of machine architecture, and up, to the higher levels of programming abstraction, using Java and object-oriented programming techniques. Topics include

1. Assembly language programming for the Intel chip family, emphasizing internal data representation, the logic of machine addressing, registers, the system stack, component development and techniques for communication among the components.

2. Programming in the C language, a relatively high-level systems programming language that also provides low-level capabilities similar to those of assembly language.

3. Programming in Java, which shares much of the syntax of C, removing pointer management and introducing object-oriented programming concepts.

4. An overview of common UNIX commands and shell-script programming.

Examples and assignments reinforce and refine those first seen in PAC I and often connect directly to topics in the core computer science graduate courses, such as Programming Languages, Compilers, Fundamental Algorithms, and Operating Systems.

ALGORITHMS

Fundamental Algorithms
G22.1170  Prerequisite: at least one year’s experience with a high-level language such as Pascal, C, C++, or Java; knowledge of assembly language; and familiarity with recursive programming methods and with data structures (arrays, pointers, stacks, queues, linked lists, binary trees). 3 points.
Reviews a number of important algorithms, with emphasis on correctness and efficiency: solving recurrence equations; sorting algorithms; selection; binary search; hashing; binary search trees and balanced-tree strategies; tree traversal; partitioning; graphs; spanning trees; shortest paths; connectivity; depth first search; breadth first search. Dynamic programming, divide and conquer.

Elements of Discrete Mathematics
G22.2340  Identical to G63.2050. May not be taken by students who have received a grade of B or better in G22.1170. 3 points.
Introduction to the central mathematical concepts that arise in computer science. Emphasis is on proof and abstraction. Topics include proof techniques; combinatorics; sets, functions, and relations; discrete structures; order of magnitude analysis; formal logic; formal languages and automata.

Honors Analysis of Algorithms
G22.3520  Prerequisites: G22.1170 or one semester of undergraduate algorithms, and permission of the instructor. 4 points.
Design of algorithms and data structures. Review of searching, sorting, and fundamental graph algorithms. In-depth analysis of algorithmic complexity, including advanced topics on recurrence equations and NP-complete problems. Advanced topics on lower bounds, randomized algorithms, amortized algorithms, and data structure design as applied to union-find, pattern matching, polynomial arithmetic, network flow, and matching.

PROGRAMMING LANGUAGES

Programming Languages
G22.2110  3 points.
Design and use of mainstream programming languages: naming, scoping, type models, control structures, procedural abstractions, modularization. Implementation issues and run-time organization. Languages studied include Ada, C, C++, Java, LISP, ML, and Python. Extensive programming exercises in various languages.

Compilers and Computer Languages
G22.2130  Prerequisite: G22.1170. 3 points.
Structure of one-pass and multiple-pass compilers, symbol table management, lexical analysis. Traditional and automated parsing techniques, including recursive descent and LR parsing. Syntax-directed translation and semantic analysis, run-time storage management, intermediate code generation. Introduction to optimization, code generation.

Honors Programming Languages
G22.3110  Prerequisite: permission of the instructor. 4 points.
In-depth examination of the four major categories of programming languages: imperative, object-oriented, functional, and logic languages. The specific languages covered include Ada, C++, LISP, ML, Prolog, and SETL. Funda-mental issues of programming languages, such as type systems, scoping, concurrency, modularization, control flow, and semantics, are discussed.

Honors Compilers and Computer Languages
G22.3130  Prerequisites: one semester of undergraduate compilers or G22.2130, and permission of the instructor. 4 points.
Lexical scanning and scanner generation from regular expressions; LL, LR, and universal parser generation from context-free grammars; syntax-directed translation and attribute grammars; type and general semantic analysis; code generation, peephole optimization, and register allocation; and global program analysis and optimization. Provides experience using a variety of advanced language systems and experimental system prototypes.

COMPUTER SYSTEMS

Computer Systems Design
G22.2233  Pre- or corequisite: G22.1170. 3 points.
Gives students whose interest is in software an introduction to hardware and the logical design of digital computers. Topics include design of basic logic modules and arithmetic units; fixed and microprogrammable control structures; computer architecture; memory organization; and input-output organization.

High Performance Computer Architecture
G22.2243  Prerequisite: a course in computer organization and knowledge of assembly language programming. 3 points.
Measures of architecture quality. Memory system techniques: cache-memory design techniques, models of program behavior, cache and virtual memory structures. Pipeline computers, vector processors, and array processors. Multiprocessors, synchronization, cache coherence. Parallelization techniques, efficient parallel software.

UNIX Tools
G22.2245  3 points.
Brief history of the UNIX operating system: basic utilities (mail, editors); shells; windowing systems; shell programming using UNIX tools (awk, set, grep, tar); networking tools; news readers; etiquette and Internet databases and facilities; C programming tools; UNIX-based systems programming; desktop publishing tools; visualization systems; symbolic algebra tools; and system administration.

Design of Operating Systems
G22.2250  Prerequisite: G22.1170. 3 points.
Review of linkers and loaders. High-level design of key operating system concepts such as process scheduling and synchronization; deadlocks and their prevention; memory management, including (demand) paging and segmentation; and I/O and file systems, including examples from UNIX/Linux and Windows. Programming assignments, which may be written in C, C++, Java, or C#.

Networks and Distributed Systems
G22.2260  Prerequisites: course in undergraduate networks and/or operating systems; programming experience in C/C++ or Java is helpful for the final project. 3 points.
A course in computer networks and large-scale distributed systems. Teaches the design and implementation techniques essential for engineering both robust networks and Internet-scale distributed systems. The goal is to guide students so they can initiate and critique research ideas in networks and distributed systems and implement and evaluate a working system that can handle a real-world workload. Topics include routing protocols, network congestion control, wireless networking, peer-to-peer systems, overlay networks and applications, distributed storage systems, and network security.

Data Communications and Networks
G22.2262  Prerequisite: G22.2250. 3 points.
Studies the software tools used by computers to converse with each other and with the real world. Communications systems and media (including people); bandwidth limitations; channel sharing and grouping; data formatting; error detection and correction; protocols; networks; I/O driver design; operating system interfaces; and human interfaces.

Database Systems
G22.2433  Prerequisite: G22.1170. 3 points.
Database system architecture. Modeling an application and logical database design. The relational model and relational data definition and data manipulation languages. Design of relational databases and normalization theory. Physical database design. Concurrency and recovery. Query processing and optimization.

Advanced Database Systems
G22.2434  Prerequisite: G22.2433. 3 points.
Studies the internals of database systems as an introduction to research and as a basis for rational performance tuning. Topics: concurrency control, fault tolerance, operating system interactions, query processing, and principles of tuning.

Software Engineering
G22.2440  Prerequisites: G22.2110, G22.2130, and G22.2250. 3 points.
Presents modern software engineering techniques. Examines the software life cycle, including software specification, design, implementation, testing, and maintenance. Object-oriented design methods.

Distributed Computing
G22.2631  Prerequisites: G22.1170 and G22.2250. 3 points.
Concepts underlying distributed systems: synchronization, communication, fault tolerance, and performance. Examined from three points of view: (1) problems, appropriate assumptions, and algorithmic solutions; (2) linguistic constructs; and (3) some typical systems.

Honors Operating Systems
G22.3250  Prerequisites: one undergraduate course in algorithms and one in C or C++ programming. 4 points.
Operating-system structure. Processes. Process synchronization. Language mechanisms for concurrency. Deadlocks: modeling, prevention, avoidance, and recovery. Memory management. File-system interface. Secondary storage. Distributed systems: layered system design, managing distributed processes, distributed shared memory, fault-tolerance. CPU scheduling. Queuing and performance: analysis of single M/M/1 queue and others. Protection and security. Advanced security concepts: threat monitoring, encryption, and public keys.

COMPUTER GRAPHICS

Computer Graphics
G22.2270  Prerequisite: G22.1170. 3 points.
Problems and objectives of computer graphics. Vector, curve, and character generation. Interactive display devices. Construction of hierarchical image list. Graphic data structures and graphics languages. Hidden-line problems; windowing, shading, and perspective projection. Curved surface generation display.

User Interfaces
G22.2280  Prerequisite: proficiency in C programming. 3 points.
Review of some of the basic principles and history of user interfaces. Building an interactive window system from the ground up, starting with a generic portable graphics base. Examination of future and emerging (nontraditional) user interfaces, including virtual reality and immersive environments.

ARTIFICIAL INTELLIGENCE

Computer Vision
G22.2271  Prerequisite: G22.1170. 3 points.
Basic techniques of computer vision and image processing. General algorithms for image understanding problems. Study of binary image processing, edge detection, feature extraction, motion estimation, color processing, stereo vision, and elementary object recognition. Mathematical, signal processing, and image processing tools. Relation of computer vision algorithms to the human visual system.

Artificial Intelligence
G22.2560  Prerequisites: G22.1170 and G22.2110. 3 points.
There are many cognitive tasks that people do easily and almost unconsciously but that have proven extremely difficult to program on a computer. Artificial intelligence is the problem of developing computer systems that can carry out these tasks. This course covers problem solving and state space search; automated reasoning; probabilistic reasoning; planning; and knowledge representation.

Machine Learning
G22.2565  Prerequisites: undergraduate course in linear algebra and strong programming skills for implementation of algorithms studied in class. Recommended: knowledge of vector calculus, elementary statistics, and probability theory. 3 points.
This course covers a wide variety of topics in machine learning, pattern recognition, statistical modeling, and neural computation. The course covers the mathematical methods and theoretical aspects but primarily focuses on algorithmic and practical issues.

Foundations of Machine Learning
G22.2566  3 points.
This course introduces the fundamental concepts and methods of machine learning, including the description and analysis of several modern algorithms, their theoretical basis, and the illustration of their applications. Many of the algorithms described have been successfully used in text and speech processing, bioinformatics, and other areas in real-world products and services. The main topics covered are probability and general bounds; PAC model; VC dimension; perceptron, Winnow; support vector machines (SVMs); kernel methods; decision trees; boosting; regression problems and algorithms; ranking problems and algorithms; halving algorithm, weighted majority algorithm, mistake bounds; learning automata, Angluin-type algorithms; and reinforcement learning, Markov decision processes (MDPs).

Web Search Engines
G22.2580  3 points.
Discusses the design of general and specialized Web search engines and the extraction of information from the results of Web search engines. Topics include Web crawlers, database design, query language, relevance ranking, document similarity and clustering, the “invisible” Web, specialized search engines, evaluation, natural language processing, data mining applied to the Web, and multimedia retrieval.

Natural Language Processing
G22.2590  3 points.
Survey of the techniques used for processing natural language. Syntactic analysis: major syntactic structures of English; alternative formalisms for natural language grammar; parsing algorithms; analyzing coordinate conjunction; parsing with graded acceptability. Semantic analysis: meaning representations; analysis of quantificational structure; semantic constraints; anaphora resolution; analysis of sentence fragments. Analysis of discourse and dialog. Text generation. Students get some experience using a natural language parser and a natural language query interface. Brief weekly written assignments and a term project involving a mixture of library research and programming (mostly in Lisp).

Advanced Topics in Natural Language Processing: Statistical and Corpus-Based Methods
G22.2591  3 points.
One of the roadblocks to improving the performance of natural language systems is the difficulty of acquiring large amounts of knowledge about the properties of language: which words can meaningfully combine in linguistic structures and how words are semantically related. The recent availability of very large machine-readable corpora has sparked increased interest in acquiring this information automatically from text, using a combination of symbolic and statistical analysis.

This course reviews some of the recent work in this area, including the following topics: statistical models of language; entropy and perplexity;

n-gram word models: acquisition and smoothing, part-of-speech models; finite state models: hidden Markov models, acquisition procedures; probabilistic context-free grammars: acquisition procedures; semantic models: word-concurrence, word classes; applications in information retrieval, speech recognition, and machine translation.

Heuristic Problem Solving
G22.2965  3 points.
This course revolves around several problems new to computer science (derived from games or puzzles in columns for Dr. Dobb’s Journal, Scientific American, and elsewhere). The idea is to train students to face a new problem, read relevant literature, and come up with a solution. The solution entails winning a contest against other solutions. The winner receives candy. The best solutions become part of an evolving “Omniheurist” Web site that is expected to get many visitors over the years.

The course is for highly motivated, mathematically adept students. It is open to supported Ph.D. students and master’s students who have passed the core exam. Class size has been around 10 in the past, and instructor and students have all gotten to know one another very well. Algorithmic and programming knowledge are the main prerequisites. It also helps to be familiar with a rapid prototyping language such as MatLab, Mathematica, K, or Python, or to be completely fluent in some other language.

THEORETICAL COMPUTER SCIENCE

Logic in Computer Science
G22.2390  3 points.
A beginning graduate-level course in mathematical logic with motivation provided by applications in computer science. There are no formal prerequisites, but the pace of the class requires that students can cope with a significant level of mathematical sophistication. Topics include propositional and first-order logic; soundness, completeness, and compactness of first-order logic; first-order theories; undecidability and Godel’s incompleteness theorem; and an introduction to other logics such as second-order and temporal logic.

Introduction to Cryptography
G22.3210  3 points.
The primary focus of this course is on definitions and constructions of various cryptographic objects, such as pseudorandom generators, encryption schemes, digital signature schemes, message authentication codes, block ciphers, and others, time permitting. The class tries to understand what security properties are desirable in such objects, how to properly define these properties, and how to design objects that satisfy them. Once a good definition is established for a particular object, the emphasis will be on constructing examples that provably satisfy the definition. Thus, a main prerequisite of this course is mathematical maturity and a certain comfort level with proofs. Secondary topics, covered only briefly, are current cryptographic practice and the history of cryptography and cryptanalysis.

Advanced Cryptography
G22.3220  Prerequisite: G22.3210. 3 points.
Basics of computational number theory for cryptography. Identification protocols. Digital signatures. Public-key encryption. Additional selected topics.

Honors Theory of Computation
G22.3350  Prerequisites: one semester of undergraduate theory of computation or formal languages, and permission of the instructor. 4 points.

Formal languages: regular languages, regular expressions, finite-state machines, context-free languages, grammars, and pushdown machines. Computability: primitive recursive functions, partial recursive functions, recursive languages, recursively enumerable languages, and Turing machines. Computational complexity: space and time complexity, complexity classes (such as P, NP, PSPACE, L, and NL), and complete problems.

NUMERICAL ANALYSIS, SCIENTIFIC COMPUTING, AND MATHEMATICAL PROGRAMMING

Scientific Computing
G22.2112  Prerequisites: multivariate calculus, linear algebra, and basic probability. C/C++ programming very helpful. 3 points.
A practical introduction to scientific computing covering theory and basic algorithms together with use of visualization tools and principles behind reliable, efficient, and accurate software. Students program in C/C++ or MatLab. Specific topics include IEEE arithmetic, conditioning and error analysis, classical numerical analysis (finite difference and integration formulas, etc.), numerical linear algebra, optimization and nonlinear equations, ordinary differential equations, and basic Monte Carlo.

Numerical Methods I
G22.2420  Identical to G63.2010. Prerequisites: undergraduate linear algebra and some experience with programming. 3 points.
Floating-point arithmetic; conditioning and stability; numerical linear algebra, including systems of linear equations, least squares, and eigenvalue problems; LU, Cholesky, QR, and SVD factorizations; conjugate gradient and Lanczos methods; Gauss quadrature. Current software packages. Computer programming assignments form an essential part of the course.

Numerical Methods II
G22.2421  Prerequisite: G22.2420. 3 points.
Nonlinear equations (Newton’s method). Ordinary differential equations: initial value problem (Runge-Kutta and multistep methods, convergence and stability); two-point boundary value problem. Elliptic partial differential equations: finite difference and finite element methods, fast solvers, multigrid, iterative methods exploiting special structure. Brief introduction to time-dependent partial differential equations. Current software packages. Computer programming assignments form an essential part of the course.

Topics in Numerical Analysis
G22.2945  May be identical to G63.2030, G63.2031, G63.2040, G63.2051, G63.2060. Prerequisites vary according to topic. 3 points.
Recent topics have included computational fluid dynamics, finite elements method, particle methods. Current course descriptions are available from the department’s Web site.

SEMINARS AND RESEARCH

Information Technology Projects
G22.3812  Prerequisite: permission of the instructor. 3 points.
This course teaches students some of the skills required to participate in and run IT projects that succeed in the real world. Students simultaneously learn skills in the classroom and apply the skills in a project while interning at a local “client.” Clients are mostly companies, but sometimes they are government agencies or nonprofit organizations. Students are given the opportunity to work on projects early in their development so that they can experience the full software project life cycle. Students work in teams of about four individuals. Each team undertakes one project that lasts the entire semester. The readings, classroom lectures, discussions, and activities teach skills that help implement projects of this size. The following are examples of some projects:

Software purchase evaluation: In this type of project, a client needs some software to solve a particular business problem. However, it makes more sense to address this problem by purchasing, rather than building, the software. In this case, the team begins by analyzing the business problem and gathering requirements. It then designs an architecture that would connect the new system with existing systems. In the project’s second half, the team evaluates commercial products that might meet the requirements.

Software development: A client needs some software to solve a business problem. The team quickly prosecutes the software development life cycle—including requirements gathering, architecture, design, development, and testing—to produce a prototype system that addresses the business problem. The deliverables are the prototype code and a report. The report documents advice and knowledge gained during the project that might be useful to the staff at the client who will build a production system based on the prototype. About three-quarters of the projects involve software development.

Advanced Laboratory
G22.3813  Prerequisites: permission of the faculty project supervisor, completion of at least 12 points of study, and programming background. 1-3 points per term for master’s students, 1-12 points per term for Ph.D. students.
Large-scale programming project or research in cooperation with a faculty member. Students should be prepared to spend at least eight hours per week on this course.

Master’s Thesis Research
G22.3840  Prerequisite: approval of a faculty adviser. 3-6 points.

Ph.D. Research Seminar
G22.3850  Sections: 001, Cryptography; 002, Systems; 003, Theory; 004, Formal Methods; 005, Algebraic and Topological Computing; and 006, Machine Learning. Prerequisite: permission of the instructor. 1 point.
Graduate seminars serve as loosely structured forums for exploring research topics from broad areas of computer science. They are designed to foster dialogue by bringing together faculty and students from a given area and to encourage the exchange of ideas. As such, they bridge the gap between more structured course offerings and informal research meetings.

Ph.D. Thesis Research
G22.3860  Prerequisite: permission of the thesis adviser or director of graduate studies for the Ph.D. program. 1-12 points per term.

Special Topics in Computer Science
G22.3033  Prerequisites vary according to topic. 3 points.
Topics vary each semester. Recent offerings:

Adaptive Software Engineering

Advanced Rendering

Advanced Topics in Multimedia

Algorithms and the Internet

Analysis of Hardware Reactive Systems

Animation Production

Application Servers

Applied Cryptography and Security

Artificial Life for Computer Graphics

Bioinformatics

Computational Geometry and Modeling

Computational and Systems Biology

Computer Systems Security

Cryptographic Tools in Deployed Systems: What Does the Padlock Mean?

Data Warehousing and Mining

Development and Analysis of Real-Time and Hybrid Systems

Distributed Programming

Distributed Storage Systems

Experiments in Motion Capture

Exposure-Resilient Cryptography

Foundations of Machine Learning

Geometric Modeling

Internet/Intranet Protocols and Applications

Introduction to Computational Number Theory and Algebra

Logic and Verification

Machine Translation

Models/Analysis of Real-Time/Hybrid Systems

Mobile Robots

Production Quality Software

Program Analysis

Random Graphs

Rapid Visualization

Reactive Verification

Recapturing Life

Statistical and Computational Learning Theory

Structures in Natural Language Processing

Systems Biology

Timed and Hybrid Systems

Topics in Automated Deduction

Topics in Complexity Theory

Values Embodied in Information and Communication Technologies

What If a Computer Lies?

Web Service and Applications

World Wide Web Programming

 Back to Top