Graduate Special Topics in Computer Science
NOTE: for descriptions
of standard graduate computer science courses, see Graduate Course Descriptions.
G22.3033-001 Experiments in Motion Capture
This class is open to students of various backgrounds (Art, Dance, Science,
Film, Architecture, Music etc etc -- (It is listed as a computer science
class, but no strong programming skills are necessary). Students should be
able to use computers in a creative way. We will teach all the software
components to you. Supported platforms are MAX/MSP Jitter, Maya, 3D Studio
Max, Matlab, C++, and many other software environments.
Motion Capture is the process of recording human movement (or other
movement) in physical space, and transforming that information in a
computer-usable form. The use of Motion Capture has been become of increased
popularity, due to recent technological advances, and increased demand in
the entertainment industry. One year ago NYU CIMS put a new state-of-the-art
Motion Capture lab in place, which includes 10 high speed VICON cameras, a
professional dance floor, lots of silly body-suits, large retro-silver beach
balls, and a real-time 3D capture server that links to various graphics
environments. The lab supports many art & science projects around this
technology. This includes applications in dance, music, game play, digital
puppetry, animation, and medicine.
This class gives students the opportunity to learn this new technology and
develop art or science projects around it. The class will be held in the
lab. First the class will go through the "motion capture pipeline" with a
sequences of exercises (be prepared to "suit up" and get some physical
exercises). After that, the main focus of the class will be to develop group
projects. In parallel, we will also cover various topics of motion capture,
and what other people are doing with it, with a focus on art & entertainment
As one project option, we offer the http://squidball.net environment, a
large interactive motion capture game, first tested past summer on a 4000
player audience. After spring break, some groups will be able to collaborate
with another class called "PlaySpaces: Play and Public Space" by Katie Salen
at Parsons School of Design to further build on this interactive platform.
See the course homepage at
for more information.
G22.3033-002 Introduction to Computational Number Theory & Algebra
Note: this course description is from fall 2003.
Pre-requisites: No formal prerequisites, although some exposure to probability theory and
abstract algebra (at the undergraduate level) would be helpful. The text
will be a manuscript that is currently in preparation, and it includes all the
necessary mathematical background.
This course is an introduction to computational aspects of number theory and
algebra. The topics to be covered (tentatively) include: long integer arithemtic,
Euclid's algorithm and its applications, primality testing, factorization of polynomials
and integers, algorithms for discrete logarithms, and lattice basis reduction and its applications.
The selection of topics is geared towards those that are especially useful in modern cryptography, but
are anyway interesting in their own right.
Grades will be based on problem sets.
G22.3033-003 Foundations of Machine Learning
Note: this course description is from spring 2005.
Prerequisites: Familiarity with basics in linear algebra, probability, and analysis
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
- Perceptron, Winnow,
- Support vector machines (SVMs)
- Kernel methods
- Decision trees
- Regression problems and algorithms
- Ranking problems and algorithms
- Halving algorithm, weighted majority algorithm, mistake bounds
- Learning automata, Angluin-type algorithms
- Reinforcement learning, Markov decision processes (MDPs)
Note: except for a few common topics briefly addressed in the
fall 2004 Machine Learning course, there is no overlap in
the material of the two courses. Students may get credit for both.
G22.3033-005 Internet/Intranet Protocols & Applications
Note: this course description is from spring 2005.
Prerequisites: Knowledge of networking principles, ability to program in
Java, ability to write large (10s of pages) programs
Internet and Intranet Protocols and Applications studies the world's
most widely used application level network protocols and software systems.
We study protocols, such as HTTP for the Web, and SMTP, POP3, and IMAP
for email. We consider protocol design issues, especially as they
influence functionality, reliability and performance. We carefully read
protocol specifications, such as the HTTP specification, RFC 2616.
We study the systems which use these protocols, clients and servers. We
also study intermediate systems which enhance performance, such as
caching proxies and content delivery services.
We will examine complex functionality and performance issues, such as
time-out management and high-performance concurrent servers.
Programming assignments ask students to write clients and servers to the
sockets interface. Students write several small programming assignments
and one large project. Guest lecturers may present current research and
practice on a subset of the following issues: reliable internet
multicast, the design and implementation of the Apache Web server,
performance issues in WWW servers, and Internet security.
The last quarter of the course may examine research that enhances
internet and Web performance.
G22.3033-005 Analysis of Reactive Systems
Note: this course description is from fall 2004.
Prerequisites: Some background in
algorithm design, familiarity with the language of first-order logic,
and parallel programs.
Recommended: Temporal Verification of Reactive Systems: Safety
by Zohar Manna and Amir Pnueli, Springer-Verlag
Reactive systems are systems whose role is to maintain an ongoing
interaction with their environment rather than produce some final
value upon termination. Typical examples of reactive systems are Air
traffic control system, Programs controlling mechanical devices such
as a train, a plane, or ongoing processes such as a nuclear reactor.
The Formal Methods approach to software construction is based on
viewing a program and its execution as mathematical objects and
applying mathematical and logical techniques to specify and analyze
the properties and behavior of these objects. The main advantages of
the formal approach to software construction is that, whenever
applicable, it can lead to an increase of the reliability and
correctness of the resulting programs by several orders of
Several approaches to the verification of reactive systems are
available, the most prominent of which are Algorithmic (model
checking) and Deductive verification. This semester we concntrate on
deductive verification, where we use theorem-proving techniques to
establish the correctness of reactive programs relative to their temporal
specifications. We will be using computer-aided theorem provers such
as PVS and STeP for verifying the properties of programs.
* The computational model of Fair Discrete Systems (FDS).
* A simple programming language (SPL) and its translation into FDS.
* The specification language of linear temporal logic (LTL).
* The PVS Theorem prover. Encoding FDS's and LTL within PVS.
* Verifying invariance properties.
* Algorithmic construction of auxiliary invariants.
* Verifying progress properties.
* The CHAIN and WELL rules.
* Verification Diagrams.
* Verifying progress under compassion.
* Verifying general LTL properties.
G22.3033-007 Random Graphs
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" or (personal favorite)
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
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
More Info: Contact Prof Spencer directly at
or check out his website:
and click on
click on Random Graphs under Topics. The course will
be reasonably similar to that given in spring 2004.
G22.3033-009 Rapid Visualization
Note: this course description is from spring 2005.
Prerequisite: WWW Programming or equivalent Java experience.
The principal challenge facing technology companies today is to offer new,
relevant products that keep up with the explosive growth in bandwidth and
storage on networks and computers. To remain competitive in a do-or-die
climate, innovative product houses - from IDEO to Cooper Interactive to Frog
to HP - have embraced new, cost effective rapid prototyping methods. To get
the best results from costly development cycles, these companies develop
rich scenarios around the end-user, and use creative methods early in the
process to envision and iterate a range of product outcomes. Rapid
Visualization, with tools drawn from various creative disciplines,
dramatically increases the volume and quality of ideas that enter the new
product pipeline, and accelerates their time to market.
This course introduces these methods with case studies pulled from, among
other sources, the instructor's hands-on experience directing a rapid
visualization team at AT&T Labs-Research. Armed with a new set
of techniques -
storyboards, service and use-case scenarios,
and even faux ads - students will gain a practical understanding of the
value of rapid visualization to new product development. Students will apply
these methods to the development of a novel software tool.
Is a picture worth a
thousand lines of code?
G22.3033-010 Data Warehousing & Mining
Note: this course description is from spring 2005.
We live in the Age of Information. The importance of collecting data that reflects a business or scientific
activity to achieve competitive advantage is widely recognized now. Advanced systems for collecting
data and managing it in large databases are in place in most large and mid-range companies. However,
the bottleneck of turning this data into your success is the difficulty of extracting knowledge about the
system from the collected data.
What goods should be promoted to this customer?
What is the probability that a certain customer will respond to a planned promotion?
Can one predict the most profitable securities to buy/sell during the next trading session?
Will this customer default on a loan or pay back on schedule?
What medical diagnosis should be assigned to this patient?
How large are the peak loads of a telephone or energy network going to be?
Why does the manufacturing facility suddenly start to produce defective goods?
These are all the questions that can be answered if information hidden in a database can be found
explicitly and utilized. Modeling the investigated system and discovering relations that connect variables
are the subject of data mining.
The course will introduce concepts and techniques of data mining and data warehousing, including
concept, principle, architecture, design, implementation, application of data warehousing and data
Data warehousing and OLAP technology for data mining
Descriptive data mining: characterization and comparison
Classification and prediction
Mining complex types of data
Applications and trends in data mining
G22.3033-012 Values Embodied in Information & Communication Technologies
This experimental course is for students with technical computer science or engineering backgrounds
who are interested in learning about social, political, and ethical implications of their
field, and for students with humanistic, social science, and communications backgrounds who are
interested in learning more about new technologies that that touch virtually all parts of our lives.
The course will be divided roughly into two parts. In the first, we will study a tradition of work in the
philosophy and social study of technology that seeks to understand the rich and sometimes troubling
relationship between social and political factors and development and deployment of technology. We
will ask questions like: Is technology neutral? Who should make decisions about technical developments?
What is the role of scientists and engineers? Does technology make the world better, or worse?
The second part of the course will be devoted specifically to information technology and new media
analyzing specific cases the Internet, search engines, web-cookies, anonymity online, data
mining -- according to themes and principles learned in the first. Visiting speakers will include
technology activists as well as systems designers who think about values as they pursue their work.
Although the course had been taught before in the Department of
Culture and Communication,
in spring 2004 we sought for the first time a mix of students with
This change is particularly important for the final project where
pair students with technical and non-technical backgrounds. Final
project may involve analysis of selected systems from
both technical and values perspectives, or even (depending on
technical skill level) design and/or implementation of system
prototypes inspired by particular social values. In addition to final
projects, students will be expected to come to class prepared to
discuss readings and occasionally to make short presentations.
For more details, see the spring 2004 course homepage at
G22.3033-013 Advanced Topics in Machine Learning
Prerequisite: some background in machine learning.
Having taken either "Machine Learning and Pattern Recognition"
or "Foundations of Machine Learning" is recommended, but
not an absolute requirement.
This course is primarily intended for PhD students whose research work
is related to machine learning, and for advanced MSc students who
intend to do thesis work on machine learning. The course will be a
combination of seminar-style sessions reviewing key papers from the
literature and tutorial lectures on advanced research topics.
The topics covered in the course will include:
- Advanced topics in graphical models, approximate inference
- Variational methods for inference and learning
- Unsupervised learning, dimensionality reduction,
and independent component analysis
- Advanced sampling methods for inference and learning
(hybrid Monte-Carlo, contrastive divergence)
- Markov random fields and conditional random fields
- Energy-based models
- Advanced discriminative methods for sequence labeling
- Advanced topics in reinforcement learning and
Markov decision processes
| contact firstname.lastname@example.org