Departmental Counselor: Donald E. Crabb, Ry 161B, 702-7173,
decc@cs.uchicago.edu
Associate Director of Graduate and Undergraduate Studies: Donald E. Crabb, Ry 161B, 702-7173, decc@cs.uchicago.edu
Departmental and Concentration Secretary: Lori Gullickson, Ry 152,
702-1799, lori@cs.uchicago.edu
World Wide Web: http://www.cs.uchicago.edu/
The Department of Computer Science was founded in 1983 and began offering advanced degrees (M.S. and Ph.D.) soon after its inception. In 1995, the department began offering a concentration program in computer science to undergraduates.
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.
The requirements for a degree in computer science express the educational intent of the Department of Computer Science; they are designed around the concept of the cumulative character of an education based on computer science, mathematics, and the other sciences, as well as the interdisciplinary nature of a liberal arts education.
Requirements for the bachelor's degree look to the advancement of students' general education in computer science and their knowledge of its relation to the other sciences (Bachelor of Science) or to the other arts (Bachelor of Arts). Descriptions of the detailed requirements that give meaning to these educational intentions follow. Students should understand that any particular degree requirement can be modified if persuasive reasons are presented to the departmental counselor.
Placement. The Department of Computer Science does not offer credit or placement for Advanced Placement tests in computer science.
Undergraduate Programs. Two bachelor's degrees are available in the Department of Computer Science: the B.A. in computer science and the B.S. in computer science. Additionally, the Department of Mathematics administers a B.S. in mathematics with specialization in computer science. More information on this degree program can be found in the listings for the Department of Mathematics elsewhere in this catalog.
Both computer science baccalaureate degree programs require fulfillment of the College's general education requirements. Of these, the Common Core mathematical sciences requirement must be satisfied by completing an approved two-quarter calculus sequence. The Common Core physical sciences requirement must be satisfied by completing an approved one-year sequence in either chemistry or physics.
NOTE: It is the policy of the Division of Physical Sciences that students concentrating in computer science may not use physical sciences placement credit to fulfill the general education requirement.
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 which 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.
Degree Programs in Computer Science. Candidates for the B.A. and B.S. in computer science take a third quarter of calculus, 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.
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 interested in taking to fulfill the requirements.
Approved Mathematical Sciences Courses. The following sequences are approved for the mathematical sciences component of the Common Core, as well as the third quarter of calculus required for the concentration program:
Math 131-132-133
Math 151-152-153
Math 161-162-163
Approved Physical Sciences Courses
Chem 111-112-113
Chem 121-122-123
Phys 121-122-123
Phys 131-132-133
Phys 141-142-143
Approved Linear Algebra Courses
Math 250
Math 255
Math 258
Approved Course Sequences from Outside Computer Science
Astron 213-214
BioSci 196-197
Chem 111-112, or 121-122, if chemistry is not used to satisfy the physical sciences requirement.
Chem 201-202, 217-218, or 220-221
Econ 200-203, 210-211
GeoSci 231-232
Math 203-205, 207-209, 254-256, or 257-259
Philos 235-285
Phys 121-122, 131-132, or 141-142, if physics is not used to satisfy the physical sciences requirement.
Phys 225-227, or 234-235
Stat 220-222, 220-224, or 244-245
Approved Computer Science Concentration Program
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.
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
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 ComSci 280, or
ComSci 270 and ComSci 281
Artificial Intelligence Sequence (Two Courses Required):
ComSci 250-251
Approved Minor Programs
Three-course minor programs for the B.S. degree must be approved by the departmental counselor. Students are urged to consult early with the departmental counselor to discuss their choice.
Summary of Requirements
General Chem 111-112-113 or 121-122-123 or
Education Phys 121-122-123 or higher
Math 131-132, 151-152, or 161-162
Concentration 1 third quarter of a calculus sequence
9 courses in computer science, drawn from the approved program
plus the following requirements:
B.A. B.S.
3 courses from outside 1 course in linear algebra computer science, at least 2 courses from outside
two of which form an computer science forming
approved sequence an approved sequence
(See list on preceding page.) 3 courses in an approved
minor program in a related field outside computer
science
13 16
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 at 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 298.
This thesis must be based on an approved research project that is directed by a faculty member and approved by the departmental counselor.Recommended Sequences in Computer Science
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 [Computer Programming as a Liberal Art I and II (HyperCard)]. 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 who are 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.
LASZLO BABAI, Professor, Departments of Computer Science and Mathematics and the College
DONALD E. CRABB, Lecturer, Department of Computer Science and the College; Associate Director, Graduate and Undergraduate Studies, Department of Computer Science; Departmental Counselor, Department of Computer Science
TODD DUPONT, Professor, Departments of Computer Science and Mathematics and the College
LANCE FORTNOW, Associate Professor, Department of Computer Science and the College
IAN FOSTER, Associate Professor, Department of Computer Science and the College
TERRY GAASTERLAND, Assistant Professor, Department of Computer Science and the College
KRISTIAN J. HAMMOND, Associate Professor, Department of Computer Science and the College
STUART A. KURTZ, Professor, Department of Computer Science and the College
KETAN MULMULEY, Associate Professor, Department of Computer Science and the College
GOPALAN NADATHUR, Associate Professor, Department of Computer Science and the College
MICHAEL J. O'DONNELL, Professor, Department of Computer Science and the College
JANOS SIMON, Professor, Department of Computer Science and the College
ROBERT I. SOARE, Professor, Departments of Computer Science and Mathematics and the College
MICHAEL SWAIN, Assistant Professor,
Department of Computer Science and the College
Courses
There are three levels of courses listed below. Courses numbered 100 to 199 are open to both College students and graduate students but may only be taken for credit by College students. Courses numbered 200 to 299 are open to both College students and graduate students. Courses numbered 300 to 399 are open to College students with the consent of the instructor. Other graduate courses and seminars offered by the Department of Computer Science are open to College students with the consent of the instructor and the departmental counselor. Consult the departmental secretary for more information.
Undergraduate Courses
101-102. Introduction to the World Wide Web (HTML, CGI's, and Java). 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). 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. M. Swain, 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. ComSci 105-106 fulfills the Common Core requirement in the mathematical sciences. 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. D. Crabb, Staff. Autumn, Winter.
110. Computer Programming as a Liberal Art I: Programming Arts (HyperCard) (=ComSci 110, GS Hum 298). PQ: Math 102, or 106, or placement into 131 or equivalent; or consent of instructor. ComSci 110-111 fulfills the Common Core requirement in the mathematical sciences. This course aims to keep pace with how computing technology is penetrating the humanistic disciplines. Students learn to program on an Apple Macintosh in the HyperTalk language, within the multimedia application HyperCard, and to apply the skills of programming more generally as a liberal art. As an introduction to programming, the course presents techniques of problem solving, program coding, algorithm construction, and debugging using the object-like programming environment of HyperCard. D. Crabb, W. Sterner. Winter.
111. Computer Programming as a Liberal Art II: Programs as Arguments (HyperCard) (=ComSci 111, GS Hum 299). PQ: ComSci 110 or consent of instructor. ComSci 110-111 fulfills the Common Core requirement in the mathematical sciences. This is a continuation of ComSci 110, enlarging upon programming arts by identifying characteristic forms of computer programs, such as machines, models, simulations, and games as genres of argumentation. Students study 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. More complete programming experience in HyperCard's object-like techniques is fostered through case studies in the different programming genres. Topics include Turing Machines as general computing models and an interpretation of hypertextual discourse as a "computer game." D. Crabb, 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 two courses in the ComSci 115-116-117 sequence fulfill the Common Core requirement in the mathematical sciences. 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, M. Swain, Staff. Autumn, Winter, Spring.Undergraduate and Graduate Courses
Other 200-level courses may be offered. Please contact the department for further 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. 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. Winter.
230/330-231. 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. Staff. Spring (230/330); Not offered 1997-98, will be offered 1998-99 (231).
232. Advanced Programming Languages. PQ: ComSci 221 or consent of instructor. This course is a continuation of ComSci 221. S. Kurtz. Not offered 1997-98; will be offered 1998-99.
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 115-116 or 105-106. 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. Hammond, 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. Hammond. Winter.
253. Projects in Artificial Intelligence. PQ: ComSci 250-251 or consent of instructor. This course is a practicum in Artificial Intelligence. The goal of the class is to teach students how to conceptualize a problem, organize behaviors, and then implement a complete AI system. During the course, each student selects a particular project, collects data to define the behavior to be modeled, outlines examples, implements a system, then 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. Hammond. 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. Staff. Winter.
274. Combinatorics and Probability (=ComSci 274, Math 284). PQ: Math 250 or 254, or ComSci 275, or consent of instructor. Some 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. 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. L.
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. Staff. Not offered 1997-98; will be offered 1998-99.
285. Introduction to Numerical Computation. PQ: Math 205, 250, and ComSci 105 or 115; or consent of instructor. 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. To profit from this course, the student needs to be proficient in FORTRAN, C, or Pascal; the student should also know multivariable calculus, as well as the basic facts of linear algebra. M. Brenner. Spring.
291. Three-dimensional Computer Graphics. PQ: Consent of instructor. This course teaches how to create lifelike three-dimensional scenes with a computer. Students 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. M. Swain. Not offered 1997-98; will be offered 1998-99.
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. Winter.
298. Bachelor's Thesis. PQ: Open to fourth-year students who are candidates for honors in computer science. Consent of departmental counselor. Students are required to submit the College Reading and Research Course Form. Staff. Summer, Autumn, Winter, Spring.
299. 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.Graduate Courses
College students may register for graduate courses with the consent of the departmental counselor. Not all 300-level courses listed here will be offered each year, and other 300-level courses may be offered that are not listed. Please contact the departmental secretary for further information.
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. Staff. Not offered 1997-98; will be offered 1998-99.
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 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, which promises new capabilities qualitatively different from the Web browsers that dominate the Internet today, 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, focusing on the interaction between long-term knowledge and understanding. We cover issues in representation, memory organization, and the use of knowledge to control inference. Staff. Winter.
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. Staff. Not offered 1997-98; will be offered 1998-99.
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. J. Firby. Not offered 1997-98; will be offered 1998-99.
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. The class focuses 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. K. Hammond. Autumn.
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. J. Firby. Not offered 1997-98; will be offered 1998-99.
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. M. Swain. Spring.
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. J. Firby. Not offered 1997-98; will be offered 1998-99.
357. Qualitative Reasoning. PQ: ComSci 217, 350, and 352. An examination of formal theories of the commonsense world, naïve physics, and the logics that support it. Staff. Not offered 1997-98; will be offered 1998-99.
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. Staff. Not offered 1997-98; will be offered 1998-99.
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, and gives give a short introduction to linear programming to help analyze these problems. Staff. Not offered 1997-98; will be offered 1998-99.
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. Not offered 1997-98; will be offered 1998-99.
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. J. Simon. Not offered 1997-98; will be offered 1998-99.
374. Constructive Combinatorics. PQ: Consent of instructor and mathematical maturity. Covers constructive combinatorial techniques in several areas: enumerative combinatorics, invariant theory, representation theory of symmetric groups, and so on. 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. The winter quarter concerns recursive (that is, 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. The spring quarter 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. Not offered 1997-98; will be offered 1998-99.
385. Introductory Theory of Computing. PQ: Consent of instructor. An upper-level survey of computability and complexity theory designed for first-year graduate students. 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. Staff. Spring.
387. Complexity Theory B. PQ: Consent of instructor. Topics in computational complexity theory with an emphasis on combinatorial problems in complexity. Staff. Not offered 1997-98; will be offered 1998-99.
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 in current research topics in computing theory. Staff. Not offered 1997-98; will be offered 1998-99.
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 often required. Staff. Summer, Winter, Spring.