The computer science concentration program prepares students for either graduate work or employment in computer science by offering both the degree of Bachelor of Arts and the degree of Bachelor of Science. Students receiving the B.A. will have sufficient breadth and depth for either graduate study or immediate employment in computer science. Recipients of the B.S. will, in addition, have substantial depth and breadth in a field outside of computer science through the completion of an approved minor program.

A concentration in mathematics with a specialization in computer science continues to meet the needs of mathematics concentrators who also have a strong interest in computing. The description of that program may be found in the Mathematics section of this catalog.

Both the B.A. and B.S. in Computer Science require fulfillment of the College's general education requirements. Of these, the mathematical sciences requirement in general education must be satisfied by completing an approved two-quarter calculus sequence. The physical sciences requirement in general education must be satisfied by completing an approved two-quarter sequence in either chemistry or physics. Candidates for either the B.A. or B.S. in computer science take a third quarter of the chemistry or physics sequence, Computer Science 17400, and nine courses in computer science chosen from an approved program.

B.A. students also take three approved courses outside computer science, at least two of which must form a sequence. B.S. students add a course in linear algebra to the nine computer science courses required of B.A. concentrators. B.S. students take two additional approved courses outside of computer science that form a sequence, as well as a three-course minor in a related field outside of computer science.

Students taking a bachelor's degree in computer science should note that by judicious employment of courses from another field for extra-departmental requirements or for electives, a minor field can be developed that is often in itself a solid basis for graduate or professional work in that field. Some disciplines where this collateral minor benefit applies include biology, biophysics, chemistry, education, geophysical sciences, history, linguistics, mathematics, philosophy, political science, psychology, physics, sociology, statistics, and theoretical economics.

Placement. The Department of Computer Science does not offer credit or placement for Advanced Placement tests in computer science.

Computer science students may use AP credit for chemistry or physics to fulfill their physical sciences requirement in general education or the physical sciences component of the concentration. However, no credit designated simply as "physical science" (from either AP or the College's physical sciences examinations) may be used to satisfy general education or concentration requirements.

Approved Programs. The notion of "approval" in the concentration program requirements allows timely response to change in the course offerings of the various departments. The computer science faculty is responsible for approval of specific courses and sequences. An initial list of approved course sequences follows, but additional courses may be approved. Consult the departmental counselor for details on specific courses you are considering taking to fulfill the requirements.

For the authoritative version of the Department of Computer Science requirements and course descriptions, consult the departmental Web site (http://www.cs.uchicago.edu).

There is a single approved program comprising required courses in four topical areas plus the minor. This is a general program in computer science and is used for either the B.A. or the B.S. degree. Upper-level or graduate courses in similar topics may be substituted for those on the list that follows, with the approval of the departmental counselor.

Introductory Programming Sequence (three courses required):

CMSC 10500, 10600, 11700 (not recommended for concentrators), or

CMSC 11500, 11600, 11700, or

CMSC 12500, 12600, 11700

Programming Languages and Systems Sequence (two courses required):

Two courses chosen from CMSC 22100, 22200, 22600, 23000

Algorithms and Theory Sequence (two courses required):

CMSC 27000 and 28000, or

CMSC 27000 and 28100

Other Sequences (one sequence required):

Artificial Intelligence Sequence (two courses required):
CMSC 25000-25100

Advanced Systems Sequence (two courses required):

CMSC 22100, or 22200, or 22600, or 23000, or 23300, depending upon what courses the student has taken in the Programming Languages and Systems Sequence (courses may NOT be used to fulfill both requirements)

Numerical Analysis Sequence (two courses required):

CMSC 28500 and a third quarter of calculus or another course in solving differential equations (ODE/PDE)

ASTR 21300-24200

BIOS 19600-19700, 20300, 21000, 21100, 21200, 21300, 21400, 21500, 21600, 21700, 21800, 22000, 22100, 22200, 22600, 22800, 22900, 23000, 23100, 23600, 24700, 25600, 25800, 25900

CHEM 11100, 11200, 12100, 12200, if chemistry is not used to satisfy the physical sciences requirement

CHEM 20100, 20200, 22000, 22100

ECON 20000, 20100, 20200, 20300, 21000, 21100, 22500, 23100, 25000, 27000, 27100, 28100

GEOS 23100-23400, 23500-23600, 23900

LING 20100-21000, 21700

MATH 20300-21100, 25400-27800

MUSI 26300-26400

PHIL 23500-28500

PHYS 12100-12200, 13100-13200, 14100-14200, if physics is not used to satisfy the physical sciences requirement

PHYS 22500-22700, 23400-23500, 23600-23700

STAT 22000-25100

or PHYS 12100-12200 or higher†

MATH 13100-13200 or higher†

Concentration

1 CHEM 11300 or higher†

or PHYS 12300 or higher†

1 CMSC 17400 or higher*

9 courses in computer science from the

approved program

† Credit may be granted by examination.

* Credit for CMSC 17400 may be granted by an

Grading. Subject to College and divisional regulations and with the consent of the instructor, all students, except concentrators in computer science, may register for regular letter grades, P/N grades, or P/F grades in any course in computer science. A Pass grade is given only for work of C- quality or higher.

Concentrators in computer science may take any 20000-level computer science course elected beyond concentration requirements for a grade of P. A grade of C- or better must be earned in each course used to fulfill concentration program requirements. Courses taken to fulfill concentration requirements in computer science must be taken for a quality grade; P/N or P/F grades are not permitted.

Incompletes are typically given in the Department of Computer Science only to those students who have done at least 60 percent of the course's work of a passing quality and who are unable to complete all course work by the end of the quarter. Other restrictions on Incompletes are the province of individual instructors, many of whom do not permit Incompletes. Students must make arrangements in advance with instructors and obtain their written consent to receive Incompletes.

Honors. Students may earn a B.A. or B.S. degree with honors by attaining a grade of B or better in all courses in the concentration and by attaining a grade of B or better in a three-course sequence (taken as a minor or as electives) consisting of graduate computer science courses (30000-level and above).

Students may also earn a B.A. or B.S. degree with honors by attaining the same minimum B grade in all courses in the concentration and by writing a successful bachelor's thesis as part of Computer Science 29900. This thesis must be based on an approved research project that is directed by a faculty member and approved by the departmental counselor.

Courses in Specific Areas of Computer Science. Students interested in artificial intelligence (AI) should take Computer Science 25000 and 25100 (Introduction to Artificial Intelligence), in addition to Computer Science 11500-11600-11700. Graduate-level AI courses are open to College students. These courses are numbered Computer Science 35000 to 35400. Consult the course listings for details.

Students interested in advanced programming (i.e., systems) should take Computer Science 22100 (Programming Languages), and Computer Science 22200 (Computer Organization). Time permitting, they should also take Computer Science 22600 (Compilers), Computer Science 23000 (Operating Systems), Computer Science 23300 (Networks and Distributed Systems), and such courses in advanced programming topics that may be offered.

Students interested in theoretical computer science should complete basic courses in algebra and then take Computer Science 27400 (Combinatorics and Probability), Computer Science 28000 (Introduction to Formal Languages), and Computer Science 28100 (Introduction to Complexity Theory). Once students have completed Computer Science 27000 and 28000 or 28100, they will be qualified for most of the advanced topics courses offered at the 30000-level and above.

Students interested in numerical and scientific computing should take Computer Science 28500.

The department also offers a number of special-interest courses that are detailed in the course descriptions. New courses are added to the schedule on a regular basis. Consult the departmental counselor and the Computer Science Web site (http://www.cs.uchicago.edu).

Preparation for Graduate Study in Computer Science. Students interested in continuing their studies beyond the undergraduate level should concentrate in computer science and take as many computer science courses as possible. The most important courses are Computer Science 11500-11600-11700, 22100, 22200, 22600, 23000, 23300, 27000, 28000, and 28100. For more information about options for graduate study, students should consult the departmental counselor and the director of graduate studies.

Yali amit, Professor, Departments of Statistics and Computer Science, and the College

Laszlo Babai, Professor, Departments of Computer Science and Mathematics, and the College

DAVID BEAZLEY, Assistant Professor, Department of Computer Science and the College

Todd Dupont, Professor, Departments of Computer Science and Mathematics, James Franck Institute, and the College

FRANCOIS FLEURET, Instructor, Department of Computer Science and the College

IAN FOSTER, Professor, Department of Computer Science and the College; Senior Scientist, Argonne National Laboratory

LEO IRAKLIOTIS, Senior Lecturer and Director of the Computer Science Professional Program, Department of Computer Science; Associate Chairman, Department of Computer Science

ROBERT C. KIRBY, L. E. Dickson Instructor, Departments of Computer Science and Mathematics, and the College

Stuart A. Kurtz, Professor, Department of Computer Science and the College; Chairman, Department of Computer Science

Ketan Mulmuley, Professor, Department of Computer Science and the College

SVETLOZAR NESTOROV, Assistant Professor, Department of Computer Science and the College

PARTHA NIYOGI, Assistant Professor, Departments of Computer Science and Statistics, and the College

Michael J. O'Donnell, Professor, Department of Computer Science and the College

SHARON SALVETER, Senior Lecturer, Department of Computer Science and the College

L. Ridgway Scott, Louis Block Professor, Departments of Computer Science and Mathematics, and the College

Janos Simon, Professor, Department of Computer Science and the College

Robert I. Soare, Paul Snowden Russell Distinguished Service Professor, Departments of Computer Science and Mathematics, and the College

RICK STEVENS, Professor, Department of Computer Science and the College

STEPHEN WRIGHT, Professor, Department of Computer Science and the College

L refers to courses with a laboratory.

10000. Web Design: Aesthetics and Languages (=CMSC 10000, GSHU 29600, HUMA 25100). As a complement to courses in criticism, aesthetics, cultural studies, or Web programming, this course explores Web design as a liberal art of technology. Good multimedia design is based on our sensory intelligences. Yet, on the Web it requires syntheses of natural languages and artificial languages; of grammar, rhetoric, and logic; and, of course, mastery of the subject matter being presented. For the culture of "real virtuality," what design principles effectively and attractively communicate information, narratives, and explanations? We examine and create design environments in print and electronic media, with a focus on the Internet. M. Browning. Winter.

10100. Introduction to Programming for the World Wide Web (HTML, CGI, and Java) I. This course teaches the basics of building and maintaining a site on the World Wide Web. We discuss Internet terminology and how the Internet and its associated technologies work. Topics include computer programming, programming Web sites, hypertext markup language (HTML), Cascading Style Sheets (CSS), and Common Gateway Interface (CGI) scripts (using PERL). Students also learn how to use JavaScript to add client-side functionality. S. Salveter, Staff. Summer, Winter.

10200. Introduction to Programming for the World Wide Web (HTML, CGI, and Java) II. PQ: Knowledge of HTML. CMSC 10200 can be used to fulfill the mathematical sciences requirement in general education. Topics include dynamic hypertext markup languages (dHTML), Common Gateway Interface (CGI) scripts (using PERL), and Java. Students learn how to set up a Web server, write Java applets, and use communication components such as ActiveX and Javabeans. Staff. Summer, Spring.

10500-10600-10700. Fundamentals of Computer Programming (Scheme, C++) I, II, III. PQ: MATH 10600, or placement into 13100 or equivalent; or consent of departmental counselor. CMSC 10500-10600 can be used to fulfill the mathematical sciences requirement in general education. This sequence is an introduction to computer programming using the Scheme and C++ programming languages, which emphasize structure, algorithm construction, and design. Topics include variables, complex types, iteration, recursion, and procedural/functional/data abstraction, basic algorithms and data structures. Both the CMSC 10500-10600-10700 sequence and the CMSC 11500-11600-11700 sequence are general introductions to computer programming. CMSC 10500-10600-10700 assumes no previous programming experience and less advanced mathematical knowledge. This course is usually taught on a Macintosh microcomputer. Staff. Autumn, Winter, Spring.

11000-11100. Multimedia Programming as an Interdisciplinary Art I, II (=CMSC 11000-11100, GSHU 23500-23600). PQ: MATH 10600, or placement into MATH 13100, or equivalent; or consent of instructor. CMSC 11000 or 11100 meets the mathematical sciences requirement in general education. This sequence provides students with both practical programming skills and core ideas in computer science in relation to interdisciplinary applications. Across all disciplines, our ideas of the arts, the character of "images" and "texts," and the ways we form communities are being transformed by the World Wide Web (e.g., by scripting languages and the QuickTime Media Layer). Students learn to program on an Apple Macintosh using HyperCard, QuickTime, and a variety of user scripting languages (e.g., Lingo, JavaScript, HyperTalk, and AppleScript). The course presents techniques of problem solving, program coding, algorithm construction, and debugging using the Web as its programming environment. W. Sterner, Staff. Winter, Spring.

11200. Introduction to Interactive Logic (=CMSC 11200, GSHU 23700). PQ: MATH 10600, or placement into 13100, or equivalent. Some experience with computers helpful. This hands-on course presents logic as a concrete discipline that is used for understanding and creating human-computer technology in the context of science, technology, and society. We look at computer science, logic, philosophy, aesthetics, design, and the study of technology, as well as at the software packages of Tarski's World and possibly HyperProof. No programming skills are assumed, but those with some programming background do projects with HyperCard, a Computer Assisted Design package, Prolog, or other software. The course continues in the same spirit as CMSC 11000-11100, but they are not prerequisites. W. Sterner. Spring. Not offered 2001-02; will be offered 2002-03.

11500-11600-11700. Introduction to Computer Programming I, II, III (Scheme, C++). PQ: Placement into MATH 15100 or equivalent, or consent of departmental counselor. Students may take CMSC 10500, then 11600-11700, although this is NOT recommended. Any course in the CMSC 11500-11600-11700 sequence can be used to fulfill the mathematical sciences requirement in general education. An introduction to computer programming using the Scheme and C++ programming languages. Students learn functional and object-oriented programming. Topics include control and data abstraction, self-reference, time and space analysis, and basic algorithms and data structures. The CMSC 11500-11600-11700 sequence is recommended for concentrators, as well as for all students planning to take more advanced courses in computer science. Staff. Summer, Autumn, Winter, Spring.

12500-12600. Honors Introduction to Computer Programming I, II. PQ: Placement into MATH 16100 or equivalent, or consent of departmental counselor. CMSC 12500 and CMSC 12600 can be used to fulfill the mathematical sciences requirement in general education. The first quarter of honors introduction to computing is based on the famous Scheme book by Abelson and Sussman. It covers material more deeply and quickly than 11500. There is more emphasis on computational structure and less time spent on basic programming. Students in this course have such strong mathematical skills that they learn programming in Scheme very quickly. Although we spend little time explaining or exercising basic programming techniques, students in this class write more code and complete more complex systems than is the rule in CMSC 11500. However, no previous programming experience is required. In CMSC 12600 students continue developing their programming and analytical skills. Students who have completed CMSC 11500 may take CMSC 12600 with consent of instructor. Staff. Autumn, Winter.

17400. Discrete Mathematics. PQ: Placement into MATH 15100 or equivalent, or consent of departmental counselor. This is a directed course in mathematical topics and techniques needed by students taking Algorithms (CMSC 27000). It is also a prerequisite to several other courses, including Honors Combinatorics and Probability (CMSC 27400/MATH 28400). This course emphasizes mathematical discovery and rigorous proof, which are illustrated on a refreshing variety of accessible and useful topics. Basic counting is a recurring theme and provides the most important source for sequences, which is another recurring theme. Further topics include proof by induction; recurrences and Fibonacci numbers; graph theory and trees; number theory, congruences, and Fermat's little theorem; counting, factorials, and binomial coefficients; combinatorial probability; random variables, expected value, and variance; and limits of sequences, asymtotic equality, and rates of growth. L. Babai. Autumn.

Other 20000-level courses may be offered. Please consult the departmental Web site (http://www.cs.uchicago.edu) and the quarterly Time Schedules for the most up-to-date information.

21000. Introduction to Parallel Programming. PQ: Functional knowledge of C or FORTRAN. This course provides science students with the tools needed to solve large-scale computational problems on parallel computers and Beowulf-style clusters of workstations. We begin with a review of parallel machine architectures, programming paradigms, and performance modeling, analysis, and tuning. We then address how to design algorithms for distributed-memory machines using the message-passing programming paradigm and how to efficiently implement them in C or FORTRAN using MPI (the Message Passing Interface standard). Applications commonly used in the scientific computing community are used as case studies. Staff. Autumn.

21500. Logic and Logic Programming (=CMSC 21500, MATH 27900). PQ: MATH 25400, or CMSC 27700, or consent of instructor. Programming knowledge not required. Predicate logic is a precise logical system developed to formally express mathematical reasoning. Prolog is a computer language intended to implement a portion of predicate logic. This course covers both predicate logic and Prolog, which are presented to complement each other and to illustrate the principles of logic programming and automated theorem proving. Topics include syntax and semantics of propositional and predicate logic, tableaux proofs, resolution, Skolemization, Herbrand's theorem, unification, and refining resolution. It includes weekly classes and programming assignments in Prolog (e.g., searching, backtracking, and cut). This course overlaps only slightly with CMSC 27700; students are encouraged to take both courses. This course is offered in alternate years. R. Soare. Winter.

22100. Programming Languages. PQ: CMSC 10600 or 11600, or consent of instructor. Programming language design aims at the closest possible correspondence between the structures of a program and the task it performs. This course studies some of the structural concepts affecting programming languages: iterative and recursive control flow, data types and type checking, procedural versus functional programming, modularity and encapsulation, fundamentals of interpreting and compiling, and formal descriptions of syntax and semantics. Students write short programs in radically different languages to illuminate the variety of possible designs. M. O'Donnell. Autumn.

22200. Computer Architecture. PQ: CMSC 10600 or 11600. Survey of contemporary computer organization covering: early systems, CPU design, instruction sets, control, processors, busses, ALU, memory, pipelined computers, multiprocessors, networking, and case studies. The course focuses on the techniques of quantitative analysis and evaluation of modern computing systems, such as the selection of appropriate benchmarks to reveal and compare the performance of alternative design choices in system design. The emphasis is on the major component subsystems of high performance computers: pipelining, instruction level parallelism, memory hierarchies, input/output, and network-oriented interconnections. If time permits, we also cover emerging topics such as portable computers, high-performance parallel computers, graphics computers, and techniques for performance modeling and simulation. R. Stevens. Autumn.

22600/32600. Compilers for Computer Languages. PQ: CMSC 22200 or consent of instructor. The translation of high-level directives into machine-executable instructions is a spectacular success of applied computer science. This course teaches formal and systematic techniques for syntax-directed translation. Topics include lexical analysis, parsing, abstract syntax, and elements of code generation. A programming language compiler is built. Staff. Spring.

23000/33000. Operating Systems. PQ: CMSC 11700 and 22200, or consent of instructor. This course covers basic concepts of operating systems. Topics discussed include the notion of a process, interprocess communication and synchronization, main memory allocation, segmentation, paging, linking and loading, scheduling, file systems, and security and privacy. This course is taught on Sun workstations using UNIX. D. Beazley. Winter.

23300/33300. Networks and Distributed Systems. PQ: CMSC 23000 or consent of instructor. Basic knowledge of C, C++, and Java, as well as operating system concepts such as processes and threads. This course focuses on the principles and techniques used in the development of networked and distributed software. Topics include programming with sockets, remote procedure calls (RPC), interprocess communication (IPC), distributed objects (CORBA and DCOM), and commonly used network protocols including TCP/IP, UDP, FTP, and HTTP. In addition, data encoding, encryption, and compression algorithms are presented. This is a project-oriented course in which students are required to develop software in the UNIX programming environment. D. Beazley. Spring.

24000. Information Theory and Coding. PQ: Consent of instructor. This course introduces students to the mathematical theory of information with emphasis on coding, especially the development of efficient codes. Topics include an introduction to coding, quantification of information and its properties, Huffman codes, arithmetic codes, L to Z and other adaptive coding techniques, and specific applications. A. Bookstein. Winter.

25000-25100. Introduction to Artificial Intelligence and LISP I, II. PQ: CMSC 10500-10600 or 11500-11600. An introduction to the theoretical, technical, and philosophical issues of AI. This course looks at natural language processing, planning, problem solving, diagnostic systems, naïve physics, and game playing. LISP and LISP programming are introduced. P. Niyogi. Winter, Spring.

27000. Theory of Algorithms. PQ: CMSC 17400 or consent of instructor. Design and analysis of efficient algorithms, with emphasis on ideas rather than on implementation. Algorithmic questions include sorting and searching, discrete optimization, algorithmic graph theory, algorithmic number theory, and cryptography. Design techniques include "divide-and-conquer" methods, dynamic programming, greedy algorithms, and graph search, as well as the design of efficient data structures. Methods of algorithm analysis include asymptotic notation, evaluation of recurrent inequalities, the concepts of polynomial-time algorithms, and NP-completeness. L. Babai. Winter.

27400. Honors Combinatorics and Probability (=CMSC 27400, MATH 28400). PQ: MATH 25000 or 25400, or CMSC 17400, or consent of instructor. Experience with mathematical proofs. Methods of enumeration, construction, and proof of existence of discrete structures are discussed in conjunction with the basic concepts of probability theory over a finite sample space. Enumeration techniques are applied to the calculation of probabilities, and, conversely, probabilistic arguments are used in the analysis of combinatorial structures. Topics include basic counting, linear recurrences, generating functions, extremal set systems, Latin squares, finite projective planes, graph theory, Ramsey theory, coloring graphs and set systems, random variables, independence, expected value, standard deviation, Chebyshev's and Chernoff's inequalities, the structure of random graphs and tournaments, probabalistic proofs of existence, and linear algebra methods to prove inequalities in combinatorics and geometry. L. Babai. Spring.

27700. Mathematical Logic I (=CMSC 27700, MATH 27700). PQ: MATH 25400. This course provides an introduction to mathematical logic. Topics include propositional and predicate logic and the syntactic notion of proof versus the semantic notion of truth, including soundness and completeness. We also discuss the Goedel completeness theorem, the compactness theorem, and applications of compactness to algebraic problems. Staff. Autumn.

27800. Mathematical Logic II (=CMSC 27800, MATH 27800). PQ: MATH 27700 or equivalent. Some of the topics examined are number theory, Peano arithmatic, Turing compatibility, unsolvable problems, Godel's incompletness theorem, undecidable theories (i.e., the theory of groups), quantifier elimination, and decidable theories (i.e., the theory of algebraically closed fields). Staff. Winter.

27900. Chaos, Complexity, and Computers (=CMSC 27900, MATH 29200, PHYS 25100). PQ: One year of calculus and two quarters of physics at any level. Knowledge of computer programming not required. In this course we use the computer to investigate the question of how patterns and complexity arise in nature. The systems studied are drawn from physics, biology, and other areas of science. This course also is intended to be an introduction to the use of computers in the physical sciences. T. Witten. Winter.

28000. Introduction to Formal Languages (=CMSC 28000, MATH 28000). PQ: MATH 25000 or 25500 or CMSC 17400, and experience with mathematical proofs. Topics include automata theory, regular languages, CFLs, and Turing machines. This course is a basic introduction to computability theory and formal languages. This course is offered in alternate years. Staff. Autumn.

28100. Introduction to Complexity Theory (=CMSC 28100, MATH 28100). PQ: MATH 25000 or 25500 or CMSC 17400, and experience with mathematical proofs. Computability topics are discussed, including the s-m-n theorem and the recursion theorem. We also discuss resource-bounded computation. This course introduces complexity theory. Relationships between space and time, determinism and nondeterminism, NP-completeness, and the P versus NP question are investigated. This course is offered in alternate years. J. Simon. Autumn.

28500. Introduction to Numerical Computation. PQ: MATH 20500 and 25000, and CMSC 10500 or 11500; or consent of instructor. Advanced knowledge of FORTRAN, C, or Pascal; and basic knowledge of multivariable calculus and linear algebra. Basic processes of numerical computation are examined from both an experimental and theoretical point of view. The course deals with numerical linear algebra, approximation of functions, approximate integration and differentiation, Fourier transformation, solution of nonlinear equations, and the approximate solution of initial value problems for ordinary differential equations. The course concentrates on the most widely used methods in each area covered. T. Dupont. Spring.

29500. Digital Sound Modeling. PQ: Knowledge of computer programming or consent of instructor. This course studies how the basic structure of sound perception affects the useful ways of representing sound in digital computations. We focus on basic synthesis techniques, rather than on signal analysis or on special applications of synthesis, such as music or speech. Course work is divided among intuitive mathematical studies, listening exercises, and a cooperative project using synthesis software. M. O'Donnell. Spring.

29700. Reading and Research in Computer Science. PQ: Consent of instructor and approval of departmental counselor. Open to both concentrators and nonconcentrators; students are required to submit the College Reading and Research Course Form. Reading and research in an area of computer science under the guidance of a faculty member. A written report is typically required. Staff. Summer, Autumn, Winter, Spring.

29900. Bachelor's Thesis. PQ: Open to fourth-year students who are candidates for honors in computer science. Consent of instructor and departmental counselor. Students are required to submit the College Reading and Research Course Form. Staff. Summer, Autumn, Winter, Spring.

31000. Foundations of Computer Science. PQ: Consent of instructor. This class is an upper-level survey of computability and complexity theory. S. Kurtz. Autumn.

32900-33900. High-Performance Computing on the Internet I, II. PQ: Consent of instructor. This course teaches students how to create high-performance computations that span computers connected by local and wide-area networks. Examples of such computations are "smart instruments" that use remote computers to enhance instrument data, "networked parallel computers" that link distributed resources to solve hard computational problems, and "networked virtual spaces" that link distributed computers and graphics resources. High-performance Internet computing introduces demanding performance requirements in addition to the usual concerns that arise in distributed systems. I. Foster. Winter, Spring.

33100. Advanced Operating Systems. PQ: CMSC 23000/33000 and consent of instructor. This course covers advanced topics in operating systems and systems research. Possible topics include, but are not limited to, parallel computing and multiprocessing, threads, message passing, networking, distributed systems, linkers, loaders, dynamic loading, debuggers, garbage collection, software components, file systems, and security. D. Beazley. Autumn.

34000. Scientific Parallel Computing. PQ: Experience in scientific computing helpful. Consent of instructor. The use of multiple processors cooperating to solve a common task. We study issues related to this general problem in the areas of computer architecture, performance analysis, prediction and measurement, programming languages, and algorithms for large-scale computation. The course involves programming at least one parallel computer. Possibilities include one of the clusters of workstations connected by high-speed networks currently at the University of Chicago. We focus on the state of the art in parallel algorithms for scientific computing. Specific topics are chosen based on student interest. General principles of parallel computing are emphasized. L. R. Scott. Winter.

34700. Scalable Internet Services. PQ: Consent of instructor. The demands and opportunities of the World Wide Web present challenges for operating and distributed systems research in wide-area, Internet-scale systems. This class surveys current research in this area, including work in wide-area caching, prefetching, replication, naming, distributed computation, scalable servers, security, and communication protocols. A primary goal is to provide the background necessary for doing research on these topics. We read and evaluate research papers selected from the literature. In addition to lectures, students are asked to evaluate the papers as a basis for discussion. Students enrolled for full credit also do a class project in small groups. I. Foster. Autumn.

35000. Introduction to Artificial Intelligence. PQ: CMSC 25000. This course is an introduction to the theoretical, technical, and philosophical aspects of Artificial Intelligence. The emphasis is on computational and mathematical modes of inquiry into the structure and function of intelligent systems. Topics include learning and inference, speech and language, vision and robotics, and reasoning and search. P. Niyogi. Winter.

35400. Machine Learning. PQ: CMSC 35000/25000 or consent of instructor. An introduction to the theory and practice of machine learning. The course emphasizes statistical approaches to the problem. Topics covered include pattern recognition, empirical risk minimization and the Vapnik Chervonenkis theory, neural networks, decision trees, genetic algorithms, unsupervised learning, and multiple classifiers. P. Niyogi. Spring.

37000. Algorithms. PQ: CMSC 27000 or consent of instructor. Analysis and design of efficient algorithms, with emphasis on ideas rather than on implementation. Algorithmic questions include sorting and searching, discrete optimization, algorithmic graph theory, algorithmic number theory, and cryptography. Design techniques include "divide-and-conquer" methods, dynamic programming, greedy algorithms, and graph search, as well as the design of efficient data structures. Methods of algorithm analysis include asymptotic notation, evaluation of recurrent inequalities, the concepts of polynomial-time algorithms, and NP-completeness. L. Babai. Winter.

37100. Topics in Algorithms. PQ: CMSC 27000 or consent of instructor. For many optimization problems, it is impossible (or NP-hard) to design an algorithm that finds an optimal solution fast. It is interesting and important to study approximation algorithms that work faster, at the cost that we find only a good solution, not necessarily an optimal one. Sometimes we are also restricted in our access to the input, namely we have to react to partial input (typically first few requests of a request sequence) without knowledge of the complete input; thus we are building a solution step by step. Such algorithms are called on-line. The subject of the course is a theoretical study of these two classes of algorithms, illustrated on a number of optimization and combinatorial problems. The course includes recent results and thus provides an introduction to current research problems. J. Sgall. Autumn.

37200. Combinatorics. PQ: CMSC 27500 and background in linear algebra. Various aspects of families of finite sets are considered. The course emphasizes applications of linear algebra and the probabilistic method to combinatorics. Such techniques are frequently used in the theory of computing. This course is offered in alternate years. L. Babai. Spring.

37300. Parallel Algorithms. PQ: CMSC 27000 or consent of instructor. This course discusses models of parallel computation: shared memory and networks. Topics include basic algorithmic techniques (e.g., parallel prefix computation, list ranking, tree-contraction routing problems, complexity classes, and completeness results) and randomized parallel algorithms. This course is offered in alternate years. J. Simon. Winter.

37400. Constructive Combinatorics. PQ: Advanced knowledge of mathematics and consent of instructor. This course covers constructive combinatorial techniques in areas such as enumerative combinatorics, invariant theory, and representation theory of symmetric groups. Constructive techniques refer to techniques that have algorithmic flavor, as against purely existential techniques based on counting. K. Mulmuley. Spring.

38000-38100. Computability Theory I, II (=CMSC 38000-38100, MATH 30200-30300). PQ: MATH 25500 or consent of instructor. CMSC 38000 concerns recursive (e.g., computable) functions and sets generated by an algorithm (recursively enumerable sets). Topics include various mathematical models for computations, including Turing machines and Kleene schemata, enumeration and s-m-n theorems, the recursion theorem, classification of unsolvable problems, and priority methods for the construction of recursively enumerable sets and degrees. CMSC 38100 treats classification of sets by the degree of information they encode, algebraic structure and degrees of recursively enumerable sets, advanced priority methods, and generalized recursion theory. R. Soare. Winter, Spring.

38200. Distributed Algorithms. PQ: CMSC 27000 or consent of instructor. This course studies algorithmic problems in distributed systems. Topics include models of distributed systems, problems of contention and cooperation among processes, distributed consensus and agreement, and leader election and clock synchronization. Also discussed are static and dynamic algorithms, fault tolerance, and uses of randomization. J. Simon. Spring.

38500. Computability and Complexity Theory (=CMSC 38500, MATH 30500). PQ: Consent of instructor. Part one consists of models for defining computable functions, such as primitive recursive functions, (general) recursive functions, and Turing machines; and their equivalence, the Church-Turing Thesis, unsolvable problems, diagonalization, and properties of computably enumerable (c.e.) sets. Part two deals with Kolmogorov complexity (resource bounded complexity) that studies the quantity of information in individual objects and uses the book by Li and Vitanyi. The third part covers functions computable with special bounds on time and space of the Turing machine, such as polynomial time computability, the classes P and NP, nondeterministic Turing machines, NP-complete problems, polynomial time hierarchy, and P-space complete problems. Staff. Autumn. Not offered 2001-02; will be offered 2002-03.

38600. Complexity Theory A. PQ: Consent of instructor. Topics in computational complexity theory with an emphasis on machine-based complexity classes. This course is offered in alternate years. Staff. Spring.

38700. Complexity Theory B. PQ: Consent of instructor. Topics in computational complexity theory with an emphasis on combinatorial problems in complexity. This course is offered in alternate years. Staff. Winter.

39000. Computational Geometry. PQ: Consent of instructor. A seminar on topics in computational geometry. K. Mulmuley. Winter.

39200. Realizability Semantics (Computation and Communication in Constructive Logic). PQ: Mathematical maturity. Classical logic is founded on the premise that every proposition is either true or false, and its logical relations to other propositions depend only on that binary truth value. Constructive logic characterizes a strange theory subtly different from intuitionist doctrine. Lauchli's realizabity theory formalizes constructions as functions invariant under certain permutations, and characterizes precisely the Heyting calculus for constructive reasoning. We refine Lauchli's theory to show that his permutation invariance corresponds to reliable communicability in spite of certain misunderstandings in a language. M. O'Donnell. Winter.

39600. Topics in Theoretical Computer Science. PQ: Consent of instructor. A seminar on current research topics in computing theory. Staff. Autumn, Winter, Spring.