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.
Approved Computer Science Concentration Program
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
CMSC 10500, 10600, 11700 (not recommended for
CMSC 11500, 11600, 11700, or
CMSC 12500, 12600, 11700
Programming Languages and Systems Sequence (two
Two courses chosen from CMSC 22100, 22200,
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
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)
Approved Course Sequences from Outside Computer
Students in the B.A. and B.S. programs may draw
on the following courses for the three courses that they are required
to take outside computer sciences. Other courses are acceptable
as approved by the departmental counselor.
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
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
For students in the B.S. program, approved linear
algebra courses include MATH 25000, 25500, and 25800. Three-course
minor programs must be approved by the departmental counselor. Students
are urged to consult early with the departmental counselor to discuss
Summary of Requirements
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.
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.
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.
Undergraduate and Graduate Courses
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.
College students may register for graduate courses with the consent of the departmental counselor. Not all 30000-level courses listed here will be offered each year, and other 30000-level courses may be offered that are not listed. Please contact the department Web site (http://www.cs.uchicago.edu) for further information.
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.