Graduate Course Descriptions

Note: Descriptions of courses in the Special Topics in Computer Science Series (G22.3033) are listed separately.

Preparatory Accelerated Course (PAC)

Applicants to the master.s programs who have insufficient background in computer science but are otherwise admissible are referred to PAC. These two courses (part one, which is offered in the fall, and part two, in the spring) are designed to fulfill the minimum prerequisites for beginning a master.s program in computer science or information systems. Those admitted to the M.S. program with the requirement to complete PAC are considered M.S. degree students while they are enrolled in PAC courses, although the credits for the courses do not count toward the M.S. degree. Applicants should apply for their ultimate degree objective rather than for PAC, even if they expect to be required to take these courses.

Intensive Introduction to Graduate Study in Computer Science I (PAC) G22.1133

Prerequisite: programming experience in any language. 4 points

An accelerated introduction to the fundamental concepts of computer science for students who lack a formal background in the field. Topics include algorithm design and program development; data types; control structures; subprograms and parameter passing; recursion; data structures; searching and sorting; dynamic storage allocation and pointers; abstract data types, such as stacks, queues, lists, and tree structures; generic packages; and an introduction to the principles of object-oriented programming. Concepts are implemented using the Ada programming language as a representative modern high-level imperative language, emphasizing packages as a means to develop skills in effective software design and development. Students should expect an average of 12-16 hours of programming and related course work per week.

Intensive Introduction to Graduate Study in Computer Science II (PAC II) G22.1144

Prerequisite: G22.1133 or departmental permission. 4 credits

Builds directly on the foundation developed in PAC I and extends this two ways: down, to the level of machine architecture, and up, to the higher levels of programming abstraction, using Java and object-oriented programming techniques. Topics include

1. Assembly language programming for the Intel chip family, emphasizing internal data representation, the logic of machine addressing, registers, the system stack, component development and techniques for communication among the components.

2. Programming in the C language, a relatively high-level systems programming language that also provides lowlevel capabilities similar to those of assembly language.

3. Programming in Java, which shares much of the syntax of C, removing pointer management and introducing object-oriented programming concepts.

4. An overview of common UNIX commands and shell-script programming.

Examples and assignments reinforce and refine those first seen in PAC I and often connect directly to topics in the core computer science graduate courses, such as Programming Languages, Compilers, Fundamental Algorithms, and Operating Systems.

Algorithms

Fundamental Algorithms G22.1170

Prerequisite: at least one year.s experience with a high-level language such as Pascal, C, C++, or Java; knowledge of assembly language; and familiarity with recursive programming methods and with data structures (arrays, pointers, stacks, queues, linked lists, binary trees). 3 points.

Reviews a number of important algorithms, with emphasis on correctness and efficiency: solving recurrence equations; sorting algorithms; selection; binary search; hashing; binary search trees and balanced-tree strategies; tree traversal; partitioning; graphs; spanning trees; shortest paths; connectivity; depth first search; breadth first search. Dynamic programming, divide and conquer.

Elements of Discrete Mathematics G22.2340

Identical to G63.2050. May not be taken by students who have received a grade of B or better in G22.1170. 3 points.

Introduction to the central mathematical concepts that arise in computer science. Emphasis is on proof and abstraction. Topics include proof techniques; combinatorics; sets, functions, and relations; discrete structures; order of magnitude analysis; formal logic; formal languages and automata.

Honors Analysis of Algorithms G22.3520

Prerequisites: G22.1170 or one semester of undergraduate algorithms, and permission of the instructor. 4 points.

Design of algorithms and data structures. Review of searching, sorting, and fundamental graph algorithms. In-depth analysis of algorithmic complexity, including advanced topics on recurrence equations and NP-complete problems. Advanced topics on lower bounds, randomized algorithms, amortized algorithms, and data structure design as applied to union-find, pattern matching, polynomial arithmetic, network flow, and matching.

Programming Languages

Programming Languages G22.2110

3 points.

Design and use of mainstream programming languages: naming, scoping, type models, control structures, procedural abstractions, modularization. Implementation issues and runtime organization. Languages studied include Ada, C, C++, Java, LISP, ML, and Python. Extensive programming exercises in various languages.

Compiler Construction G22.2130

Prerequisite: G22.1170. 3 points.

Structure of one-pass and multiplepass compilers, symbol table management, lexical analysis. Traditional and automated parsing techniques, including recursive descent and LR parsing. Syntax-directed translation and semantic analysis, run-time storage management, intermediate code generation. Introduction to optimization, code generation.

Honors Programming Languages G22.3110

Prerequisite: permission of the instructor. 4 points.

In-depth examination of the four major categories of programming languages: imperative, object-oriented, functional, and logic languages. The specific languages covered include Ada, C++, LISP, ML, Prolog, and SETL. Fundamental issues of programming languages, such as type systems, scoping, concurrency, modularization, control flow, and semantics, are discussed.

Honors Compilers and Computer languages G22.3130

Prerequisites: one semester of undergraduate compilers or G22.2130, and permission of the instructor. 4 points.

Lexical scanning and scanner generation from regular expressions; LL, LR, and universal parser generation from context-free grammars; syntaxdirected translation and attribute grammars; type and general semantic analysis; code generation, peephole optimization, and register allocation; and global program analysis and optimization. Provides experience using a variety of advanced language systems and experimental system prototypes.

Computer Systems

Computer Systems Design G22.2233

Pre- or corequisite: G22.1170. 3 points.

Gives students whose interest is in software an introduction to hardware and the logical design of digital computers. Topics include design of basic logic modules and arithmetic units; fixed and microprogrammable control structures; computer architecture; memory organization; and input-output organization.

High Performance Computer Architecture G22.2243

Prerequisite: a course in computer organization and knowledge of assembly language programming. 3 points.

Measures of architecture quality. Memory system techniques: cachememory design techniques, models of program behavior, cache and virtual memory structures. Pipeline computers, vector processors, and array processors. Multiprocessors, synchronization, cache coherence. Parallelization techniques, efficient parallel software.

Unix Tools G22.2245

3 points.

Brief history of the UNIX operating system: basic utilities (mail, editors); shells; windowing systems; shell programming using UNIX tools (awk, set, grep, tar); networking tools; news readers; etiquette and Internet databases and facilities; C programming tools; UNIX-based systems programming; desktop publishing tools; visuvisualization systems; symbolic algebra tools; and system administration.

Design of Operating Systems G22.2250

Prerequisite: G22.1170. 3 points.

Review of linkers and loaders. Highlevel design of key operating system concepts such as process scheduling and synchronization; deadlocks and their prevention; memory management, including (demand) paging and segmentation; and I/O and file systems, including examples from UNIX/Linux and Windows. Programming assignments, which may be written in C, C++, Java, or C#.

Data Communications and Network Design G22.2262

Prerequisite: G22.2250. 3 points.

Studies the software tools used by computers to converse with each other and with the real world. Communications systems and media (including people); bandwidth limitations; channel sharing and grouping; data formatting; error detection and correction; protocols; networks; I/O driver design; operating system interfaces; and human interfaces.

Database Systems G22.2433

Prerequisite: G22.1170. 3 points.

Database system architecture. Modeling an application and logical database design. The relational model and relational data definition and data manipulation languages. Design of relational databases and normalization theory. Physical database design. Concurrency and recovery. Query processing and optimization.

Advanced Database Systems G22.2434

Prerequisite: G22.2433. 3 points.

Studies the internals of database systems as an introduction to research and as a basis for rational performance tuning. Topics: concurrency control, fault tolerance, operating system interactions, query processing, and principles of tuning.

Software Engineering G22.2440

Prerequisites: G22.2110, G22.2130, and G22.2250. 3 points.

Presents modern software engineering techniques. Examines the software life cycle, including software specification, design, implementation, testing, and maintenance. Object-oriented design methods.

Networks and Distributed Systems G22.2620

Prerequisites: A course in undergraduate networks and/or operating systems; programming experience in C/C++ or Java is helpful for the final project. 3 points.

A course in computer networks and large-scale distributed systems. Teaches the design and implementation techniques essential for engineering both robust networks and Internet-scale distributed systems. The goal is to guide students so they can initiate and critique research ideas in networks and distributed systems and implement and evaluate a working system that can handle a real-world workload. Topics include routing protocols, network congestion control, wireless networking, peer-to-peer systems, overlay networks and applications, distributed storage systems, and network security.

Distributed Computing G22.2631

Prerequisites: G22.1170 and G22.2250. 3 points.

Concepts underlying distributed systems: synchronization, communication, fault tolerance, and performance. Examined from three points of view: (1) problems, appropriate assumptions, and algorithmic solutions; (2) linguistic constructs; and (3) some typical systems.

Honors Operating Systems G22.3250

Prerequisites: one undergraduate course in algorithms and one in C or C++ programming. 4 points.

Operating-system structure. Processes. Process synchronization. Language mechanisms for concurrency. Deadlocks: modeling, prevention, avoidance, and recovery. Memory management. Filesystem interface. Secondary storage. Distributed systems: layered system design, managing distributed processes, distributed shared memory, fault-tolerance. CPU scheduling. Queuing and performance: analysis of single M/M/1 queue and others. Protection and security. Advanced security concepts: threat monitoring, encryption, and public keys.

Computer Graphics

Computer Graphics G22.2270

Prerequisite: G22.1170. 3 points.

Problems and objectives of computer graphics. Vector, curve, and character generation. Interactive display devices. Construction of hierarchical image list. Graphic data structures and graphics languages. Hidden-line problems; windowing, shading, and perspective projection. Curved surface generation display.

User Interfaces G22.2280

Prerequisite: proficiency in C programming. 3 points.

Review of some of the basic principles and history of user interfaces. Building an interactive window system from the ground up, starting with a generic portable graphics base. Examination of future and emerging (nontraditional) user interfaces, including virtual reality and immersive environments.

Artificial Intelligence

Computer Vision G22.2271

Prerequisite: G22.1170. 3 points.

Basic techniques of computer vision and image processing. General algorithms for image understanding problems. Study of binary image processing, edge detection, feature extraction, motion estimation, color processing, stereo vision, and elementary object recognition. Mathematical, signal processing, and image processing tools. Relation of computer vision algorithms to the human visual system.

Artificial Intelligence G22.2560

Prerequisites: G22.1170 and G22.2110. 3 points.

There are many cognitive tasks that people do easily and almost unconsciously but that have proven extremely difficult to program on a computer. Artificial intelligence is the problem of developing computer systems that can carry out these tasks. This course covers problem solving and state space search; automated reasoning; probabilistic reasoning; planning; and knowledge representation.

Machine Learning G22.2565

Prerequisites: undergraduate course in linear algebra and strong programming skills for implementation of algorithms studied in class. Recommended: knowledge of vector calculus, elementary statistics, and probability theory. 3 points.

This course covers a wide variety of topics in machine learning, pattern recognition, statistical modeling, and neural computation. The course covers the mathematical methods and theoretical aspects but primarily focuses on algorithmic and practical issues.

Foundations of Machine Learning G22.2566

3 points.

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; and reinforcement learning, Markov decision processes (MDPs).

Web Search Engines G22.2580

3 points.

Discusses the design of general and specialized Web search engines and the extraction of information from the results of Web search engines Topics include Web crawlers, database design, query language, relevence ranking, document similarity and clustering, the “invisible” Web, specialized search engines, evaluation, natural language processing, data mining applied to the Web, and multimedia retrieval.

Natural Language Processing G22.2590

3 points.

Survey of the techniques used for processing natural language. Syntactic analysis: major syntactic structures of English; alternative formalisms for natural language grammar; parsing algorithms; analyzing coordinate conjunction; parsing with graded acceptability. Semantic analysis: meaning representations; analysis of quantificational structure; semantic constraints; anaphora resolution; analysis of sentence fragments. Analysis of discourse and dialog. Text generation. Students get some experience using a natural language parser and a natural language query interface. Brief weekly written assignments and a term project involving a mixture of library research and programming (mostly in LISP).

Advanced Topics in Natural Language Processing: Statistical and Corpus-based Methods G22.2591

3 points.

One of the roadblocks to improving the performance of natural language systems is the difficulty of acquiring large amounts of knowledge about the properties of language: which words can meaningfully combine in linguistic structures and how words are semantically related. The recent availability of very large machine-readable corpora has sparked increased interest in acquiring this information automatically from text, using a combination of symbolic and statistical analysis. This course reviews some of the recent work in this area, including the following topics: statistical models of language; entropy and perplexity; n-gram word models: acquisition and smoothing, part-of-speech models; finite state models: hidden Markov models, acquisition procedures; probabilistic context-free grammars: acquisition procedures; semantic models: word-concurrence, word classes; applications in information retrieval, speech recognition, and machine translation.

Heuristic Problem Solving G22.2965

3 points.

This course revolves around several problems new 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. The solution entails winning a contest against other solutions. The winner receives candy. The best solutions become part of an evolving “Omniheurist” Web site that is expected to get many visitors over the years. The course is for highly motivated, mathematically adept students. It is open to supported Ph.D. students and master’s students who have passed the core exam. Class size has been around 10 in the past, and instructor and students have all gotten to know one another very well. Algorithmic and programming knowledge are the main prerequisites. It also helps to be familiar with a rapid prototyping language such as MATLAB, Mathematica, K, or Python, or to be completely fluent in some other language.

Theoretical Computer Science

Logic in Computer Science G22.2390

3 points.

A beginning graduate-level class in mathematical logic with motivation provided by applications in computer science. There are no formal prerequisites, but the pace of the class requires that students can cope with a significant level of mathematical sophistication. Topics include propositional and first-order logic; soundness, completeness, and compactness of first-order logic; first-order theories; undecidability and Godel’s incompleteness theorem; and an introduction to other logics such as second-order and temporal logic.

Applied Cryptography and Network Security G22.3205

3 points.

The course first introduces the fundamental mathematical cryptographic algorithms focusing on those that are used in current systems. To the extent feasible, the mathematical properties of the cryptographic algorithms are justified, using elementary mathematical tools. Second, actual security mechanisms and protocols, mainly those employed for network traffic and relying on the previously introduced cryptographic algorithms are presented. The topics covered will include introduction to basic number theoretical properties, public/private and symmetric key systems, secure hash functions, digital signature standards, digital certificates, IP security, email security, web security, and stand-alone computer privacy and security tools.

Introduction to Cryptography G22.3210

3 points.

The primary focus of this course is on definitions and constructions of various cryptographic objects, such as pseudorandom generators, encryption schemes, digital signature schemes, message authentication codes, block ciphers, and others time permitting. The class tries 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 a good definition is established 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. Secondary topics, covered only briefly, are current cryptographic practice and the history of cryptography and cryptanalysis.

Advanced Cryptography G22.3220

Prerequisite: G22.3210. 3 points.

Basics of computational number theory for cryptography. Identification protocols. Digital signatures. Publickey encryption. Additional selected topics.

Honors Theory of Computation G22.3350

Prerequisites: one semester of undergraduate theory of computation or formal languages, and permission of the instructor. 4 points.

Formal languages: regular languages, regular expressions, finite-state machines, context-free languages, grammars, and pushdown machines. Computability: primitive recursive functions, partial recursive functions, recursive languages, recursively enumerable languages, and Turing machines. Computational complexity: space and time complexity, complexity classes (such as P, NP, PSPACE, L, and NL), and complete problems.

Numerical Analysis, Scientific Computing, and Mathematical Programming

Scientific Computing G22.2112

Prerequisites: multivariate calculus, linear algebra, and basic probability. C/C++ programming very helpful. 3 points.

A practical introduction to scientific computing covering theory and basic algorithms together with use of visualization tools and principles behind reliable, efficient, and accurate software. Students program in C/C++ or MATLAB. Specific topics include IEEE arithmetic, conditioning and error analysis, classical numerical analysis (finite difference and integration formulas, etc.), numerical linear algebra, optimization and nonlinear equations, ordinary differential equations, and basic Monte Carlo.

Numerical Methods I G22.2420

Identical to G63.2010. Prerequisites: undergraduate linear algebra and some experience with programming. 3 points.

Floating-point arithmetic; conditioning and stability; numerical linear algebra, including systems of linear equations, least squares, and eigenvalue problems; LU, Cholesky, QR, and SVD factorizations; conjugate gradient and Lanczos methods; Gauss quadrature. Current software packages. Computer programming assignments form an essential part of the course.

Numerical Methods II G22.2421

Prerequisite: G22.2420. 3 points.

Nonlinear equations (Newton’s method). Ordinary differential equations: initial value problem (Runge- Kutta and multistep methods, convergence and stability); two-point boundary value problem. Elliptic partial differential equations: finite difference and finite element methods, fast solvers, multigrid, iterative methods exploiting special structure. Brief introduction to time-dependent partial differential equations. Current software packages. Computer programming assignments form an essential part of the course.

Topics in Numerical Analysis G22.2945

May be identical to G63.2030, G63.2031, G63.2040, G63.2051, G63.2060. Prerequisites vary according to topic. 3 points.

Recent topics have included computational fluid dynamics, finite elements method, particle methods. Current course descriptions are available from the department’s Web site.

Seminars and Research

Information Technology Projects G22.3812

Prerequisite: permission of the instructor. 3 points.

This course teaches students some of the skills required to participate in and run IT projects that succeed in the real world. Students simultaneously learn skills in the classroom and apply the skills in a project while interning at a local .client.. Clients are mostly companies, but sometimes they are government agencies or nonprofit organizations. Students are given the opportunity to work on projects early in their development so that they can experience the full software project life cycle. Students work in teams of about four individuals. Each team undertakes one project that lasts the entire semester. The readings, classroom lectures, discussions, and activities teach skills that help implement projects of this size. The following are examples of some projects:

Software purchase evaluation: In this type of project, a client needs some software to solve a particular business problem. However, it makes more sense to address this problem by purchasing, rather than building, the software. In this case, the team begins by analyzing the business problem and gathering requirements. It then designs an architecture that would connect the new system with existing systems. In the project.s second half, the team evaluates commercial products that might meet the requirements.

Software development: A client needs some software to solve a business problem. The team quickly prosecutes the software development life cycle. including requirements gathering, architecture, design, development, and testing.to produce a prototype system that addresses the business problem. The deliverables are the prototype code and a report. The report documents advice and knowledge gained during the project that might be useful to the staff at the client who will build a production system based on the prototype. About three-quarters of the projects involve software development.

Advanced Laboratory G22.3813

Prerequisite: permission of the faculty project supervisor, completion of at least 12 points of study, and programming background. 1-3 points per term for master's students, 1-12 points per term for Ph.D. students.

Large-scale programming project or research in cooperation with a faculty member. Students should be prepared to spend at least eight hours per week on this course.

Master’s Thesis Research G22.3840

Prerequisite: approval of a faculty adviser. 3-6 points.

Ph.D. Research Seminar G22.3850

Sections: 001, Cryptography; 002, Systems; 003, Theory; 004, Formal Methods; 005, Algebraic and Topological Computing; and 006, Machine Learning. Prerequisite: permission of the instructor. 1 point.

Graduate seminars serve as loosely structured forums for exploring research topics from broad areas of computer science. They are designed to foster dialogue by bringing together faculty and students from a given area and to encourage the exchange of ideas. As such, they bridge the gap between more structured course offerings and informal research meetings.

Ph.D. Thesis Research G22.3860

Prerequisite: permission of the thesis adviser or director of graduate studies for the Ph.D. program. 1-12 points per term.

Special Topics in Computer Science G22.3033

Each semester, multiple special topics courses are offered, covering topics that may not be offered on a regular basis.

Courses and prerequisites vary; information is posted as it becomes available for each semester. Links to Special Topics course descriptions by semester follow.