Graduate Special Topics in Computer Science

NOTE: for descriptions of standard graduate computer science courses, see Graduate Course Descriptions.

G22.3033.01 Computer Security

see the course homepage

G22.3033.02 Robust Geometric Computation

Prerequisites: Fundamental Algorithms, knowledge of C or C++.

Algorithms for constructing convex hulls and Voronoi diagrams, mesh generation and planning robot motion are examples of geometric algorithms. Such algorithms arise in many applied areas including numerical simulation, computer graphics, robotics and engineering design. Although there is much theoretical investigation of such algorithms, the implementation issues are just beginning to be studied. Foremost among the practical concerns is numerical robustness.

This course shall focus on a new approach to robustness known as ``exact geometric computation''. We are interested in both practice and theory, and will investigate the software infrastructure necessary to make exact computation viable. One realization of this is found in our Core Library project. A software term project is expected.

For more details see the course homepage

G22.3033.03 Internet & Intranet Protocols & Applications

Prerequisite: Data Communication and Network Design (G22.2262) or equivalent or permission of the instructor (send email to

This course studies the world's most widely used application level network protocols and software systems. We study protocols, such as HTTP, NNTP and SMTP. We consider protocol design issues, especially as they influence reliability and security. We carefully read protocol specifications, such as the HTTP specification, RFC 2068. We study the systems which use these protocols, clients and servers. We also study intermediate systems which enhance security, such as proxies and firewalls, and performance, such as network caches. Programming assignments ask students to write clients and servers to the sockets interface. We will examine complex functionality and performance issues, such as time-out management and high-performance concurrent servers. We do several small and one large programming assignment. In past offerings students have implemented an HTTP 1.1 server and a caching proxy. We study the design of network systems, such as firewalled corporate intranets. Guest lecturers will present current research and practice on some of the following issues: Internet security, wide area performance management, Web caching, and real-time networking. The last quarter of the course examines research that enhances internet and Web performance.

G22.3033.06 Survey of Computational Logic

Prerequisites: For Computer Science Students: Fundamental Algorithms (should have been completed with the grade of A); Theory of Computation (should either have been completed with the grade of A, or taken concurrently with this course; students without this second prerequisite may enroll with special permission of the instructor [].) For Mathematics Students: Completion of at least 3 graduate courses, including linear algebra and fundamentals of analysis, with an average grade at least B+.

The course will be conducted in 'advanced' style, largely using recommended readings and class notes/handouts. Some computer work may be assigned at a later date. A term paper on a topic approved by the instructor is also required.

Textbooks: Patrick Suppes, Introduction to Logic Patrick Suppes, Axiomatic Set Theory (Dover)

Topics to be Covered: Predicate logic. The role of set theory in logic. Set-theoretic primitives. Encoding of integers in set theory. Undecidability results; Chaitin's form of Godel's theorem. Notion of a 'proof verifier'. Herbrand's theorem. Decidable sublanguages of set theory and other parts of mathematics. . Techniques for systematic formal use of 'subtheories'. Resolution theorem proving. Formal verification of programs. The Knuth-Bendix treatment of equational systems. Equational methods specialized for systems of recursive definitions; the Boyer-Moore verifier system.

G22.3033.09 Computation in Biology

Prerequisites: G22.1170 (Fundamental Algorithms) and C/C++. Some elementary statistics desirable, but a quick overview of the required math in class.

At the end of this millennium we are witnessing the beginning of a new era in the biological sciences, an era that holds the potential of revolutionizing (or endangering, depending one one's take) almost every aspect of human life. Ethical issues aside, the fact remains that the "Century of Biology" is arriving at a brisk pace and even if a fraction of the hype is true, its impact will be profound.

This course will provide a well-rounded overview of the field of Computational Molecular Biology today. Although the focus of the class will be on computational techniques for analyzing biological data, we intend to address a host of other issues as well, including:

  • elementary biology
  • biotechnology methods used to collect the data under consideration
  • accessing and using public repositories of biological information

At the end of the class, we expect that the student will have a good understanding of the important problems in the field as well as an appreciation for the kind of skills required for performing successful research.

G22.3033.10 Foundations of Modern Type Systems

Prerequisite: G22.3110 (Honors PL) or permission of the Instructor

One of the most important features of any programming language is its type system. Much research has been devoted to developing new type systems, which has led to the introduction of polymorphic functional languages, object oriented languages, and languages with advanced module facilities. This class will investigate the theoretical foundations of type systems and their practical impact upon language design and implementation. Topics to be covered include: The typed lambda calculus in its many forms, the semantics of types, models of inheritance and subtyping, higher-order type systems with modules, and practical aspects of type system design.

top | contact