Return to Table of Contents

Go to Program of Study

Go to bottom of document

Courses

There are three levels of courses listed below. Courses numbered 100-199 are open to both College students and graduate students but may only be taken for credit by College students. Courses numbered 200-299 are open to both College students and graduate students. Courses numbered 300-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

105. Fundamentals of Computer Programming (Pascal). PQ: Math 102, or 106, or placement into 131 or equivalent; or consent of departmental counselor. ComSci 105 fulfills one half of the two-course Common Core requirement in the mathematical sciences. This course is a survey introduction to computer programming using the Pascal programming language that emphasizes structure, algorithm construction, and design. Topics include variables, complex types, iteration, recursion, and procedural/functional/data abstraction. This course is usually taught on a Macintosh microcomputer. D. Crabb, Staff. Summer, Autumn, Winter, Spring.

110. Computer Programming as a Liberal Art I: Programming Arts (HyperCard) (=GS Hum 298). PQ: Math 102, or 106, or placement into 131 or equivalent; or consent of instructors. ComSci 110-111 fulfills the Common Core requirement in the mathematical sciences. This course aims to keep pace with how computing technology is penetrating into 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) (=GS Hum 299). PQ: ComSci 110 or consent of instructors. 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. Summer, Autumn, Winter, Spring.

Undergraduate and Graduate Courses

Other 200-level courses may be offered during 1996-97. Please contact the department for further information.

215. Logic and Logic Programming (=Math 279). PQ: Math 254 or ComSci 315, or consent of instructor. Programming experience 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. This course is offered in alternate years. Staff. Winter. Not offered 1996-97; will be offered 1997-98.

221. Programming Languages. PQ: ComSci 116 or consent of instructor. Programming language design aims at the closest possible correspondence between the structures of a program and of the problem that it solves. This course studies some of the structural concepts affecting programming languages--iterative and recursive control flow, data types and type checking, procedural vs. 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. Winter.

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

230. Operating Systems. PQ: ComSci 117 and 222. 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. J. Firby. Autumn.

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-Z and other adaptive coding techniques, and specific applications. A. Bookstein. Winter.

250. Introduction to Artificial Intelligence and LISP I (=Psych 227). PQ: ComSci 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. Hammond, Staff. Autumn.

251. Introduction to Artificial Intelligence and LISP II (=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 covered 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 (=Math 284). PQ: Math 250 or 254, or ComSci 275, or consent of instructor. Some experience with 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, extremal 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. Winter.

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. Not offered 1996-97; will be offered 1997-98.

280. Introduction to Formal Languages (=Math 280). PQ: Math 250 or 255, and experience with mathematical proofs. Topics covered 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. Not offered 1996-97; will be offered 1997-98.

281. Introduction to Complexity Theory (=Math 281). PQ: ComSci 280. This course is a continuation of ComSci 280. More 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. Winter.

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

295. Digital Sound Modeling. PQ: Consent of instructor or some programming experience. 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. Coursework is divided between mathematical studies, listening exercises, and a cooperative project using synthesis software. M. O'Donnell. Spring. Not offered 1996-97; will be offered 1997-98.

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. 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 in 1996-97, and other 300-level courses may be offered that are not listed. Please contact the departmental secretary for further information.

315. Mathematical Logic I (=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. 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. Autumn.

330. Operating Systems. PQ: 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. Autumn.

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. K. Hammond. Autumn.

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

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

353. Agency: Theories of Planning and Action (=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. Spring.

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

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

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

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

370. Algorithms. PQ: ComSci 270 or consent of instructor. Analysis and design of efficient algorithms, with emphasis on the 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. Winter.

371. Combinatorial Optimization (=Bus 475). 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. Winter.

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 covered 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. Winter.

376. Linear Programming I (=Bus 472). PQ: Background in 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. This course is offered in alternate years. K. Martin. Winter.

377. Linear Programming II (=Bus 474). 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. Theory of Recursive Functions I, II (=Math 302-303). PQ: Math 255 or consent of instructor. Math 302 concerns recursive (i.e., 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. Math 303 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. This course is offered in alternate years. R. Soare. Winter, Spring. Not offered 1996-97; will be offered 1997-98.

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

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

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

395. Logic and Databases. PQ: Consent of instructor. A seminar covering the latest research into logic and its role in databases. T. Gaasterland. Winter.

396. Topics in Theory. PQ: Consent of instructor. A seminar in 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 often required. Staff. Summer, Autumn, Winter, Spring.

Go to top of document