Go to bottom of document
Go to: Undergraduate Courses
105. Fundamentals of Computer Programming. PQ: Math 102 or 106 or
placement into Math 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 (=GS Hum 298).
PQ: Math 102, 106, placement into Math 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 (=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. PQ:
Placement into Math 151 or equivalent, or consent of departmental counselor.
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.
Go to top of document
Other 200-level courses may be offered during 1995-96. 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 necessary.
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. R. Soare.
Winter.
217. Symbolic Programming. PQ: ComSci 220. An introduction to
symbolic reasoning techniques useful in building "expert systems" and other
large, knowledge-intensive systems. Topics include automated inference,
deductive retrieval, unification, and search. The course takes a pragmatic,
hands-on approach, with an emphasis on building systems in LISP and Prolog.
J. Firby. Winter.
220. Data Structures. PQ: ComSci 106, 109, or 116. This course
teaches the C++ programming language, and the programming assignments are done
in a UNIX environment on Sun workstations. Topics include classes (C++
user-defined data types), information hiding, object-oriented programming,
arrays, stacks, queues, hashing, heaps, balanced search trees, and various
linked structures. This course will not be offered after 1995-96; ComSci 117
will take its place. T. Dupont. Autumn.
221. Programming Languages. PQ: ComSci 106 or 116. 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. M. O'Donnell. 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. Staff. Spring.
230. Operating Systems. PQ: ComSci 220 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.
Go to top of document 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). 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 or consent of instructor. This is a continuation of
the issues and topics introduced in ComSci 250. C. Martin, K. Hammond.
Winter.
253. Projects in Artificial Intelligence. PQ: ComSci 250-251 or consent
of instructor. A different topic is explored each year. 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 (=Math 284). PQ: Math 254 or consent of instructor.
Problems of enumeration, existence, construction, and optimization of
discrete structures are covered. Also covered are permutations and
combinations, linear recurrences, generating functions, enumeration of rooted
trees, principle of inclusion and exclusion, the Möbius inversion formula,
Polya's theory of counting, systems of distinct representatives, construction
of block designs, error correcting codes, Hadamard matrices, backtrack methods,
and dynamic programming. L. Babai. Spring.
275. Graph Theory. PQ: Math 250, 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 1995-96; will
be offered 1996-97.
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. L. Fortnow. Autumn.
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. L. Fortnow. Not offered 1995-96; will be offered
1996-97.
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.
Go to top of document 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, 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 the mathematics and
computational aspects of sound representation covering, in addition to its
obvious quantitative aspects, sound generation models in the lab. M.
O'Donnell. Spring.
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 Form. Staff.
Autumn, Winter, Spring.
299. Reading and Research in Computer Science. PQ: Consent of the
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.
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 1995-96, and other 300-level courses may be offered during 1995-96. Please
contact the department 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. T. Slaman.
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. C. Martin, Staff.
Autumn.
350. Representation and Memory. PQ: ComSci 250 and 251. A graduate
introduction to artificial intelligence, focusing on the interaction between
long-term knowledge and understanding. This course covers 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. A
graduate introduction to natural language processing, this course includes
representation, parsing, natural language generation, and the interaction
between long-term knowledge and understanding. C. Martin. Spring.
352. Planning and Problem Solving. PQ: ComSci 250 and 251. This is
an examination of 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.
Go to top of document 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. C. Martin. 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. This course is offered
in alternate years. J. Simon. Winter. Not offered 1995-96; will be offered
1996-97.
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. This course is offered in
alternate years. Staff. Winter. Not offered 1995-96; will be offered
1996-97.
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.
This course is offered in alternate years. L. Babai. Spring. Not offered
1995-96; will be offered 1996-97.
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. This course is offered in alternate years. J. Simon. Winter. Not
offered 1995-96; will be offered 1996-97.
376. Linear Programming I (=Bus 472). PQ: 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. C. Martin. Not offered 1995-96;
will be offered 1996-97.
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.
This course is offered in alternate years. C. Martin. Not offered
1995-96; will be offered 1996-97.
380. Theory of Recursive Functions I (=Math 302). PQ: Math 255 or
consent of instructor. This course concerns recursive (i.e., computable)
functions and sets generated by an algorithm (i.e., 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. This course
is offered in alternate years. R. Soare. Winter. Not offered 1995-96;
will be offered 1996-97.
Go to top of document 381. Theory of Recursive Functions II (=Math 303). PQ: ComSci 380.
This course 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. Not offered 1995-96; will
be offered 1996-97.
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. This course is offered in alternate
years. J. Simon. Winter. Not offered 1995-96; will be offered
1996-97.
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. 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. Winter.
Not offered 1995-96; will be offered 1996-97.
387. Complexity Theory B. PQ: Consent of instructor. Topics in
computational complexity theory with an emphasis on combinatorial problems in
complexity. This course is offered in alternate years. Staff. Winter.
Not offered 1995-96; will be offered 1996-97.
Go to middle of document
Go to: Undergraduate and Graduate Courses
Go to: Graduate Courses
Computer Science 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.
Contact the departmental secretary for more information.Undergraduate Courses
Go to bottom of documentUndergraduate and Graduate Courses
Go to bottom of document
Go to bottom of documentGraduate Courses
Go to bottom of document
Go to bottom of document