16:198:500Proseminar in Computer Science (1) Several sections are offered each term, introducing students to research activities inside the department. Format varies. Required for all new full-time students in Ph.D. program.

16:198:505Computer Structures (3) Hardware subsystems. Computer organization, memory systems, arithmetic, I/O, control, data communications, parallel processors, RISC architectures, and other topics of current interest. Levy, Paull. Prerequisite: Admission requirements.

16:198:507(F) Advanced Computer Architecture (3) Advanced topics in computer architecture, including advanced processor design, models and workload characteristics for multiprocessor systems, memory and cache coherence and consistency, multiprocessor architecture, and I/O. Bianchini, Iftode, Martin, Nguyen. Prerequisite: 16: 198:505.

16:198:509(F) Foundations of Computer Science (3) Introduction to first-order logic, emphasizing methods used in computer science. Introduction to mathematical models of computation, especially deterministic and nondeterministic Turing machines, computability theory, and space and time complexity theory. P and NP. Allender, Szegedy. Prerequisite: Admission requirements.

16:198:510Numerical Analysis (3) Derivation, analysis, and application of methods used to solve numerical problems with computers; solution of equations by iteration, approximation of functions, differentiation and quadrature, differential equations, linear equations and matrices, least squares. Gerasoulis, Richter. Prerequisites: Ability to program; a minimum of four terms of undergraduate mathematics, including calculus and linear algebra.

16:198:513Design and Analysis of Data Structures and Algorithms I (3) Worst case, average case, and amortized analysis. Data structures: search trees, hash tables, heaps, Fibonacci heaps, union-find. Algorithms: string matching, sorting and ordering statistics, graph algorithms. NP-completeness. Farach-Colton, Fredman, Kalantari, Khachiyan, Steiger, Szemer�di. Prerequisites: Admission requirements; familiarity with Prim and Kruskal minimum spanning tree algorithms and Dijkstra shortest path algorithm.

16:198:514(S) Design and Analysis of Data Structures and Algorithms II (3) Advanced data structures, approximation algorithms, probabilistic and randomized algorithms, number-theoretic algorithms, and parallel computation. Fredman, Khachiyan, Steiger. Prerequisite: 16:198:513.

16:198:515(F) Programming Languages and Compilers I (3) LR parsing; attributed grammars; code generation; types and polymorphism; programming language paradigms: logic, functional, object-oriented; data abstraction; formal semantics: axiomatic l-calculus, denotational. Borgida, Kremer, Ryder. Prerequisites: A first course in compilers (equivalent to 01:198:415) and 16:198:513 (both are possible corequisites with permission of instructor).

16:198:516(S) Programming Languages and Compilers II (3) Advanced topics in compiler design and modern programming language paradigms chosen from optimization, especially register allocation methods; data flow analysis techniques, including interprocedural analysis; parallelization of sequential programs; incremental compilation. Kremer, Ryder. Prerequisite: 16:198:515.

16:198:519Operating Systems Theory (3) Operating system basics; process management; synchronization, memory management; interprocess communication, network protocols, RPC, client-server architectures; file systems and distributed file systems; scheduling and security; current trends and case studies. Bianchini, Iftode, Martin, Nath, Nguyen. Prerequisite: 01:198:416 or 16:198:505 or equivalent.

16:198:520Introduction to Artificial Intelligence (3) Overview of artificial intelligence. Basic problems and methods; deductive inference, declarative programming, heuristic search; reasoning and representation in perception, planning, and learning. �DeCarlo, Hirsh, Kulikowski, McCarty, Steinberg, Stone. Prerequisite: Admission requirements.

16:198:521Linear Programming (3) Linear inequalities, extreme points and rays, fundamental theorems. Optimality and duality. Geometric view. Primal and dual simplex methods. Degeneracy. Primal-dual method. Sensitivity. Basis factorization, implementation issues. Column generation. Structured models. Network simplex method and unimodularity. Polynomial-time algorithms for linear programming. Grigoriadis, Kalantari, Khachiyan. Prerequisites: Linear algebra and admission requirements.

16:198:522(S) Network and Combinatorial Optimization Algorithms (3) Negative and minimum mean cycles. Maximum flows and minimum cuts. Combinatorial implications. Dynamic trees and scaling. Parametric flows. Minimum cost-flow networks. Generalized, multiterminal, and multicommodity flows. Sparsest cuts. Nonbipartite cardinality and weighted matching. T-joins. Spanning trees and matroids. Approximation algorithms. Grigoriadis. Prerequisites: 16:198:503 or 513 or equivalent, elementary knowledge of linear programming, or permission of instructor.

16:198:523(F) Computer Graphics (3) Introduction to computer image synthesis: modeling, animation, rendering, and geometric techniques. Topics include geometric transformations, modeling hierarchies, viewing and visibility, animation techniques, curve and surface design, lighting, shading, and ray tracing. DeCarlo. Prerequisites: 01:198:323, 344, 16:198:510, or 513; fluency in C or C++.

16:198:524(S) Nonlinear Programming Algorithms (3) Convex sets and functions. Unconstrained and constrained optimization. First- and second-order optimality conditions. Duality theory. Conjugate and quasi-Newton methods. Line search and feasible direction methods. Quadratic programming, linear complementarity. Approaches to global optimization. Karmarkar's algorithm. Path-following Newton methods. Matrix scaling. Kalantari. Prerequisites: 16:198:521 or equivalent, four terms of calculus.

16:198:525,526Advanced Numerical Analysis (3,3) In-depth analysis of selected topics from the following: linear algebraic systems; computation of eigenvalues and eigenvectors; numerical solution of initial- and boundary-value problems for ordinary differential equations; spline and Fourier approximation. Richter. Prerequisite: 16:198:510 or equivalent.

16:198:527(S) Computer Methods for Partial Differential Equations (3) Principles of advanced numerical analysis and computer programming for the solution of partial differential equations. Introduction to finite element methods. Theory of stability and accuracy of methods for hyperbolic, parabolic, and elliptic problems. Emphasis on applications in science and engineering. Richter. Prerequisites: Background in numerical analysis, computer programming, and elementary theory of partial differential equations.

16:198:528(S) Parallel Numerical Computing (3) Analysis of numerical algorithms for a variety of parallel architectures. Parallelization of existing algorithms. Mapping of algorithms onto various architectures. Techniques for developing fast parallel numerical algorithms. Algorithms implemented on existing simulators or actual parallel machines. Gerasoulis. Prerequisites: Numerical algorithms (01: 198:323 or 16:198:510) and nonnumerical algorithms (01:198:344 or 16:198: 503); basics of Unix, Fortran, or C.

16:198:529(F) Computational Geometry (3) Design and analysis of algorithms for geometric problems. Topics include proof of lower bounds, convex hulls, searching and point location, plane sweep and arrangements of lines, Voronoi diagrams, intersection problems, decomposition and partitioning, farthest-pairs and closest-pairs, curved and rectilinear geometry. Szegedy or Steiger. Prerequisite: 16:198:513. Recommended: 16:198:514.

16:198:530(F) Principles of Artificial Intelligence (3) Introduction to current research problems and methods in artificial intelligence. Models of real-world tasks, including uncertainty, reward, and causality; model-based reasoning for perception and action. Overview of current research applications. DeCarlo, Hirsh, Kulikowski, McCarty, Steinberg, Stone. Prerequisite: 01:198:440 or permission of instructor.

16:198:531(F) Artificial Intelligence Software: Techniques and Languages (3) Programming tools needed to write or understand AI systems. Search, pattern matching, LISP, logic programming, objects and frames, rules. Steinberg. Prerequisite: 16:198:520.

16:198:532(S) Foundations of Knowledge Representation (3) Knowledge-representation problem in AI, with an emphasis on the use of logical techniques. Computational logic. Modal logics of time, action, knowledge, belief. Formal analysis of reasoning that is not strictly deductive (e.g., nonmonotonic reasoning, abductive reasoning). Approaches to tractable reasoning. Borgida, McCarty. Prerequisites: 16:198:509, 520, or permission of instructor.

16:198:533(S) Natural Language Processing (3) Survey of models and reasoning required in computational systems that use natural language to communicate. Linguistic description and computational models of syntax, semantics, discourse, and conversation. Algorithms for parsing, generation, dialogue management, and collaboration. Stone. Prerequisite: 16:198:530 or permission of instructor.

16:198:534(S) Computer Vision (3) Provides an understanding of processes involved in formation of images of visual scenes; examines how computational approaches for transforming, estimating, or recognizing such images are formulated and implemented. Course also looks at where these methods can and have been applied. Stresses implementation and practical use of a wide variety of vision algorithms. DeCarlo. Prerequisite: 16:198:530 or permission of instructor.

16:198:535(S) Pattern Recognition Theory and Applications (3) Pattern recognition as an inductive process, statistical classification, parametric and nonparametric methods, adaptive methods, error estimation, applications in image processing, character, speech recognition, and diagnostic decision making. Kulikowski. Prerequisite: 16:198:530.

16:198:536(S) Machine Learning (3) Survey of machine learning, including decision-tree and rule learning systems, neural networks, Bayesian approaches, nearest neighbor methods, PAC-learning, genetic algorithms, reinforcement learning, and inductive logic programming. Hirsh. Prerequisite: 16:198:530 or permission of instructor.

16:198:538(S) Complexity of Computation (3) Complexity classes, reducibilities, and complete sets. Relation- ships between time and space complexity, between serial and parallel computation, and among deterministic, probabilistic, and nondeterministic computation. Complexity theoretic notions of randomness. Allender. Prerequisites: 16:198:509, 513.

16:198:539(F) Theory of Computation (3) Mathematical theory of computing machines. Computable functions, recursive and recursively enumerable sets, recursion and fixed-point theorems, abstract complexity and complexity theoretic analogues of aspects of recursive-function theory, algorithmic (Kolmogoroff) complexity theory. Allender. Prerequisite: 16:198:509 or equivalent.

16:198:540(S) Combinatorial Methods in Complexity Theory (3) Lower bounds in circuit, communication, and proof complexity. Interactive proof systems, approximation, and consequences. Allender, Szegedy, Szemer�di. Prerequisites: 16: 198:509, 513.

16:198:541(S) Database Systems (3) Relational data model. Relational query languages and their expressiveness. Dependency theory and relational normalization. Physical database design. Deductive databases and object-oriented databases. Optimization of relational queries. Borgida, Imielinski. Prerequisites: 01:198:336 or equivalent; 16:198:513. Recommended: 16:198:509 or equivalent.

16:198:545(S) Distributed Systems (3) Basic mechanisms for building distributed systems (remote- procedure call, synchronization, transactions), components of distributed operating systems (file systems, distributed shared memory), and issues in wide-area distributed systems (security, wide-area clustering). Bianchini, Iftode, Martin, Nguyen. Prerequisite: 16: 198:519.

16:198:547(F) Secure Computing, Applied to E-Commerce (3) Foundations of secure distributed computing, including cryptographic algorithms, distributed access-control, and certain principles of software engineering. Minsky

16:198:552(S) Computer Networks (3) Computer network protocols and architecture. Protocol design. Internetworking and TCP/IP. Medium access, routing, and traffic control. Network security. Integrated and differentiated services. Network programming. Network simulation. Nath, Nguyen. Prerequisite: 01:198:416.

16:198:553(F) Design of Internet Services (3) Internet applications, services, and programming models. Middleware, proxy caches, and directory services. Web server architecture and commodity clustering systems for scalable services. Electronic commerce. Multimedia streaming. Internet security and firewalls. Nath. Prerequisite: 16:198:552.

16:198:556(F) Parallelism: Algorithms and Complexity (3) Models of parallelism. Complexity classes. Lower bounds, simulations, separation results. Algorithms: arithmetic, comparison tasks, matrices, graphs. Routing and scheduling problems. Architectures and structures. Fredman, Steiger, Szemer�di. Prerequisite: 16: 198:513. Recommended: 16:198:505, 514.

16:198:580(S) Topics in Computers in Biomedicine (3) Survey of computational methods in biology or medicine; topics vary from instructor to instructor and may include computational molecular biology, medical reasoning, and imaging. Farach-Colton, Kulikowski. Prerequisite: 16:198:513 or 520, depending on the term, or permission of instructor.

16:198:583(F) Topics in Software Design (3) In-depth study of selected topics in the areas of software engineering, distributed computing, and electronic commerce and security. Course leads to research in these areas. Minsky. Prerequisites: Proficiency in at least two of the following areas: database systems, operating systems, programming languages, and AI.

16:198:587(S) Expert Systems (3) Scope and characterization of expert systems. Consultation processes and expertise. Knowledge acquisition and representation. Methods of inference under uncertainty and problem-solving strategies. Review of existing expert systems and specialized languages. Kulikowski. Prerequisites: 16:198:530 and permission of instructor.

16:198:594(S) Topics in Programming Languages (3) Advanced topics in the design and implementation of programming languages (e.g., compiling for parallel architectures, data-flow analysis and its applications, very high-level program optimization, automatic programming, theory of programming languages). Ryder. Prerequisite: 16:198:515.

16:198:596(S) Topics in the Foundations of Computer Science (3) Careful study of papers on the topic selected for the given term. Examples include parallelism and zero-knowledge proofs, randomness and information theory, probabilistic aspects of computation, topics in complexity theory. Allender, Fredman, Steiger, Szemer�di. Prerequisites: 16:198:509 and, depending on the topic, 16:198:538 and/or 539 and/or 540.

16:198:598Topics in Artificial Intelligence (3) A special topics course covering particular areas of research in artificial intelligence. Prerequisite: 16:198:530 or permission of instructor.

16:198:601,602,603,604,605,606 Selected Problems in Computer Science (BA,BA,BA,BA,BA,BA) In-depth study of a topic chosen by the student and professor. Prerequisite: 6 graduate credits in computer science with grades of B+ or better.

16:198:607,608Problems in Numerical Methods (BA,BA) Formal lectures and individual projects under the guidance of the instructor. Topics follow the material covered in 16:198: 525,526, and/or 527. Final project may include the implementation and evaluation of computer programs. Gerasoulis, Vichnevetsky. Prerequisites: 16:198:525 or 526 or 527 or equivalent experience, and permission of instructor.

16:198:671,672,673,674,675,676Seminar in Computer Science (3,3,3,3,3,3) Current research. Several seminars are given each term. For advanced graduate students who have at least 18 graduate credits in computer science.

16:198:701,702Research in Computer Science (BA,BA) Prerequisite: Permission of thesis adviser. For students working on their master's theses or doctoral dissertations.