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/ Math: G63.2931)

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 WWW

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

At the end of this course, you should be able to make sense of a good portion of current cryptography research papers and standards.

### G22.3033.004 Architecture & Programming of Parallel Computers

PREREQUISITES: Senior undergraduate-level or introductory graduate-level courses in computer architecture and operating systems.

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 yet available.

### G22.3033.009 Special Topics in Problem Solving

Prerequisites: Passing 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.

### G22.3033.010 Webbased Visualization

see the course homepage

### G22.3033.011 Application Servers

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.

### G22.3033.012 Autonomous Multiagent Systems

Prerequisites: Some 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

top | contact webmaster@cs.nyu.edu