** Next:** Computer Science Faculty
**Up:** Guide to Degree Programs
** Previous:** Ph.D. Program

By University convention, the numbering of courses is grouped by hundreds according to level of difficulty:

**0- 99:**- Introductory undergraduate courses
**100-199:**- Intermediate and advanced undergraduate courses. These courses may also be suitable for graduate students under certain circumstances; the Director of Graduate Studies (DGS) should be consulted.
**200-299:**- Courses for graduate students and advanced undergraduate students. Most courses are open to juniors and seniors with adequate preparation.
**300-399:**- Courses for graduate students

Within each hundred, the courses are numbered in order to reflect their particular subareas of computer science:

*x*00-*x*09:- General, programming, and programming theory.
*x*10-*x*19:- Systems.
*x*20-*x*29:- Architecture and modeling.
*x*30-*x*39:- Algorithms.
*x*40-*x*49:- Foundations and complexity. (Exception: the designation Computer Science 49S is required by Trinity College and is used to specify the first year seminar course.)
*x*50-*x*59:- Numerical analysis.
*x*60-*x*69:- Computational science.
*x*70-*x*79:- Artificial intelligence.
*x*80-*x*89:- Reserved for future use.
*x*90-*x*99:- Reading, research, and topics.

**1. Computer Science Fundamentals.** **(QR) **
An overview for students not intending to major in
computer science. Computer programming, numeric and symbolic computation,
electric circuits, architectures, translation, time complexity,
noncomputability and artificial intelligence. Not open to students
having credit for Computer Science 6 or higher.
One course.
*Biermann and staff*

**4. Introduction to Programming.** **(QR) **
A study of
clear thinking and problem solving using the computer. Representation,
problem decomposition and structured programming. Students learn a
modern computer language and develop skills by solving a variety of symbolic
and numerical problems. Not intended as an introduction to the major.

One course.
*Staff*

**6. Introduction to Program Design and Analysis I.** **(QR) **
Problem-solving techniques using a computer, top down decomposition
and object-oriented solution methodologies, introduction to programming,
programming in the C/C++ language, introduction to UNIX and programming
environments, recursion, analysis of execution times, linked data
structures, searching and sorting. Normally the first course for majors
in Computer Science who have no programming experience.

One course.
*Astrachan, Ramm or Rodger*

**49. First-Year Seminar.**
Topics vary each semester offered.
One course.
*Staff*

**100. Programming Design and Analysis II.** **(QR) **
A continuation of Computer Science 6 or 8.
Overview of advanced data structures and analysis of algorithms, data
abstraction and abstract data types, object-oriented programming, proofs
of correctness, complexity, and computability.

Prerequisite: Computer Science 6. One course.
*Astrachan or Rodger*

**100E. Programming Design and Analysis II.** **(QR) **
Same as Computer Science
100, except designed for students with considerable programmig
background who have not taken Computer Science 6.
Overview
of advanced data structures and analysis of algorithms, data
abstraction
and abstract data types, object-oriented programming, proofs of
correctnesss, complexity, and computability.
One course.
*Staff*

**104. Computer Organization and Programming.** **(QR) **
Computer structure,
machine language, instruction execution, addressing techniques, and
digital representation of data. Computer systems organization, logic
design, microprogramming and interpreters. Symbolic coding and assembly
systems.
Prerequisite: Computer Science 100 or consent of instructor.
One course.
*Ramm and staff*

**106. Programming Languages.** **(QR) **
Syntax and semantics of
programming languages. Compilation, interpretation, and programming
environments; including programming languages such as Algol,
PL/1, Pascal, APL, LISP, and Prolog. Exercises in programming.
Prerequisite: Computer Science 104. One course.
*Staff*

**108. Software Design and Implementation.** **(QR) **
Techniques for design and construction of reliable,
maintainable and useful software systems. Programming paradigms and
tools for medium to large projects: revision control, UNIX tools,
performance analysis, GUI, software engineering, testing, documentation.
Prerequisite: Computer Science 100. One course.
*Astrachan*

**109. Program Design and Construction.** **(QR) **
Substantial
programs. Design specifications, choice of data structures, estimation
of programming effort, stepwise development and program-testing
methodology. Programming teams and human factors in system implementation.
Advanced topics in use of a procedural language and file management.

Prerequisite: Computer Science 104. One course.
*Staff*

**110. Introduction to Operating Systems.** **(QR) **
Basic concepts
and principles of multi-programmed operating systems. Processes,
interprocess communication, CPU scheduling, mutual exclusion, deadlocks,
memory management, I/O devices, file systems, protection mechanisms.

Prerequisites: Computer Science 100 and 104. One course.
*Staff*

**120L. Introduction to Switching Theory and Logic Design.** **(QR) **
See C-L: Electrical Engineering 151L. One course.
*Marinos*

**130. Introduction to the Design and Analysis of Algorithms.** **(QR) **
Design and analysis of
efficient algorithms for sorting, searching, dynamic programming,
graph algorithms, fast multiplication and others; nondeterministic
algorithms and computationally hard problems.

Prerequisites: Computer Science 100 or equivalent and three semesters of
college mathematics. One course.
*Staff*

**140. Mathematical Foundations of Computer Science.** **(QR) **
An introduction to theoretical computer science including studies
of abstract machines, the language hierarchy from regular sets to
recursively enumerable sets, non-computability and the complexity
theory.

Prerequisites: Computer Science 100 and Mathematics 103. One course.
*Loveland or Rodger*

**148. Logic and Its Applications.** **(QR) **
Prerequisite: a course in logic or consent of instructor. See C-L:
Mathematics 188; also C-L: Philosophy 150. One course.
*Staff*

**149S. Problem Solving Seminar.** **(QR) **

Techniques for attacking, solving,
and writing computer programs for challenging computational problems.
Algorithmic and programming language tool kits. Course may be repeated. Consent
of instructor required. Half course.
*Staff*

**150. Introduction to Numerical Methods and Analysis.** **(QR) **
Theory, algorithms, and software that concern numerical
solution of linear equations, approximation and interpolation of functions,
numerical solution of nonlinear equations, and numerical solution
of ordinary differential equations.
Prerequisites: Computer Science 6; Mathematics 31; 32; 104 or 111.

One course.
*Staff*

**170. Methodologies in Artificial Intelligence.** **(QR) **
Theories of representation and search in artificial intelligence.
Logic, semantic networks, production rules, frames, distributed models,
and procedural representations; algorithmic and heuristic search.

One course.
*Biermann or Loveland*

**191, 192. Independent Study.**
Directed reading and research
for qualified juniors. Consent of instructor and Director of
Undergraduate Studies required. One course each.
*Staff*

**193, 194. Independent Study.**
Directed readings and
research for qualified seniors. Consent of instructor and Director of
Undergarduate Studies required. One course each.
*Staff*

**195. Computer Science Internship.**
Open to computer science
majors engaging in industrial work experience only. A faculty
member will supervise a program of study related to the work
experience, including a substantive paper containing significant
analysis and interpretation on a computer science-related topic.
Consent of director of internship programs required. Prerequisites:
Computer Science 104 and 108. One course.
*Staff*

**196. Topics in Computer Science.** **(QR) **
Topics from various areas
of computer science, changing each year.
Prerequisites: Computer Science 100 or equivalent.
One course.
*Staff*

**206. Programming Languages.** **(QR) **
Information binding, data structures and storage, control structures,
recursion, execution environments, input/output; syntax and semantics of
languages; study of PL/1, Fortran, Algol, APL, LISP, SNOBOL, and SIMULA;
exercises in programming.

Prerequisite: Computer Science 100.
c
*Wagner*

**208. Programming Methodology.** **(QR) **
Practical and theoretical topics including structured programming,
specification and documentation of programs, debugging and testing strategies,
choice and effective use of programming languages and systems, psychology of
computer programming, proof of correctness of programs, analysis of
algorithms, and properties of program schemata.

Prerequisite: Computer Science 100.
c
*Staff*

**210. Operating Systems.** **(QR) **
Fundamental principles of operating system design applied to
state-of-the-art computing environments (multiprocessors and distributed
systems) including process management (coscheduling and load balancing),
shared memory management (data migration and consistency), and distributed
file systems.

c
*Chase or Ellis*

**212. Distributed Information Systems.** **(QR) **
Principles and techniques for sharing information reliably and
efficiently in computer networks, ranging from high-speed clusters to
global-scale networks (for example, the Internet). Topics include advanced
distributed file systems, distributed programming environments, replication,
caching and consistency, transactional concurrency control, reliable update
and recovery, and issues of scale and security for Internet information
services. Prerequisites: Computer Science 210, or Computer Science 110 and
214, or consent of instructor.
c
*Chase*

**214. Computer Networks and Distributed Systems.** **(QR) **
Basic systems support for process-to-process communications across a
computer network. The TCP/IP protocol suite and the Berkeley sockets application
programs interface. Development of network application programs based on the
client-server model. Remote procedure call and implementation of remote
procedure call.

Prerequisite: knowledge of the C programming language.
c
*Staff*

**216. Data Base Methodology.** **(QR) **
Basic concepts and principles. Relational, hierarchical, and network
approaches to data organization; data entry and query language support for
database systems; theories of data organization; security and privacy issues.
Not open to student who have taken Computer Science 241.

Prerequisites: Computer Science 104 and either 109 or equivalent.
c
*Staff*

**218. Compiler Construction.** **(QR) **
Models and techniques used in the design and implementation of
assemblers, interpreters, and compilers. Lexical analysis, compilation of
arithmetic expressions and simple statements, specifications of syntax,
algorithms for syntactic analysis, code generation, and optimization techniques.

c
*Wagner*

**220. Advanced Computer Architecture I.** **(QR) **
Fundamental aspects of advanced computer architecture design
and analysis, with consideration of interaction with compilers, operating
systems, and application programs. Topics include processor design,
pipelining, caches (memory hierarchies), virtual memory, and advanced
storage systems, and simulation techniques. Advanced topics include a survey
of parallel architectures and future directions in computer architecture.
Prerequisite: Computer Science 104 or equivalent.
c
*Kedem, Lebeck, or Wagner*

**221. Advanced Computer Architecture II.** **(QR) **
Fundamental aspects of parallel computer architecture design and
analysis, including hardware/software tradeoffs, interactions with compilers,
operating systems, run-time libraries, and parallel applications. Topics
include parallel programming, message passing, shared memory, cache coherence,
cache consistency, bus-based shared memory, distributed shared memory,
interconnection networks, synchronization, on-chip parallelism. Prerequisite:
Computer Science 220 or equivalent.
c
*Lebeck*

**222. Introduction to VLSI Systems.**
A first course in VLSI design with CMOS technologies. A study of
devices, circuits, fabrication technology, logic design techniques, subsystem
design and system architecture. Modeling of circuits and subsystems. Testing of
gates, subsystems and chips, and design for testability. The fundamentals of
full-custom design, and some semi-custom design.

Prerequisites: Electrical Engineering 151 or equivalent; Electrical Engineering
161 or equivalent.
c
*Staff*

**223. Application Specific VLSI Design.** **(QR) **
Introductory VLSI design course. Modern
design methods and technology for implementing applications specific
integrated circuits (ASICs). Semicustom design
methodology, semicustom VLSI technologies such as gate arrays, standard
cell and FPGAs; the use of ASIC Computer Aided Design (CAD)
tools. Mapping algorithms into high performance silicon implementation.
Prerequisite: course in logic design.
c
*Kedem*

**225. Fault-Tolerant and Testable Computer Systems.**
Not open to students who have taken Computer Science 207.
Prerequisite: Electrical Engineering 151L or equivalent. See C-L:
Electrical Engineering 254.
c
*Marinos*

**226. Mathematical Methods for Systems Analysis I.** **(QR) **
Basic concepts and techniques used in the stochastic modeling of
systems. Elements of probability, statistics, queuing theory, and simulation.
Prerequisites: four semesters of college mathematics.
C-L: Electrical and Computer Engineering 255.
c
*Trivedi*

**230. Design and Analysis of Algorithms.** **(QR) **
Design and analysis of efficient algorithms. Algorithmic paradigms.
Applications include sorting, searching, dynamic structures, graph algorithms,
randomized algorithms. Computationally hard problems. NP completeness.

Prerequisite: Computer Science 100 or equivalent.
c
*Agarwal or Reif*

**232. Mathematical Analysis of Algorithms.** **(QR) **
Techniques for efficient implementation and precise analysis of
computer algorithms. Combinatorial mathematics and elementary probability.
Emphasis on obtaining exact closed-form expressions describing the
worst-case and average-case time and space requirements for particular
computer algorithms, whenever possible. Asymptotic methods of analysis
for obtaining approximate expressions in situations where
exact expressions are too difficult to obtain or to interpret.

Prerequisites: Mathematics 103 and 104 or equivalents.
c
*Vitter*

**234. Computational Geometry.** **(QR) **
Models of computation and lower-bound techniques; storing and
manipulating orthogonal objects; orthogonal and simplex range searching,
convex hulls, planar point location, proximity problems, arrangements, linear
programming and parametric search technique, probabilistic and incremental
algorithms.

Prerequisite: Computer Science 230 or equivalent.
c
*Agarwal or Reif*

**235. Topics in Data Compression.** **(QR) **
Emphasis on the redundancies found in textual, still-frame images,
video, and voice data, and how they can be effectively removed to achieve
compression. The compression effects in information processing. Additional
topics may include information theory, the vulnerability of compressed data
to transmission errors, and the loss of information with respect to the
human visual system (for image data). Available compression technologies and
the existing compression standards. Prerequisites: Computer Science 130 and
208 or Computer Science 254 or Electrical Engineering 282.
c
*Markas or staff*

**236. Parallel Algorithms.** **(QR) **
Models of parallel computation including parallel random access
machines, circuits, and networks; NC algorithms and P-completeness; graph
algorithms, sorting algorithms, network routing, tree contraction, string
matching, parsing algorithms; randomization and derandomization techniques.

Prerequisite: Computer Science 230 or equivalent.
c
*Reif*

**240. Computational Complexity.** **(QR) **
Turing machines, undecidability, recursive function theory,
complexity measures, reduction and completeness, NP, NP-Completeness,
co-NP, beyond NP, relativized complexity, circuit complexity, alternation,
polynomial time hierarchy, parallel and randomized computation, algebraic
methods in complexity theory, communication complexity.

Prerequisite: CPS 140 or equivalent.
c
*Agarwal*

**250. Numerical Analysis.** **(QR) **
Error analysis, interpolation and spline approximation, numerical
differentiation and integration, solutions of linear systems, nonlinear
equations, and ordinary differential equations.

Prerequisites: knowledge of an algorithmic programming language, intermediate
calculus including some differential equations, and Mathematics 104.
C-L: Mathematics 221 and Statistics 273.
c
*Rose or Sun*

**252. Numerical Methods for Partial Differential Equations.** **(QR) **
Survey of theory, algorithms, and codes for the
numerical solution of nonlinear partial differential equations of
initial value and boundary value type. Topics include
finite-difference, spectral, and finite-element representations;
stability of time-discretization techniques; adaptive spatial
meshes; multigrid and preconditioned conjugate gradient
techniques; solution on parallel computers.
Prerequisite: Computer Science 250. C-L Mathematics 222.
c
*Rose or Sun*

**254. Numerical Linear Algebra.** **(QR) **
Solution of large, sparse linear systems of equations. Storage
schemes, graph theory for sparse matrices, different orderings to minimize
fill, block factorizations, iterative methods, analysis of different
splittings, conjugate gradient methods. Eigenvalue problems, QR factorization,
Lanczos method, power method and inverse iteration, Rayleigh quotient.

Prerequisite: Computer Science 250 or equivalent.
C-L: Mathematics 223.
c
*Rose or Sun*

**260. Introduction to Computational Science.**
Introduction for students and faculty to computing
resources that facilitate research involving scientific computing:
contemporary computers, programming languages, numerical software packages,
visualization tools, and some basic issues and methods for high performance
algorithm design.

Prerequisites: Programming experience in Fortran or C, calculus, numerical
linear algebra or equivalent.
c
*Greenside, Rose, or Sun*

**264. Nonlinear Dynamics.** **(QR) **
Introduction to the mathematical theory of nonlinear dynamics, and
how this theory compares with physical experiments, with applications to biology
(Turing states and morphogenesis), computer science (randomness and
computability), mathematics (chaos and strange attractors), and physics
(pattern formation and transition to turbulence).

Prerequisites: Computer Science 6, Mathematics 111, and Physics 51L, 52L.
C-L: Physics 213.
c
*Behringer or Greenside*

**266. Communication, Computation, and Memory in Biological Systems.** **(QR) **
Communication and memory in biological systems: voltage sensitive ion
channels, hormone-receptor interactions, and initiation and control of Rna/DNA
synthesis. Models of signaling and memory are developed and related to
electronic signaling schemes. Prerequisites: Computer Science 100, two
semesters of college chemistry, and four semesters of college mathematics.
c
*Starmer*

**270. Artificial Intelligence.** **(QR) **
Heuristic versus algorithmic methods; programming of games such as
chess; theorem proving and its relation to correctness of programs; readings in
simulation of cognitive processes, problem solving, semantic memory, analogy,
adaptive learning.

Prerequisite: Computer Science 100 or consent of instructor.
c
*Biermann or Loveland*

**271. Numeric Artificial Intelligence.** **(QR) **
Introduction to the core areas of artificial intelligence from
a quantitative perspective. Topics include planning in deterministic and
stochastic domains; reasoning under uncertainty, optimal decision making;
computer speech, computer vision, and robotics; machine learning, supervised
and reinforcement learning; natural language processing; agents. Minimal overlap
with Computer Science 270. Prerequisite: Computer Science 100 or consent of
instructor.
c
*Littman*

**274S. Computational Linguistics Seminar.** **(QR) **
Readings and research seminar on topics related to the processing of
English or other natural languages: syntax, semantics, pragmatics, discourse,
and others.

Prerequisite: Computer Science 270 or consent of the instructor.
c
*Biermann*

**300. Computer Science Research Seminar.**
The course is designed to orient first-year graduate students and
provide an in-depth look at the research projects going on in the department.
The course also emphasizes the necessary skills for research investigation and
presentation in computer science. In particular, instruction is given in how
to formulate research problems or projects, identify goals, and present
results. (Concentration on the problem-solving aspect of research is the
focus of the research project or thesis during the following semester.)
Students will make and critique technical presentations, both oral and
written.

3 units.
*Staff*

**312. Operating Systems Theory.**
Advanced study of theoretical aspects of operating systems emphasizing
models and control of concurrent processes, processor scheduling, and memory
management.

Prerequisites: Computer Science 226 and 210.
3 units.
*Chase, Ellis or Wagner*

**320. Advanced Topics in Digital Systems.**
A selection of advanced topics from the areas of digital computer
architectures and fault-tolerant computer design.

See C-L: Electrical and Computer Engineering 352.
3 units.
*Marinos*

**322. CMOS VLSI Design.**
A second course in VLSI, aimed at the design of VLSI systems in CMOS.
The main thrusts of the course will be (1) to provide enough background in the
theory of CMOS circuits to understand circuit level trade-offs; (2) to
introduce a symbolic design system and its supporting software, which greatly
aid the design process; and (3) to examine sample chip designs with an eye to
understanding competitive design methodologies. Students will complete a
CMOS-oriented project comprising the design and implementation of either a
hardware or a software subsystem.

Prerequisite: Computer Science 222 or equivalent.
C-L: Electrical and Computer Engineering 361.
3 units.
*Kedem*

**326. Systems Modeling.**
Advanced study of analytical models of systems; queuing model and its
parameterization and validation. Methods for computer solutions of some models.
Prerequisites: Computer Science 226 and 210.
3 units.
*Trivedi*

**327. Seminar in Computer Systems Analysis.**
Topics in computer systems analysis, especially for fault-tolerant
systems, including reliability, availability and performance analysis,
comparative analysis of architectures, performability, analytic and numerical
solution techniques, stochastic Petri nets, simulation.
1 to 3 units.
*Staff*

**337. VLSI Algorithms.**
Algorithmic and systems aspects of VLSI. Topics include theoretical
studies of the layout problem, array logic, placement and routing,
fault-tolerance in VLSI designs, design for testability, the design of networks
of processors, and cost trade-offs in VLSI designs. Each student will
complete an in-depth study of a topic approved by the instructor.

Prerequisites: Computer Science 230 and either 222 or 322.
3 units.
*Staff*

**350. Topics in Numerical Mathematics.**
Advanced topics in numerical mathematics to be selected from areas of
current research.
Prerequisites: Computer Science 250 and 252.
3 units.
*Greenside, Rose, or Sun*

**364. Advanced Topics in Nonlinear and Complex Systems.**
Survey of current research topics that may include: advanced signal
analysis (wavelets, Karhunen-Loeve decomposition, multifractals),
bifurcation theory (amplitude and phase equations, symmetry breaking),
spatiotemporal chaos, granular flows, broken ergodicity, complexity theory
of dynamical systems, and adaptive systems (genetic algorithms, neural
networks, artificial life). Quantitative comparisons between theory,
simulations, and experiments will be emphasized.

Prerequisite: Computer Science/Physics 264 required; Physics 230, 231,
and 303 or equivalents are strongly recommended as further background.
C-L: Physics 313.
3 units.
*Behringer, Greenside, or Palmer*

**370. Seminar in Artificial Intelligence.**
Topics in artificial intelligence, such as natural
language
understanding, learning, theorem proving and problem solving,
search
methodologies. Topics will vary from semester to semester.
Includes research
literature reading with student presentation.
1 to 3 units.
*Staff*

**376. Advanced Topics in Artificial Intelligence.**
Course content will vary from year to year and will include a detailed
study of one or more of the following: mechanical theorem proving, natural
language processing, automatic program synthesis, machine learning and
inference, representations of knowledge, language for artificial intelligence
research, artificial sensorimotor systems, and others.

Prerequisite: Computer Science 270.
3 units.
*Biermann or Loveland*

**391. Internship.**
The student is required to gain practical computer
science experience by taking a job in industry. The student
writes a report about this experience. Requires prior consent
from the student's advisor and from the Director of Graduate
Studies. Pass/fail grading only. May be repeated with
permission of the advisor and the Director of Graduate Studies. 1
unit.
*Staff*

**395. Research.**
Instruction in methods used in the investigation of original problems.
Individual work and conferences.
1 to 6 units.
*All members of the graduate staff*

**310. Topics in Operating Systems** (formerly Computer Science 332).

**340. Theory of Computation** (formerly Computer Science 325).

**Comp 145. Software Engineering Laboratory
Comp 171. Natural Language Processing
Comp 230. File Management Systems
Comp 236. Computer Graphics
Comp 238. Raster Graphics
Comp 254. Picture Processing and Pattern Recognition
Comp 265. Architecture of Computers**

Duke Department of Computer Science