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 projects.

As one project option, we offer the 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 of algorithms.

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
  • 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.

Textbooks: 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 magnitude.

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.

Course topics:

* 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) "Erdos Magic." 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

More Info: Contact Prof Spencer directly at or check out his website: b 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 - concept sketches, 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 mining.

Data warehousing and OLAP technology for data mining
Data preprocessing
Descriptive data mining: characterization and comparison
Association analysis
Classification and prediction
Cluster analysis
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 diverse backgrounds This change is particularly important for the final project where ideally we 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

top | contact