Graduate Special Topics in Computer Science

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

G22.3033-001 Machine Learning


  • a course in algorithms
  • familiarity with Unix
  • programming proficiency
  • no fear of math
  • Machine Learning is the study of computer programs that automatically improve their performance through experience. This course covers the theory and practice of machine learning from a variety of perspectives. We cover topics such as learning decision trees, neural network learning, statistical learning methods, genetic algorithms, explanation-based learning, and reinforcement learning. The course covers theoretical concepts such as inductive bias, the PAC and Mistake-bound learning frameworks, minimum description length principle, and Occam's Razor. Programming assignments focus on hands-on experiments, such as neural network learning for face recognition, and decision tree learning from databases of credit records.

    G22.3033-005 Computational Logic and Set Theory

    The role of logic in mathematics. Basics of set theory and the von Neumann encoding of integers. Propositional and predicate calculus. Some decidability results for propositional calulus and elementary set theory. Predicate calculus and the notion of model. A quick look at SETL - a set-theoretic programming language. The Godel completeness theorem. Undecidabilty and unsolvability results. Chaitin's theorem and its consequences. Undecidabilty and unsolvability results. Hereditarily finite sets, Godel's incompleteness theorem. Basic facts concerning cardinality, large cardinals, inner models of set theory. Axioms of reflexivity. MLSS decidabilty and the tableau method. Survey of the verifier system. Proof primitives, some inital proofs. Basic definitions for set theory. The theory mechanism Basic definitions for analysis. Some verifier system internals: syntax trees, substitution.

    G22.3033-006 Application Servers

    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 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-007 Special Topics in Problem Solving

    Prerequisites: A- or better in Fundamental Algorithms. Comfort with some prototyping language and with interfaces to the web.

    Interesting problems usually can't be solved in closed form or using polynomial algorithms. Ambulances can't be scheduled based on rough hunches in a castrophe. Shipping companies must exploit non-linear constraints involving profit margins, demand, and volume, and still keep the boats moving. The same goes for optimal substring search for microarray design or optimal portfolio management. The people who program the practical solutions to these problems comprise the elite of their technical organization. They are sought after throughout their careers, because of their versatality, imagination, and programming talent. I call them omniheurists -- solvers of all problems.

    This course aims to develop your skills as an omniheurist. We will study problems that require heuristics and approximation algorithms. The heuristics include branch and bound, simulated annealing, tabu searching, evolutionary algorithms, and adaptive gradient methods. Approximation algorithms to NP-complete problems will help for subproblems. The problems take minutes to explain but the challenge they pose will keep you busy in a creative way for a few hours. I don't promise an easy course, but I believe you will enjoy this class and find it useful.

    This is a course for students who can think creatively about algorithms and are willing to prototype them. I will spend an hour teaching the prototyping language I use (for all of my research) but you are free to use any you like.

    In the fall of 2002, the course emphasis will be on problem-solving in two areas: distributed computing and biological computing. The distributed computing projects will involve adversarial games in which distributed computing goals (e.g. ambulance pickup; competitive consumption) must be achieved in the context of an adversary who can cause failures or otherwise try to thwart you. The biological computing projects will involve combinatorial problems having to do with verifying DNA sequences using Crick-Watson pairing, the reconstruction of sequences using restriction enzymes, the use of combinatorial design for experiments, and and so on. The course will present all the necessary domain knowledge. At the end, you will be able to face a difficult problem in an area where the domain is not familiar to you, but still be able to contribute a computational solution.

    G22.3033-010 Topics in Cryptography

    This course will deal primarily with public-key cryptography; specifically, identification schemes, signature schemes, and asymmetric encryption schemes. The emphasis will be on practical cryptographic schemes while at the same time focusing on rigorous, mathematical security analysis. Although there are no formal pre-requisites, the course "Introduction to Cryptography" (G22.3033-003) would be quite helpful. In any case, a student should have knowledge of some of the rudiments of cryptography (or be willing to read up on it); also helpful is some exposure to complexity theory, algorithms, and probability theory.

    top | contact