Special Topics in Computer Science for Fall 2001
NOTE: for descriptions
of standard graduate computer science courses, see Graduate Course Descriptions.
G22.3033.01 Random Graphs (cross-listed w/
Prerequisites: Mathematical maturity. This
topic takes from several areas but the material will be developed in the
course. An acquaintance with, say, variance (in probability) and/or chromatic
number (in graph theory) will be helpful but not mandatory.
Description: Equally appropriate titles would
have been "Probabilistic Combinatorics" or "The Probabilistic Method." The
Probabilistic Method is a lasting legacy of the late Paul Erdos. For "Uncle
Paul" the purpose was to prove the existence of a graph, coloring, tournament,
or other combinatorial object. A random object would be described, and then
one would show that that object had the desired properties with positive
probability. Today we are very interested in algorithmic implementation,
both deterministically and with random algorithms. There is further great
interest (the official title) in the study of random discrete structures (not
just graphs, though that is the main one) for their own sake. The course
involves probability, Discrete Math, and algorithms. Probability results
include Chernoff Bounds, Martingales, the Lovasz Local Lemma and the Janson
Inequalities and will be derived from scratch. Topics include: Ramsey Numbers,
Continuous Time Greedy Algorithms, Graph Coloring, Discrepancy, the Liar Game
and the Tenure Game.
Text: Noga Alon, Joel Spencer, The Probabilistic
Method, second edition publisher: John Wiley, 2000
G22.3033.02 Programming for the
Prerequisite: good programming skills,
especially in C or C++.
A comprehensive introduction to
the Java programming language. In addition to the language itself,
topics include: introduction to object-oriented concepts, networking,
concurrent programming with threads.
G22.3033.003 Topics in Cryptography
The primary focus of this course will be
on formal definitions and efficient constructions of various cryptographic
objects, such as pseudo-random generators, encryption schemes, digital signature
schemes, message authentication codes, block ciphers, and others time permitting.
We will try 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 we establish a good definition 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. I will be doing proofs
in class, and you will be doing them on the homeworks.
Secondary topics that we will cover only briefly
will be current cryptographic practice and the history of cryptography and
At the end of this course, you should be able
to make sense of a good portion of current cryptography research papers
Visit the "work-in-progress"course website
for more information.
G22.3033.004 Architecture & Programming
of Parallel Computers
PREREQUISITES: Senior undergraduate-level
or introductory graduate-level courses in computer architecture and operating
Parallel computing is a critical component
of current-day computing technology, and is likely to grow in importance
with the proliferation of multiprocessor PC desktops and servers (consisting
of 8-16 Pentiums on a shared bus), and scalable clusters of commodity workstations.
This course shall examine the organizing principles
behind parallel computing both from an architectural and a programming perspective.
The course consists of two parts, organized around a common set of issues
relevant to all parallel systems: naming, synchronization, latency, and bandwidth.
The first part will discuss how modern parallel computer architectures deal
with these issues, both at the small (shared memory multiprocessors) and
large (scalable multiprocessors) scales. The second part of the course will
discuss how the issues are dealt with in several common programming paradigms
including message-passing, shared-memory, and higher-level approaches. The
focus in this part of the course will be on both programming expression and
programming for performance.
The intended audience for this course is doctoral
students with research interests in computer architectures, software systems
(programming languages, compilers, operating systems), and applications.
COURSE STRUCTURE: The course will consist
of lectures based on material from two textbooks (recommended) supplemented
with current research papers. There will be both written and programming
assignments as well as a significant term project (which can be done in groups
of 2-3 students) focusing on writing a parallel server application.
G22.3033.006 Computational Biology
The genome contained within
a human cell is very large and complex. It holds all of the genetic information
necessary for its creation and function encoded with a total of six feet
of DNA. The goals of the Human Genome Initiative (HGI), as framed by the
National Institutes of Health and the Department of Energy, were to generate
a complete map, containing well-defined markers, and to sequence the entire
human genome within a short period. The sequencing aspects of this project
had to deal with approximately 3 billion base pairs. A large number of genes
(30,000) were identified but remain to be characterized in terms of biochemical,
developmental, and clinical criteria. Additionally, the development of approaches
to globally, and quantitatively, characterize message (RNA transcripts, which
direct synthesis of specific proteins) will also play a major role in virtually
every aspect of biological, pharmaceutical and clinical research. The science
of computational genomics and bio-informatics have been created out of this
massive sea of sequence data and the need to establish functionality of genes
largely based on similarities discerned at the level of the DNA code; bypassing
the need for extensive biochemical characterization.
This emerging subfield relies
on some classical and many novel mathematical, statistical and algorithmic
ideas that are essential to accomplish this task. This course deals with
mainly these mathematical and computational approaches. The course is self
contained, developing the biological, statistical, probabilistic and algorithmic
tools and techniques along the way
G22.3033.007 Formal Verification
Methods for Software Engineering
This course counts toward the specialization in Software Engineering.
Course description is not
Topics in Problem Solving
grade on MS Core Exam
This course revolves around
several new problems 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. At the same time, it will be part of an evolving
"Omniheurist" website that we expect will get many visitors over the years.
For each puzzle, students will
be divided into teams. One or more teams researches the literature and works
out a winning strategy. That team must present the previous work, the strategy
and implements it. Another team works on the interface so people can play
it interactively and so that strategies can work on it. Students in the class
will take turns recording the class discussion.
The course is for highly motivated,
mathematically adept students. It is open to supported PhD students and master's
students who have passed the Core exam. Class size is limited to 30 students.
Algorithmic and programming knowledge are the main prerequisites. It also
helps if you are familiar with a rapid prototyping language such as Mathematica,
K, Python, or some other language in which you are completely fluent.
Requirements: There are 5 projects,
but no textbook and no exams. Class participation however is mandatory in
at least 12 out of 14 classes. Also, you will need to find relevant literature
(mostly without guidance). We will take attendance.
Are you suited for the course?
Here is the style of problem we will attack. there is a board having two
supports, but the supports are both placed to the left of the center. A weight
is placed farther to the left to prevent the board from tipping. You play
a game in which you and your opponent are given 7 weights of various sizes
each. You are to put your weights on the board in alternate moves. If the
board tips as the result of a weight just placed, then the player who placed
the weight loses. If nobody loses after all 15 (1 + 7 + 7) weights are placed,
then the weights are removed one at a time. If the board tips as the result
of a weight just removed, then the player who removes the weight loses. You
are to design a computer winning strategy.
see the course homepage
This course counts toward
the specialization in Distributed Computing.
An application server is a rich,
highly portable software that runs on a middle tier and handles all application
operations between browser-based pervasive devices and back-end databases
and business applications. Application servers provide a platform independent
programming interface for developing portable Java applications. Application
servers also facilitate the integration of legacy applications via on-the-fly
transformation of XML-formatted data, and support a wide variety of XML-enabled
client channels that include traditional web clients and a growing set of
smart "pervasive" devices. As emerging standards such as SOAP enable a new
generation of "web services" that allow systems to make remote procedure
calls to other systems over the Internet, application servers are setting
the stage as modern platforms for Web Service platforms initiatives, application
server appliances, Web services and wireless applications. This course concentrates
on architecting, designing, and developing persistent software application
using application server technology. Throughout the course, students are
exposed to the evolution of application server architectures that started
in the mid 1990s, and experiment with corresponding approaches based on traditional
client-server technology, CGI frameworks, page-based extended HTML environments,
distributed object computing platforms, object management architectures,
component-based computing environments, and web services platforms. The course
conveys the necessary skills to select the proper application server architecture
based on project requirements and scale. The course also explains how to
integrate an application server into an existing Web site, as well as how
to implement an application server-based Web application from the ground
up. Students will learn how to configure and operate application servers
for production environment taking advantage of features available in mainstream
commercial frameworks such as scalability, concurrency, security, fault tolerance,
auto-deployment, communications support, development environment, and monitoring
tools. As they design and implement applications using application server
technologies, students will learn how to identify application patterns that
lead to the most effective use of the various services provided within application
server frameworks. The design and implementation of the persistence and legacy
application integration layers using related application server technology
will be particularly emphasized. Case studies provided as part of the course
focus on how medium- to large-size sites manage the complexities inherent
in these endeavors. The case studies will help students get a firm understanding
of how application servers work and how to best deploy complex applications
in a real-world situation. Although, the course will strive to provide a
complete coverage and classification of application server technology, attempts
will be made whenever possible to select open source technologies for experimentation
and classification of application server technology, attempts will be made
whenever possible to select open source technologies for experimentation purpose.
As part of the course, students will be exposed briefly to next generation
reflective, multimedia- and agent-enabled application servers with support
for model driven architectures.
background in artificial intelligence is recommended. Good programming skills,
preferably in C++ or Java, are required.
This course provides a broad
introduction to artificial intelligence agents with an emphasis on multiagent
systems. Topics include agent architectures, inter-agent communication,
teamwork, distributed rational decision making, agent modeling, and multiagent
learning. It is a programming-intensive course by the end of which, the
student will have implemented a full-fledged team of autonomous agents in
the RoboCup soccer simulator. At the end of the course, teams of soccer-playing
agent will compete against each other in a tournament.
A preliminary version of the
syllabus is available at http://www.research.att.com/~pstone/Courses/2001nyu/syllabus.ps
| contact email@example.com