## Course Descriptions (GSAS Bulletin)

### (2015 - 2017)

#### Preparatory Accelerated Courses

**Intensive Introduction to Graduate Study in Computer
Science I (PAC I)**

CSCI-GA 1133 *Korth. 4 points. *2015-16,
2016-17

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 development; 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. The primary programming language
used in the course will be Java. 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)**

CSCI-GA 1144 * Prerequisite: CSCI-GA 1133 or
departmental permission. Zahran. 4 points. *2015-16, 2016-17

This course builds directly on the foundation developed in PAC I, covering the
essentials of computer organization through the study of assembly language
programming and C, as well as introducing the students to the analysis of
algorithms. Topics include: (1) Assembly language programming for the Intel
chip family, emphasizing computer organization, the Intel x86 instruction set,
the logic of machine addressing, registers and the system stack. (2)
Programming in the C language, a general-purpose programming language which
also has low-level features for systems programming. (3) An introduction to
algorithms, including searching, sorting, graph algorithms and asymptotic
complexity. 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, Fundamental Algorithms, and
Operating Systems.

#### Algorithms and Theoretical Computer Science

**Fundamental Algorithms **

CSCI-GA 1170 *Spencer, Yap, Dodis, Siegel. 3
points. *2015-16, 2016-17

Reviews a number of important algorithms, with emphasis on correctness and
efficiency. The topics covered include solution of recurrence equations,
sorting algorithms, selection, binary search trees and balanced-tree
strategies, tree traversal, partitioning, graphs, spanning trees, shortest
paths, connectivity, depth-first and breadth-first search, dynamic programming,
and divide-and-conquer techniques.

**Mathematical Techniques for Computer Science Applications
**

CSCI-GA 1180 *Davis, Kedem,Wright. 3 points. *2015-16,
2016-17

An introduction to theory, computational techniques, and applications of linear
algebra, probability and statistics. These three areas of continuous
mathematics are critical in many parts of computer science, including machine
learning, scientific computing, computer vision, computational biology, natural
language processing, and computer graphics. The course teaches a specialized
language for mathematical computation, such as Matlab, and discusses how the
language can be used for computation and for graphical output. No prior
knowledge of linear algebra, probability, or statistics is assumed.

**Elements of Discrete Mathematics **

CSCI-GA 2340 *Prerequisites: May not be taken
by students who have received a grade of B or better in CSCI-GA 1170. Staff. 3
points. *2015-16, 2016-17

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.

**Random Graphs **

CSCI-GA 3230 *Spencer. 3 points. 2*015-16,
2016-17

This course covers numerous topics related to random graphs, including generalized randomized structures, random processes, probabilistic methods and Erdös Magic. Also covered are branching processes, phase transitions for large random evolutions, derandomization via conditional expectations and
semidefinite programming derandomization techniques. Algorithms, probability
and discrete mathematics all appear, but concepts will be defined from scratch.
Emphasis will be on methods of asymptotic calculation.

**Honors Analysis of Algorithms **

CSCI-GA 3520 *Prerequisites: Permission of the
instructor for master’s students. Yap, Siegel. 4 points. *2015-16, 2016-17

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 and Compilers

**Programming Languages **

CSCI-GA 2110 *Goldberg. 3 points. *2015-16,
2016-17

Discusses the design, use, and implementation of imperative, object-oriented,
and functional programming languages. The topics covered include scoping, type
systems, control structures, functions, modules, object orientation, exception
handling, and concurrency. A variety of languages are studied, including C++,
Java, Ada, Lisp, and ML, and concepts are reinforced by programming exercises.

**Compiler Construction **

CSCI-GA 2130 *Prerequisites: CSCI-GA 1170,
CSCI-GA 2110, and CSCI-GA 2250. Grimm. 3 points. *2015-16, 2016-17

This is a capstone course based on compilers and modern programming languages.
The topics covered include 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; and code generation. The course
includes a special compiler-related capstone project, which ties together
concepts of algorithms, theory (formal languages), programming languages,
software engineering, computer architecture, and other subjects covered in the
MS curriculum. This project requires a substantial semester-long programming
effort, such as construction of a language compilation or translation system
that includes lexical and syntactic analyzers, a type checker, and a code
generator.

**Honors Programming Languages **

CSCI-GA 3110 *Prerequisite: permission of the
instructor for master’s students. Cousot. 4 points.* 2015-16, 2016-17

The course will introduce a panorama of programming languages concepts
underlying the main programming language paradigms (such as imperative,
functional, object-oriented, logic, concurrent, and scripting languages) and
present in detail the formal methods (code semantics, specification, and
verification) used in modern high quality assurance tools for software safety
and security. A programming project (design and implementation of an
interpreter/compiler for an dynamic object-oriented mini-language) will
be programmed in OCaml, a multiparadigm language introduced at the beginning of
the course.

**Honors Compilers and Computer Languages **

CSCI-GA 3130* Prerequisites: permission of the
instructor for master’s students. Staff. 4 points.* 2015-16, 2016-17

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

**Open Source Tools **

CSCI-GA 2246 *Prerequisites: An understanding
of modern operating systems and a working knowledge of a programming language, such as C, C++ or Java. Staff. 3 points. *2015-16, 2016-17

This course covers a brief history and philosophy of open source software,
followed by an in-depth look at open source tools intended for developers. In
particular, we will present an overview of the Linux operating system, command
line tools (find, grep, sed), programming tools (GIT, Eclipse, DTrace), web and
database tools (Apache, MySQL), and system administration tools. We will also
cover scripting languages such as shell and Python.

**Operating Systems **

CSCI-GA 2250 *Grimm, Gottlieb. 3 points. *2015-16,
2016-17

The topics covered include a review of linkers and loaders and the high-level
design of key operating systems concepts such as process scheduling and
synchronization; deadlocks and their prevention; memory management, including
(demand) paging and segmentation; and I/O and file systems, with examples from
Unix/Linux and Windows. Programming assignments may require C, C++, Java, or
C#.

**Networks and Distributed Systems **

CSCI-GA 2620 *Prerequisites: A course in
undergraduate networks and/or operating systems; programming experience in
C/C++ or Java is helpful for the final project. Subramanian. 3 points. *2015-16,
2016-17

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 **

CSCI-GA 2262 *Prerequisite: CSCI-GA 2250 or an
undergraduate networking course. Franchitti. 3 points. *2015-16, 2016-17

This course teaches the design and implementation techniques essential for
engineering robust networks. Topics include networking principles, Transmission
Control Protocol/Internet Protocol, naming and addressing (Domain Name System),
data encoding/decoding techniques, link layer protocols, routing protocols, transport layer services, congestion control, quality of service, network services, programmable routers and overlay networks.

Database Systems

CSCI-GA 2433 *Kedem, Franchitti. 3 points.*
2015-16, 2016-17

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 **

CSCI-GA 2434 * Prerequisites: CSCI-GA 1170,
CSCI-GA 2110, and CSCI-GA 2250. Shasha. 3 points.* 2015-16, 2016-17

This is a capstone course emphasizing large-scale database systems. This course
studies the internals of database systems as an introduction to research and as
a basis for rational performance tuning. Topics include concurrency control, fault tolerance, operating system interactions, query processing, and
principles of tuning. Database capstone projects involve topics such as design,
concurrency control, interactions, and tuning. These projects include some or
all of the following elements: formation of a small team, project proposal,
literature review, interim report, project presentation, and final report.

**Software Engineering **

CSCI-GA 2440 *Prerequisites: CSCI-GA 1170,
CSCI-GA 2110, and CSCI-GA 2250. Franchitti. 3 points. *2015-16, 2016-17

This is a capstone course focusing on large-scale software development. This
course presents modern software engineering techniques and examines the
software life cycle, including software specification, design, implementation,
testing, and maintenance. Object-oriented design methods are also considered.
Software engineering projects involve creation of a large-scale software system
and require some or all of the following elements: formation of a small team,
project proposal, literature review, interim report, project presentation, and
final report.

**Distributed Computing **

CSCI-GA 2631 *Prerequisites: CSCI-GA 1170 and
CSCI-GA 2250. Staff. 3 points.* 2015-16, 2016-17

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 **

CSCI-GA 3250 *Prerequisites: permission of the
instructor for master’s students. Grimm, Walfish 4 points.* 2015-16,
2016-17

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.

#### Graphics and Vision

**Computer Graphics **

CSCI-GA 2270 *Prerequisite: CSCI-GA 1170.
Perlin. 3 points. *2015-16, 2016-17

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.

**Computer Vision **

CSCI-GA 2271 * Prerequisite: CSCI-GA 1170.
Geiger. 3 points. *2015-16, 2016-17

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.

#### Computational Intelligence

**Artificial Intelligence **

CSCI-GA 2560 * Geiger, Davis. 3 points. *2015-16,
2016-17

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 **

CSCI-GA 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. Staff. 3 points.* 2015-16, 2016-17

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 **

CSCI-GA 2566 * Mohri. 3 points. *2015-16,
2016-17

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 **

CSCI-GA 2580 *Prerequisites: recommend CSCI-GA
1180. Davis. 3 points. *2015-16, 2016-17

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.

**Speech Recognition **

CSCI-GA 2585 * Prerequisites: Familiarity with
basics in linear algebra, probability and analysis of algorithms. No specific
knowledge about signal processing or other engineering material is required.
Mohri. 3 points. *2015-16, 2016-17

This course gives a computer science presentation of automatic speech
recognition, the problem of transcribing accurately spoken utterances, and
presents algorithms for creating large-scale speech recognition systems. The
algorithms and techniques presented are now used in most research and
industrial systems. The objective of the course is not only to familiarize
students with particular algorithms used in speech recognition, but also to use
that as a basis to explore general concepts of text and speech, as well as
machine learning algorithms relevant to a variety of other areas in computer
science. The course will make use of several software libraries and will study
recent research and publications in this area.

**Natural Language Processing **

CSCI-GA 2590 *Grishman. 3 points. *2015-16,
2016-17

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

CSCI-GA 2965 *Prerequisites: CSCI-GA 1170 and
an ability to prototype algorithms rapidly. Shasha. 3 points. *2015-16,
2016-17

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 well-qualified master’s students. 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 is the main prerequisite. 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.

#### Logic and Verification

**Logic in Computer Science **

CSCI-GA 2390 *Prerequisites: strong
mathematical background and instructor permission for master’s students.
Barrett, Mishra. 3 points. *2015-16, 2016-17

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.

#### Cryptography

**Applied Cryptography and Network Security **

CSCI-GA 3205 * Kedem. 3 points. *2015-16,
2016-17

This course first introduces the fundamental mathematical cryptographic
algorithms, focusing on those that are used in current systems. To the extent
feasible, the mathematical properties of the cryptographic algorithms are
justified, using elementary mathematical tools. Second, actual security
mechanisms and protocols, mainly those employed for network traffic that rely
on the previously introduced cryptographic algorithms, are presented. The
topics covered include introduction to basic number-theoretical properties,
public/private and symmetric key systems, secure hash functions, digital
signature standards, digital certificates, IP security, e-mail security, Web
security, and stand-alone computer privacy and security tools.

**Introduction to Cryptography **

CSCI-GA 3210 *Prerequisites: strong mathematical
background. Regev, Dodis. 3 points. *2015-16, 2016-17

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 **

CSCI-GA 3220 *Prerequisite: CSCI-GA 3210.
Dodis. 3 points.* 2015-16, 2016-17

Basics of computational number theory for cryptography. Identification
protocols. Digital signatures. Public-key encryption. Additional selected
topics.

#### Computation for Science and Society

**Financial Software Projects **

CSCI-GA 2180* Prerequisites: It is assumed that
the students can code in C++. No prior experience in the financial sector domain is required. Staff. 3
points. *2015-16, 2016-17

The theme of this course is an "applied case study" and focuses on
fixed income markets. Topics covered include an overview of the markets, the
inner workings of an investment bank, the market players, and where software
engineers fit in. Students will be grouped into small teams to build a
financial application using practical software engineering principles. Each
team will build a risk management framework, starting with basic components.

#### Projects, Seminars, and Research

**Information Technology Projects **

CSCI-GA 3812 *Prerequisites: Permission of the
instructor. Franchitti, Korth. 3 points.* 2015-16, 2016-17

This is a capstone course that connects students directly with real-world
information technology problems. The goal of this course is to teach the skills
needed for success in real-world information technology via a combination of classroom
lectures and practical experience with large projects that have been specified
by local “clients.” The typical clients are primarily companies, but can also
be government agencies or nonprofit organizations. Each project lasts for the
entire semester and is designed to involve the full software project life
cycle. Examples of such projects are development of software to solve a
business problem, including specifying requirements, writing and testing
prototype code, and writing a final report; and evaluation of commercial
software to be purchased to address a business problem, including gathering
requirements, designing an architecture to connect the new software with
existing systems, and assessing the suitability of available software products.

**Advanced Laboratory **

CSCI-GA 3813 * Prerequisites: permission of the
faculty project supervisor and the Director of Graduate Studies for the M.S.
Programs. Staff. 1-3 points per term for master’s students, 1-12 points per
term for Ph.D. students. 2015-16, 2016-17
*Large-scale programming project or research in cooperation with a
faculty member or a professional internship

**Master’s Thesis Research **

CSCI-GA 3840 *Prerequisite: approval of a
faculty adviser and the Director of Graduate Studies for the M.S. programs.
Staff. 3-6 points.* 2015-16, 2016-17

**Ph.D. Research Seminar **

CSCI-GA 3850 *Prerequisite: permission of the
instructor. Staff. 1 point. *2015-16, 2016-17

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 **

CSCI-GA 3860 *Prerequisite: permission of the
thesis adviser or director of graduate studies for the Ph.D. program. Staff.
1-12 points per term. *2015-16, 2016-17

**Special Topics in Computer
Science **

CSCI-GA 3033 * Prerequisites vary according to
topic. Staff. 3 points. *2015-16, 2016-17

Topics vary each semester. Recent offerings:

Algorithmic and Economic aspects
of the Internet

Application Servers

Cloud Computing: Concepts &
Practice

Computational Number Theory
& Algebra

Distributed Systems

Financial Computing

Graphics Processing Units
(GPUs): Architecture & Programming

Music Software Projects

Principles of Software Security

Production Quality Software

Programming Paradigms for
Concurrency

Robotics

Social Multiplayer Games

Social Networks

Realtime & Big Data
Analytics

Statistical Natural Language Processing