Computer Science

Departmental Counselor: Donald E. Crabb, Ry 161B, 702-7173, doncrabb@cs.uchicago.edu
Associate Director of Graduate and Undergraduate Studies: Donald E. Crabb, Ry 161B, 702-7173, doncrabb@cs.uchicago.edu
Student Services Representative: Margaret Jaffey, Ry 161A, 702-6011, margaret@cs.uchicago.edu

World Wide Web: http://www.cs.uchicago.edu/

Program of Study

This computer science concentration program is intended to prepare 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 acquired 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 majors 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 the B.A. and B.S. in computer science take a third quarter of calculus and a third quarter of the chemistry or physics sequence, as well as nine courses in computer science taken from an approved program. B.A. students also take three courses outside computer science, at least two of which must form an approved 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 courses outside of computer science that form an approved 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 extradepartmental 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 possible 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 most up-to-date information on the Department of Computer Science and the concentration in computer science, consult the departmental Web site (http://www.cs.uchicago.edu).

At present, there is a single approved program that is comprised of required courses in five 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 (two courses required):

ComSci 105 and 106, or
ComSci 105 and 116, or
ComSci 115-116 (strongly recommended)

Advanced Programming Sequence (one course required):

ComSci 117, or
ComSci 217, or
ComSci 219, or
any other advanced programming courses as may be offered

Programming Languages and Systems Sequence (two courses required):

ComSci 221-222, or
ComSci 221 and 230, or
ComSci 222 and 230, or
ComSci 222 and 231

Algorithms and Theory Sequence (two courses required):

ComSci 270 and 280, or
ComSci 270 and 281
Other Sequences (one sequence required):

Artificial Intelligence Sequence (two courses required):

ComSci 250-251

Advanced Systems Sequence (two courses required):

ComSci 219 and either ComSci 221, or 222, or 230, or 231, or 233, 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):

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

Astron 213, 214

BioSci 196-197, 203, 210, 211, 212, 213, 214, 215, 216, 217, 218, 221, 222, 228, 229, 230, 231, 236, 247, 256, 258, 259

Chem 111, 112, 121, 122, if chemistry is not used to satisfy the physical sciences requirement

Chem 201, 202, 220, 221

Econ 200, 201, 202, 203, 210, 211, 225, 231, 250, 271, 281

GeoSci 231-232, 235

Hist 249

Math 203, 204, 205, 207, 208, 209, 254, 255, 256, 257, 258, 259, 261, 262, 263, 270, 272, 273, 274, 275, 277, 278

Philos 235-285

Phys 121-122, 131-132, 141-142, if physics is not used to satisfy the physical sciences requirement

Phys 225-227, 234-235, 236-237

Stat 220, 222, 224, 226, 227, 240, 241, 242, 244, 245, 251

Concentration

1	Chem 113 or higher†, or Phys 123 or higher†
1	Math 133 or higher†
9	courses in computer science from the approved program

† Credit may be granted by examination.

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 200-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 (300-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 299.

This thesis must be based on an approved research project that is directed by a faculty member and approved by the departmental counselor.

Introductory Sequences. The kinds of computer science courses appropriate for undergraduates will vary according to each student's interests. Students interested in a general programming background are encouraged to take Computer Science 115 and 116 [Introduction to Computer Science I and II (Scheme, C++)]. Students in the humanities (or others with a humanistic background) and social sciences should take Computer Science 110-111 [Multimedia Web Programming as a Liberal Art I and II (HyperCard and QuickTime)]. Students with a strong mathematics background should consider the full Computer Science 115-116-117 sequence [Introduction to Computer Programming I, II, III (Scheme, C++)]. Students interested in a two-quarter introduction to the discipline should consider Computer Science 105-106 [Fundamentals of Computer Programming I, II (Scheme, C++)]. Computer Science 116 is recommended for students interested in further programming study. Students who want experience using and creating pages for the World Wide Web should take Computer Science 101-102.

Courses in Specific Areas of Computer Science. Students interested in artificial intelligence (AI) should take Computer Science 250 and 251 (Introduction to Artificial Intelligence), plus Computer Science 253 (Projects in Artificial Intelligence), in addition to Computer Science 115-116-117. Graduate-level AI courses are open to College students. These courses are numbered Computer Science 350 to 359. Consult the course listings for details.

Students interested in advanced programming, that is, systems, should take Computer Science 115-116-117, Computer Science 217 (Symbolic Programming), Computer Science 221 (Programming Languages), and Computer Science 222 (Computer Organization). Time permitting, they should also take Computer Science 230 (Operating Systems), and Computer Science 270 (Algorithms), and such courses in advanced programming topics that may be offered.

Students interested in theoretical computer science, that is, the mathematics of computation, should complete basic courses in algebra and then take Computer Science 270, as well as Computer Science 280 (Introduction to Formal Languages) and Computer Science 281 (Introduction to Complexity Theory). NOTE: Computer Science 115-116-117 is also recommended. Once students have completed Computer Science 270 and 280 or 281, they will be qualified for most of the advanced topics courses offered at the 300-level and above.

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 take as many computer science courses as possible, as well as concentrating in computer science. The most important ones are Computer Science 115-116-117, 222, 230, 270, and 281. Also important are Computer Science 221 and 280. Donald Crabb (departmental counselor and associate director of graduate and undergraduate studies) and Lance Fortnow (director of graduate studies) are available to discuss options for graduate study with students.

101-102. Introduction to Programming for the World Wide Web (HTML, CGI's, and Java). ComSci 102 (but not ComSci 101) can be used to fulfill the mathematical sciences requirement in general education. 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), and Common Gateway Interface (CGI) scripts (using Applescript and PERL). Students learn how to use Javascript to add client-side functionality and dynamic content to Web pages, set up a Web server (WebSTAR), write Java applets, and use communication components such as ActiveX and Javabeans. L. Fortnow, J. Simon, Staff. Summer, Winter, Spring.

105-106. Fundamentals of Computer Programming I, II (Scheme, C++). PQ: Math 102 or 106, or placement into 131 or equivalent; or consent of departmental counselor. These courses can be used to fulfill the mathematical sciences requirement in general education. This course is a basic introduction to computer programming using the Scheme and C++ programming languages that emphasize structure, algorithm construction, and design. Topics include variables, complex types, iteration, recursion, and procedural/functional/data abstraction. Both the ComSci 105-106 sequence and the ComSci 115-116 sequence are general introductions to computer programming. ComSci 105-106 assumes no previous programming experience and less advanced mathematical knowledge. This course is usually taught on a Macintosh microcomputer. S. Kurtz, T. Dupont, K. Mulmuley, G. Nadathur, L. Fortnow. Autumn, Winter.

110. Multimedia Web Programming as an Interdisciplinary Art I (HyperCard and QuickTime) (=ComSci 110, GS Hum 235). PQ: Math 102 or 106, or placement into 131 or equivalent; or consent of instructor. ComSci 110 can be used to fulfill 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 including Lingo, JavaScript, HyperTalk, AppleScript, and related scripting languages. As an introduction to programming in a multimedia context, the course presents techniques of problem solving, program coding, algorithm construction, and debugging using the Web as its programming environment. W. Sterner, D. Crabb. Winter.

111. Multimedia Web Programming as an Interdisciplinary Art II (HyperCard and QuickTime) (=ComSci 111, GS Hum 236). PQ: ComSci 110 or consent of instructor. ComSci 111 can be used to fulfill the mathematical sciences requirement in general education. This course continues ComSci 110, enlarging upon Web programming arts by identifying characteristic forms of applications that may be deployed on the Web as applets, including machines, models, simulations, and games as genres of argumentation. Students encounter such forms as recurrent scientific strategies that are making important contributions to new patterns of thinking in the humanities and in the social, biological, and physical sciences. They acquire more complete programming experience in multimedia user scripting languages. Topics include Turing Machines, multimedia objects, computer games, and the complexity of Web information delivery and access. W. Sterner, D. Crabb. Spring.

112. Introduction to Interactive Logic (=ComSci 112, GS Hum 237). PQ: Math 102 or 106, or placement into 131 or equivalent. Some experience with computers is helpful. This introductory course in first-order logic covers much of the same theoretical territory as a standard course in logic, but is much more "hands on." It 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 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 ComSci 110-111, but they are not prerequisites. W. Sterner. Spring.

115-116-117. Introduction to Computer Programming I, II, III (Scheme, C++). PQ: Placement into Math 151 or equivalent, or consent of departmental counselor. Students may take ComSci 105, then 116-117, although this is NOT recommended. Any course in the ComSci 115-116-117 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 ComSci 115-116-117 sequence is recommended for concentrators, as well as for all students planning to take more advanced courses in computer science. S. Kurtz, T. Dupont, K. Mulmuley, G. Nadathur, L. Fortnow, Staff. Summer, Autumn, Winter, Spring.

174. Discrete Mathematics. PQ: Placement into Math 151 or equivalent, or consent of departmental counselor. A directed course in topics needed by students taking the theory and algorithms sequence (ComSci 270, 280, and 281). Basic concepts of finite and structural mathematics including sets, axiomatic systems, proof by induction, recurrent problems, sums, floors and ceilings, divisibility and primes, binomial coefficients, and generating functions. Examples drawn from computer science including sequential machines, formal grammars, complexity, and algorithms. L. Babai, Staff. Autumn.

Other 200-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.

215. Logic and Logic Programming (=ComSci 215, Math 279). PQ: Math 254 or ComSci 315, 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, 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, refining resolution, and programming in Prolog, including searching, backtracking, and cut. This course overlaps only slightly with ComSci 315; students are encouraged to take both courses. R. Soare. Winter.

221. Programming Languages. PQ: ComSci 106 or 116, 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 a number of radically different languages to illuminate the variety of possible designs. G. Nadathur, J. Simon, Staff. Autumn.

222. Computer Organization. PQ: ComSci 106 or 116. This is an introduction to virtual machines and system organization. Topics include multilevel machines, digital logic, microprogramming, conventional machine, operating system, and assembly language. Comparisons are made of existing computer architectures. The course may include some assembly language programming. S. Kurtz, J. Simon, Staff. Winter.

230-231/330-331. Operating Systems I, II. PQ: ComSci 117 and 222, or consent of instructor. This course covers basic concepts of operating systems. Among the topics discussed are 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 currently taught on Sun workstations using UNIX. M. O'Donnell, Staff. Winter, Spring.

232. Advanced Programming Languages. PQ: ComSci 221 or consent of instructor. This course is a continuation of ComSci 221. S. Kurtz, R. Scott. Winter.

233/333. Networks and Distributed Systems. PQ: ComSci 230 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.

240. 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.

250. Introduction to Artificial Intelligence and LISP I (=ComSci 250, Psych 227). PQ: ComSci 105-106 or 115-116. This course is an introduction to the theoretical, technical, and philosophical issues of AI and looks at natural language processing, planning, problem solving, diagnostic systems, naïve physics, and game playing. LISP and LISP programming are introduced. K. Fenstermacher, Staff. Autumn.

251. Introduction to Artificial Intelligence and LISP II (=ComSci 251, Psych 228). PQ: ComSci 250. This is a continuation of the issues and topics introduced in ComSci 250. K. Fenstermacher, Staff. Winter.

253. Projects in Artificial Intelligence. PQ: ComSci 250-251 or consent of instructor. This course is a practicum in Artificial Intelligence. The goal is to teach students how to conceptualize a problem, organize behaviors, and then implement a complete AI system. Each student selects a particular project, collects data to define the behavior to be modeled, outlines examples, implements a system, and tests and evaluates it. Weekly meetings consist of progress reports, classroom discussion of work, and instruction as to the next step in project development. Each student is expected to develop a working system that includes a substantial Artificial Intelligence component and is itself an interesting and useful artifact. K. Fenstermacher, Staff. Spring.

270. Theory of Algorithms. PQ: ComSci 106 or 116, and Math 152 or 254; or consent of instructor. This course is based on analysis of the performance of algorithms. Some of the topics are algorithms for sorting and selecting the kth largest number out of n numbers, lower bounds for sorting and searching, dynamic programming, shortest path algorithms, minimum spanning tree algorithms, fast matrix multiplication, and fast integer multiplication. L. Babai, Staff. Winter.

274. Combinatorics and Probability (=ComSci 274, Math 284). PQ: Math 250 or 254, or ComSci 275, or consent of instructor. Experience with mathematical proofs. Problems and methods of enumeration, construction, and 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 permutations, combinations, linear recurrences, generating functions, principle of inclusion and exclusion, external set systems, 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, and probabilistic proofs of existence. L. Babai. Spring.

275. Graph Theory. PQ: Math 250 or 255, or consent of instructor. This course covers the basics of the theory of finite graphs, with an emphasis on algorithmic techniques. Among the topics are degree sequences, the matrix-tree theorem, Eulerian graphs, matchings, edge and vertex coloring, planarity, Menger's theorem, the max-flow/min-cut theorem, and Ramsey theory. This course is offered in alternate years. L. Babai, Staff. Autumn.

279. Chaos, Complexity, and Computers (=ComSci 279, Math 292, Phys 251). 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. S. Coppersmith. Winter.

280. Introduction to Formal Languages (=ComSci 280, Math 280). PQ: Math 250 or 255, and experience with mathematical proofs. Topics include automata theory, regular languages, CFL's, and Turing machines. This course is a basic introduction to computability theory and formal languages. This course is offered in alternate years. Staff. Autumn.

281. Introduction to Complexity Theory (=ComSci 281, Math 281). PQ: Math 250 or 255, 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. Staff. Autumn. Not offered 1999-2000; will be offered 2000-2001.

285. Introduction to Numerical Computation. PQ: Math 205 and 250, and ComSci 105 or 115; 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, Staff. Spring.

291. Three-Dimensional Computer Graphics. PQ: Consent of instructor. This course teaches students how to create lifelike three-dimensional scenes with a computer. We cover perspective projection, surface reflectance models, hidden surface elimination, shape representations (polygons, Bezier curves, B-splines, and superquadrics), modeling inter-reflections using ray tracing and environment maps, texture models, and difficulties (aliasing) caused by the discrete sampling inherent in an image. Not offered 1999-2000; will be offered 2000-2001.

295. 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, rather than signal analysis or special applications of synthesis, such as music or speech. Course work is divided among mathematical studies, listening exercises, and a cooperative project using synthesis software. M. O'Donnell. Spring.

297. 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.

298. 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.

315. Mathematical Logic I (=ComSci 315, Math 277). PQ: Math 254. This course provides an introduction to mathematical logic. Topics include propositional and predicate logic, natural deduction systems, models, and the syntactic notion of proof versus the semantic notion of truth, including soundness and completeness. The incompleteness theorems are also covered. This course is offered in alternate years. Staff. Autumn.

326. Compilers for Computer Languages. PQ: 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. Winter.

329-339. 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.

337-338. Logic and Databases. PQ: Consent of instructor. This seminar covers the latest research into logic and its role in databases. T. Gaasterland. Winter, Spring.

350. Representation and Memory. PQ: ComSci 250 and 251. This course is an introduction to artificial intelligence that focuses on the interaction between long-term knowledge and understanding. We cover issues in representation, memory organization, and the use of knowledge to control inference. Not offered 1999-2000; will be offered 2000-2001.

351. Natural Language Processing. PQ: ComSci 217, 350, and 352. An introduction to natural language processing, this course includes representation, parsing, natural language generation, and the interaction between long-term knowledge and understanding. Not offered 1999-2000; will be offered 2000-2001.

352. Planning and Problem Solving. PQ: ComSci 250 and 251. This course examines the current theories of planning and problem solving; including planning as search; hierarchical planning and constraint posting, and adaptive planning; and the problems of plan monitoring and reasoning about time and space. Not offered 1999-2000; will be offered 2000-2001.

353. Agency: Theories of Planning and Action (=ComSci 353, Psych 346). PQ: ComSci 350 and 352. The issues involved with the construction of autonomous intelligent agents are examined. We focus on the current work on agency being done by the Chicago AI Lab and explores problems of planning from memory, control of activity, integration of perception and reasoning, and learning from execution. Not offered 1999-2000; will be offered 2000-2001.

354. Machine Learning. PQ: ComSci 350 and 352. A look at one of the more problematic areas of machine intelligence: learning. After some historical examination of the ideas of category formation and inductive generalization, we examine current work in version space learning, explanation-based generalization, genetic algorithms, and learning from planning. Not offered 1999-2000; will be offered 2000-2001.

355. Computer Vision. PQ: ComSci 220. An introduction to the automation of visual perception and the mathematical and computational techniques that have been applied to this problem. Topics include image formation, boundary detection, and image segmentation; understanding shading, texture, stereo, motion, and color; and shape representation and object recognition. The course also introduces the incorporation of vision with action, including visual routines, tracking, and implementing a focus of attention. Not offered 1999-2000; will be offered 2000-2001.

356. Action and Perception. PQ: ComSci 217, 350, and 352. One area of AI that has always intrigued researchers is the problem of controlling autonomous agents in the real world. Past work has centered on producing plans to get things done. However, recent work has shown that action and perception must be tightly coupled interactive processes and that a plan must be constantly refined during its execution. The course examines interactive plan refinement, sensing, and action. Not offered 1999-2000; will be offered 2000-2001.

357. Qualitative Reasoning. PQ: ComSci 217, 350, and 352. An examination of formal theories of the common-sense world, naïve physics, and the logics that support it. Not offered 1999-2000; will be offered 2000-2001.

358. Advanced AI Programming Techniques. PQ: ComSci 217, 350, and 352. This is an advanced programming course aimed at teaching the skills needed in the development of large, working AI systems. Not offered 1999-2000; will be offered 2000-2001.

370. Algorithms. PQ: ComSci 270 or consent of instructor. Analysis and design of efficient algorithms, with emphasis on ideas rather than on implementation. Topics include asymptotic notation; basic algorithm design techniques such as recursion, dynamic programming, greedy algorithms, and amortized analysis; sorting and searching; and graph algorithms such as graph search, minimal spanning trees, and shortest paths. J. Simon. Autumn.

371. Combinatorial Optimization (=Bus 475, ComSci 371). PQ: ComSci 270 or consent of instructor. This course focuses on combinatorial problems such as shortest path, network flow, and matching. We also give a short introduction to linear programming to help analyze these problems. This course is offered in alternate years. K. Martin, Staff. Spring.

372. Combinatorics. PQ: ComSci 275 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. L. Babai. Spring.

373. Parallel Algorithms. PQ: ComSci 270 or consent of instructor. This course discusses models of parallel computation: shared memory and networks. Topics include basic algorithmic techniques, such as parallel prefix computation, list ranking, and tree-contraction routing problems, complexity classes, and completeness results, as well as randomized parallel algorithms. This course is offered in alternate years. J. Simon. Winter.

374. 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.

376. Linear Programming I (=Bus 472, ComSci 376). PQ: Knowledge of linear algebra. This is an introductory course in linear programming theory. Topics include polyhedral theory, finite basis theorems, theorems of the alternative, duality theory, sensitivity analysis, the simplex algorithm, and interior point algorithms. K. Martin. Winter.

377. Linear Programming II (=Bus 474, ComSci 377). PQ: ComSci 376 or consent of instructor. This is a course in large-scale linear and linear integer programming. There are three parts to the course. The first part is an introduction to integer programming. Topics include branch-and-bound and basis reduction algorithms. The second part is devoted to the decomposition of large problems using Dantzig-Wolfe, Benders, and Lagrangian methods. The third part of the course deals with computing LU factorizations of large basis matrices. K. Martin. Spring.

380-381. Computability Theory I, II (=ComSci 380-381, Math 302-303). PQ: Math 255 or consent of instructor. ComSci 380 concerns recursive (such as 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. ComSci 381 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.

382. Distributed Algorithms. PQ: ComSci 270 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.

385. Introductory Theory of Computing. PQ: Consent of instructor. An upper-level survey of computability and complexity theory. L. Fortnow, Staff. Autumn.

386. 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.

387. Complexity Theory B. PQ: Consent of instructor. Topics in computational complexity theory with an emphasis on combinatorial problems in complexity. Staff. Winter.

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

396. Topics in Theory. PQ: Consent of instructor. A seminar on current research topics in computing theory. Staff. Autumn, Winter, Spring.

398. Readings 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. Supervised readings in computer science. A project or written report is typically required. Staff. Summer, Winter, Spring

.