
CS (and related) Undergraduate Courses
Revised June, 2014
The courses listed below are relevant for computer science majors. See the
Undergraduate Catalog for information about additional SCS
courses including available electives.
COMPUTER SCIENCE
15050 Study Abroad
Fall and Spring
Students who are interested in studying abroad should first contact the
Office of International Education.
More information on Study Abroad is available on OIE's Study
Abroad page and at the CS Undergraduate Office.
15075
Computer Science CoOp
Fall and Spring
Students who are interested in a CoOp experience with an external employer
typically do so in their Junior year. A CoOp is distinguished from a
summer internship in that it encompasses a summer and a contiguous semester,
either SpringSummer or SummerFall. A list of companies who are interested
in hiring CoOp students is available from the SCS Career Consultant at
the Career Center. More information on the Computer Science CoOp program
is available at the CS Undergraduate Office.
15090
Computer Science Practicum
Summer: 3 units
This course is for international students who are interested in working
for Curricular Practical Training (CPT). Such students interested in CPT
must first be authorized by the
Office of International Education before being able to enroll in the
Practicum course. More information on CPT is available on OIE's Foreign
Student Employment page and at the CS Undergraduate Office.
15112 Fundamentals of Programming and Computer Science
Fall and Spring: 12 units
A technical introduction to the fundamentals of programming with an
emphasis on producing clear, robust, and reasonably efficient code using
topdown design, informal analysis, and effective testing and debugging.
Starting from first principles, we will cover a large subset of the Python
programming language, including its standard libraries and programming
paradigms. We will also target numerous deployment scenarios, including
standalone programs, shell scripts, and webbased applications. This
course assumes no prior programming experience. Even so, it is a
fastpaced and rigorous preparation for 15122. Students seeking a more
gentle introduction to computer science should consider first taking
15110. NOTE: students must achieve a C or better in order to use this
course to satisfy the prerequisite for any subsequent Computer Science
course.
15122 Principles of Imperative Computation
Fall and Spring: 10 units
For students with a basic understanding of programming (variables,
expressions, loops, arrays, functions). Teaches imperative programming and
methods for ensuring the correctness of programs. Students will learn the
process and concepts needed to go from highlevel descriptions of
algorithms to correct imperative implementations, with specific
application to basic data structures and algorithms. Much of the course
will be conducted in a subset of C amenable to verification, with a
transition to full C near the end. This course prepares students for
15213 and 15210. NOTE: students must achieve a C or better in order
to use this course to satisfy the prerequisite for any subsequent Computer
Science course.
Prerequisite: 15112. Corequisite: 21127 or 15151.
15128 Freshman Immigration Course (Pittsburgh)
Fall: 1 unit
The Freshman Immigration Course is taken by firstsemester Computer
Science majors on the Pittsburgh campus. The course is designed to
acquaint incoming majors with computer science at CMU. Talks range from
historical perspectives in the field to descriptions of the cutting edge
research being conducted in the School of Computer Science. Enrollment is
limited to SCS Freshmen in Pittsburgh ONLY.
15129 Freshman Immigration Course II (Doha, Qatar)
Fall: 3 units
This course is ONLY offered at Carnegie Mellon in Qatar. Students and
instructors will solve different problems each week by searching the Web
and other likely places for answers. The problems will be submitted by
other faculty who will grade the quality of the answers. Students will
learn strategies and techniques for finding information on the Web more
efficiently; learn when to start with a search engine, a subjectoriented
directory, or other tools; explore and practice using advanced search
syntax for major search engines; experience specialized search engines for
images, sound, multimedia, newsgroups, and discussion lists as well as
subjectspecific search engines; discover valuable resources to help keep
you uptodate in this fastchanging environment.
15131 Great Practical Ideas in Computer Science (Pittsburgh)
Fall: 2 units
THIS COURSE IS OPEN TO CS FRESHMAN IN PITTSBURGH ONLY.
Throughout your education as a
Computer Scientist at Carnegie Mellon, you will take courses on
programming, theoretical ideas, logic, systems, etc. As you progress, you
will be expected to pick up the socalled "tools of the trade." This
course is intended to help you learn what you need to know in a friendly,
lowstress, highsupport way. We will discuss UNIX, LaTeX, debugging and
many other essential tools. Laptop required. (Laptops will be available
for those without their own laptops.)
15150 Principles of Functional Programming
Fall and Spring: 10 units
An introduction to programming based on a "functional" model of
computation. The functional model is a natural generalization of algebra
in which programs are formulas that describe the output of a computation
in terms of its inputsthat is, as a function. But instead of being
confined to real or complexvalued functions, the functional model
extends the algebraic view to a very rich class of data types, including
not only aggregates built up from other types, but also functions
themselves as values. This course is an introduction to programming that
is focused on the central concepts of function and type. One major theme
is the interplay between inductive types, which are built up
incrementally; recursive functions, which compute over inductive types by
decomposition; and proof by structural induction, which is used to prove
the correctness and time complexity of a recursive function. Another major
theme is the role of types in structuring large programs into separate
modules, and the integration of imperative programming through the
introduction of data types whose values may be altered during computation.
NOTE: students must achieve a C or better in order to use this course
to satisfy the prerequisite for any subsequent Computer Science
course.
Prerequisites: (21127 or 15151) and (15112).
15151 Mathematical Foundations of Computer Science
Fall: 10 units
This course is offered to incoming Computer Science freshmen and focuses
on the fundamental concepts in Mathematics that are of particular interest
to Computer Science such as logic, sets,induction, functions, and
combinatorics. These topics are used as a context in which students learn
to formalize arguments using the methods of mathematical proof. This
course uses experimentation and collaboration as ways to gain better
understanding of the material. Open to CS freshmen only (Fall 2012 and
Fall 2013).
NOTE: students must achieve a C or better in order to use this course
to satisfy the prerequisite for any subsequent Computer Science course.
15210 Parallel and Sequential Data Structures and Algorithms
Fall and Spring: 12 units
Teaches students about how to design, analyze, and program algorithms and
data structures. The course emphasizes parallel algorithms and analysis,
and how sequential algorithms can be considered a special case. The course
goes into more theoretical content on algorithm analysis than 15122 and
15150 while still including a significant programming component and
covering a variety of practical applications such as problems in data
analysis, graphics, text processing, and the computational sciences.
NOTE:
students must achieve a C or better in order to use this course to satisfy
the prerequisite for any subsequent Computer Science course.
Prerequisite: 15122 and 15150.
15213 Introduction to Computer Systems
Fall and Spring: 12 units
This course provides a programmer's view of how computer systems execute
programs, store information, and communicate. It enables students to
become more effective programmers, especially in dealing with issues of
performance, portability and robustness. It also serves as a foundation
for courses on compilers, networks, operating systems, and computer
architecture, where a deeper understanding of systemslevel issues is
required. Topics covered include: machinelevel code and its generation by
optimizing compilers, performance evaluation and optimization, computer
arithmetic, memory organization and management, networking technology and
protocols, and supporting concurrent computation. NOTE: students must
achieve a C or better in order to use this course to satisfy the
prerequisite for any subsequent Computer Science course.
Prerequisite: 15122.
15214 Principles of Software Construction: Objects, Design, and
Concurrency
Fall and Spring: 12 units
Software engineers today are less likely to design data structures and
algorithms from scratch and more likely to build systems from library and
framework components. In this course, students engage with concepts
related to the construction of software systems at scale, building on
their understanding of the basic building blocks of data structures,
algorithms, program structures, and computer structures. The course covers
technical topics in four areas: (1) concepts of design for complex
systems, (2) object oriented programming, (3) static and dynamic analysis
for programs, and (4) concurrent and distributed software. Student
assignments involve engagement with complex software such as distributed
massively multiplayer game systems and frameworks for graphical user
interaction.
Prerequisites: (15121 or 15122) and (21127 or 15151).
15221 Technical Communications for Computer Scientists
Fall and Spring: 9 units
The course is designed for sophomore computer science majors to improve
their abilities in practical, professional communications (both written
and oral). It aims to help students compose clear, concise technical
writings and oral presentations for multilevel audiences. Assignments
include technical definitions, descriptions, instructions, process
explanations, abstracts, memos, and research reports. Assignments may
incorporate recent computer science research at Carnegie Mellon, projects
in related technical courses, and professional case studies. Sophomores
will likely find the course more useful if they have either had an
internship or facultysupervised research, including SURG projects prior
to enrollment.
Prerequisite: 76101.
15251 Great Theoretical Ideas in Computer Science
Fall and Spring: 12 units
This course is about how to use theoretical ideas to formulate and solve
problems in computer science. It integrates mathematical material with
general problem solving techniques and computer science applications.
Examples are drawn from algorithms, complexity theory, game theory,
probability theory, graph theory, automata theory, algebra, cryptography,
and combinatorics. Assignments involve both mathematical proofs and
programming. NOTE: students must achieve a C or better in order to use
this course to satisfy the prerequisite for any subsequent Computer
Science course.
Prerequisites: (15112) and (21127 or 15151).
15312 Foundations of Programming Languages
Fall and Spring: 12 units
This course discusses in depth many of the concepts underlying the design,
definition, implementation, and use of modern programming languages.
Formal approaches to defining the syntax and semantics are used to
describe the fundamental concepts underlying programming languages. A
variety of programming paradigms are covered such as imperative,
functional, logic, and concurrent programming. In addition to the formal
studies, experience with programming in the languages is used to
illustrate how different design goals can lead to radically different
languages and models of computation.
Prerequisites: 15210 and 15251.
15313 Foundations of Software Engineering
Fall and Spring: 12 units
Students gain exposure to the fundamentals of modern software engineering.
This includes both core CS technical knowledge and the means by which this
knowledge can be applied in the practical engineering of complex software.
Topics related to software artifacts include design models, patterns,
coding, static and dynamic analysis, testing and inspection, measurement,
and software architecture and frameworks. Topics related to software
process include modeling, requirements engineering, process models and
evaluation, team development, and supply chain issues including
outsourcing and open source. This course has a strong technical focus, and
will include both written and programming assignments. Students will get
experience with modern software engineering tools.
Prerequisite: 15214.
15317 Constructive Logic
Fall: 9 units
This multidisciplinary juniorlevel course is designed to provide a
thorough introduction to modern constructive logic, its roots in
philosophy, its numerous applications in computer science, and its
mathematical properties. Some of the topics to be covered are
intuitionistic logic, inductive definitions, functional programming, type
theory, realizability, connections between classical and constructive
logic, decidable classes.
Prerequisite: 15150.
15322 Introduction to Computer Music
Spring (every other year): 9 units
Computers are used to synthesize sound, process signals, and compose
music. Personal computers have replaced studios full of sound recording
and processing equipment, completing a revolution that began with
recording and electronics. In this course, students will learn the
fundamentals of digital audio, basic sound synthesis algorithms, and
techniques for digital audio effects and processing. Students will apply
their knowledge in programming assignments using a very highlevel
programming language for sound synthesis and composition. In a final
project, students will demonstrate their mastery of tools and techniques
through music composition or by the implementation of a significant
soundprocessing technique.
Prerequisite: 15112.
15323 Computer Music Systems and Information Processing
Spring (every other year): 9 units
This course presents concepts and techniques for representing and
manipulating discrete music information, both in real time and off line.
Representations of music as explicitly timed event sequences will be
introduced, and students will learn how to build efficient runtime
systems for event scheduling, tempo control, and interactive processing.
The MIDI protocol is used to capture realtime performance information and
to generate sound. The course will also cover nonrealtime processing of
music data, including Markov models, style recognition, computer
accompaniment, querybyhumming, and algorithmic composition. This course
is independent of, and complementary to 15322, Introduction to Computer
Music, which focuses on sound synthesis and signal processing.
Prerequisite: 15122.
15354 Computational Discrete Mathematics
Fall: 12 units
This course is about the computational aspects of some of the standard
concepts of discrete mathematics (relations, functions, logic, graphs,
algebra, automata), with emphasis on efficient algorithms. We begin with a
brief introduction to computability and computational complexity. Other
topics include: iteration, orbits and fixed points, order and equivalence
relations, propositional logic and satisfiability testing, finite fields
and shift register sequences, finite state machines, and cellular
automata. Computational support for some of the material is available in
the form of a Mathematica package.
Prerequisite: 15251 or 21228.
15355 Modern Computer Algebra
Spring: 9 units
The goal of this course is to investigate the relationship between algebra
and computation. The course is designed to expose students to algorithms
used for symbolic computation, as well as to the concepts from modern
algebra which are applied to the development of these algorithms. This
course provides a handson introduction to many of the most important
ideas used in symbolic mathematical computation, which involves solving
system of polynomial equations (via Groebner bases), analytic integration,
and solving linear difference equations. Throughout the course the
computer algebra system Mathematica will be used for computation.
Prerequisite: 15251.
15359 Probability and Computing
Spring: 12 units
Probability theory has become indispensable in computer science. In areas
such as artificial intelligence and computer science theory, probabilistic
methods and ideas based on randomization are central. In other areas such
as networks and systems, probability is becoming an increasingly useful
framework for handling uncertainty and modeling the patterns of data that
occur in complex systems. This course gives an introduction to probability
as it is used in computer science theory and practice, drawing on
applications and current research developments as motivation and context.
Topics include combinatorial probability and random graphs, heavy tail
distributions, concentration inequalities, various randomized algorithms,
sampling random variables and computer simulation, and Markov chains and
their many applications, from Web search engines to models of network
protocols. The course will assume familiarity with 3D calculus and linear
algebra.
Prerequisite: 15251 and 21241 and 21259.
15381 Artificial Intelligence: Representation and Problem Solving
Spring: 9 units
This course is about the theory and practice of Artificial Intelligence.
We will study modern techniques for computers to represent taskrelevant
information and make intelligent (i.e. satisficing or optimal) decisions
towards the achievement of goals. The search and problem solving methods
are applicable throughout a large range of industrial, civil, medical,
financial, robotic, and information systems. We will investigate questions
about AI systems such as: how to represent knowledge, how to effectively
generate appropriate sequences of actions and how to search among
alternatives to find optimal or nearoptimal solutions. We will also
explore how to deal with uncertainty in the world, how to learn from
experience, and how to learn decision rules from data. We expect that by
the end of the course students will have a thorough understanding of the
algorithmic foundations of AI, how probability and AI are closely
interrelated, and how automated agents learn. We also expect students to
acquire a strong appreciation of the bigpicture aspects of developing
fully autonomous intelligent agents. Other lectures will introduce
additional aspects of AI, including natural language processing, webbased
search engines, industrial applications, autonomous robotics, and
economic/gametheoretic decision making.
Prerequisite: 15122.
15410 Operating System Design and Implementation
Fall and Spring: 12 units
Operating System Design and Implementation is a rigorous handson
introduction to the principles and practice of operating systems. The core
experience is writing a small Unixinspired OS kernel, in C with some x86
assembly language, which runs on a PC hardware simulator (and on actual PC
hardware if you wish). Work is done in twoperson teams, and "team
programming" skills (source control, modularity, documentation) are
emphasized. The size and scope of the programming assignments typically
result in students significantly developing their design, implementation,
and debugging abilities. Core concepts include the process model, virtual
memory, threads, synchronization, and deadlock; the course also surveys
higherlevel OS topics including file systems, interprocess communication,
networking, and security. Students, especially graduate students, who have
not satisfied the prerequisite at Carnegie Mellon are strongly cautioned 
to enter the class you must be able to write a storage allocator in C, use
a debugger, understand 2'scomplement arithmetic, and translate between C
and x86 assembly language. The instructor may require you to complete a
skills assessment exercise before the first week of the semester in order
to remain registered in the class. Auditing: this course is usually full,
and we generally receive many more requests to audit than we can accept.
If you wish to audit, please have your advisor contact us before the
semester begins to discuss your educational goals.
Prerequisite: 15213.
15411 Compiler Design
Fall: 12 units
This course covers the design and implementation of compiler and runtime
systems for highlevel languages, and examines the interaction between
language design, compiler design, and runtime organization. Topics
covered include syntactic and lexical analysis, handling of userdefined
types and typechecking, context analysis, code generation and
optimization, and memory management and runtime organization.
Prerequisite: 15213.
15414 Bug Catching: Automated Program Verification and Testing
Fall: 9 units
Many CS and ECE students will be developing software and hardware that
must be ultra reliable at some point in their careers. Logical errors in
such designs can be costly, even life threatening. There have already been
a number of well publicized errors like the Intel Pentium floating point
error and the Arian 5 crash. In this course we will study tools for
finding and preventing logical errors. Three types of tools will be
studied: automated theorem proving, state exploration techniques like
model checking and tools based on static program analysis. Although
students will learn the theoretical basis for such tools, the emphasis
will be on actually using them on real examples.
Prerequisite: 15122 and 15251.
15415 Database Applications
Spring: 12 units
This course covers the fundamental topics for Database Management Systems:
Database System Architectural Principles (ACID properties; data
abstraction; external, conceptual, and internal schemata; data
independence; data definition and data manipulation languages), Data
models (entityrelationship and relational data models; data structures,
integrity constraints, and operations for each data model; relational
query languages: SQL, algebra, calculus), Theory of database design
(functional dependencies; normal forms; dependency preservation;
information loss), Query Optimization (equivalence of expressions,
algebraic manipulation; optimization of selections and joins), Storage
Strategies (indices, Btrees, hashing), Query Processing (execution of
sort, join, and aggregation operators), and Transaction Processing
(recovery and concurrency control).
Prerequisite: 15210 or 15213.
15418 Parallel Computer Architecture and Programming
Spring: 12 units
The fundamental principles and engineering tradeoffs involved in designing
modern parallel computers, as well as the programming techniques to
effectively utilize these machines. Topics include naming shared data,
synchronizing threads, and the latency and bandwidth associated with
communication. Case studies on sharedmemory, messagepassing,
dataparallel and dataflow machines will be used to illustrate these
techniques and tradeoffs. Programming assignments will be performed on one
or more commercial multiprocessors, and there will be a significant course
project.
Prerequisite: 15213.
15424 Foundations of CyberPhysical Systems
Fall: 12 units
Cyberphysical systems (CPSs) combine cyber effects (computation and/or
communication) with physical effects (motion or other physical processes).
Designing algorithms to control CPSs, such as those in cars, aircraft and
robots, is challenging due to their tight coupling with physical behavior.
At the same time, it is vital that these algorithms be correct, since we
rely on CPSs for safetycritical tasks like keeping aircraft from
colliding. Students in this course will understand the core principles
behind CPSs, develop models and controls, identify safety specifications
and critical properties of CPSs, understand abstraction and system
architectures, learn how to design by invariant, reason rigorously about
CPS models, verify CPS models of appropriate scale, understand the
semantics of a CPS model and develop an intuition for operational effects.
Students will write hybrid programs (HPs), which capture relevant
dynamical aspects of CPSs in a simple programming language with a simple
semantics, allowing the programmer to refer to realvalued variables
representing real quantities and specify their dynamics as part of the HP.
Prerequisites: (15122) and (21122) and (15251 or 21241 or 18202)
15440 Distributed Systems
Fall and Spring: 12 units
The goals of this course are twofold: First, for students to gain an
understanding of the principles and techniques behind the design of
distributed systems, such as locking, concurrency, scheduling, and
communication across the network. Second, for students to gain practical
experience designing, implementing, and debugging real distributed
systems. The major themes this course will teach include scarcity,
scheduling, concurrency and concurrent programming, naming, abstraction
and modularity, imperfect communication and other types of failure,
protection from accidental and malicious harm, optimism, and the use of
instrumentation and monitoring and debugging tools in problem solving. As
the creation and management of software systems is a fundamental goal of
any undergraduate systems course, students will design, implement, and
debug large programming projects. As a consequence, competency in both the
C and Java programming languages is required.
Prerequisite: 15213.
15441 Computer Networks
Fall: 12 units
The emphasis in this course will be on the basic performance and
engineering tradeoffs in the design and implementation of computer
networks. To make the issues more concrete, the class includes several
multiweek projects requiring significant design and implementation. The
goal is for students to learn not only what computer networks are and how
they work today, but also why they are designed the way they are and how
they are likely to evolve in the future. We will draw examples primarily
from the Internet. Topics to be covered include: network architecture,
routing, congestion/flow/error control, naming and addressing,
peertopeer and the web, internetworking, and network security.
Prerequisite: 15213.
15451 Algorithm Design and Analysis
Fall and Spring: 12 units
In this coruse, we study
specific algorithms for a variety of problems, as well as general design
and analysis techniques. Specific topics include searching, sorting,
algorithms for graph problems, efficient data structures, lower bounds and
NPcompleteness. A variety of other topics may be covered at the
discretion of the instructor. These include parallel algorithms,
randomized algorithms, geometric algorithms, low level techniques for
efficient programming, cryptography, and cryptographic protocols.
Prerequisites: 15210 and 15251 and 21241.
15453 Formal Languages, Automata and Complexity
Spring: 9 units
An introduction to the fundamental ideas and models underlying computing:
finite automata, regular sets, pushdown automata, contextfree grammars,
Turing machines, undecidability, and complexity theory.
Prerequisite: 15251 or 21228.
15455 Undergraduate Complexity Theory
Fall: 9 units
Complexity theory is the study of how much of a resource (such as time,
space, parallelism, or randomness) is required to perform some of the
computations that interest us the most. In a standard algorithms course,
one concentrates on giving resource efficient methods to solve interesting
problems. In this course, we concentrate on techniques that prove or
suggest that there are no efficient methods to solve many important
problems. We will develop the theory of various complexity classes, such
as P, NP, coNP, PH, #P, PSPACE, NC, AC, L, NL, UP, RP, BPP, IP, and PCP.
We will study techniques to classify problems according to our available
taxonomy. By developing a subtle pattern of reductions between classes we
will suggest an (as yet unproven!) picture of how by using limited amounts
of various resources, we limit our computational power.
Prerequisite: 15251.
15456 Computational Geometry
Spring: 9 units
How do you sort points in space? What does it even mean? This course takes
the ideas of a traditional algorithms course, sorting, searching,
selecting, graphs, and optimization, and extends them to problems on
geometric inputs. We will cover many classical geometric constructions and
novel algorithmic methods. Some of the topics to be covered are convex
hulls, Delaunay triangulations, graph drawing, point location, geometric
medians, polytopes, configuration spaces, linear programming, and others.
This course is a natural extension to 15451, for those who want to learn
about algorithmic problems in higher dimensions.
Prerequisite: 15451.
15462 Computer Graphics
Fall and Spring: 12 units
This course provides a comprehensive introduction to computer graphics
modeling, animation, and rendering. Topics covered include basic image
processing, geometric transformations, geometric modeling of curves and
surfaces, animation, 3D viewing, visibility algorithms, shading, and ray
tracing.
Prerequisite: (21259 and 15213 and 21240) or (21259 and 15213 and
21241) or (18202 and 18213)
15591 Independent Study in Computer Science
Fall and Spring: 312 units
Specially selected projects and readings in computer science under
supervision of a faculty member in SCS. Application required.
Poster presentation is generally required to present completed work.
More information is available on the
Undergraduate Research
page.
15599 Undergraduate Thesis Research
Fall and Spring: 36 units total over 23 semesters (18
+ 18 or 9 + 18 + 9)
Formal research leading to an original result in computer science
under the supervision of an SCS faculty member. Requires a written
thesis and final presentation at the Meeting of the Minds campus
symposium. Thesis prospectus is required and must be approved before
student can start research.
More information is available on the
Undergraduate Research
page.
COMPUTATIONAL BIOLOGY
02510 Computational Genomics
Spring: 12 units
Dramatic advances in experimental technology and computational analysis
are fundamentally transforming the basic nature and goal of biological
research. The emergence of new frontiers in biology, such as evolutionary
genomics and systems biology is demanding new methodologies that can
confront quantitative issues of substantial computational and mathematical
sophistication. In this course we will discuss classical approaches and
latest methodological advances in the context of the following biological
problems: 1) Computational genomics, focusing on gene finding, motifs
detection and sequence evolution.2) Analysis of high throughput biological
data, such as gene expression data, focusing on issues ranging from data
acquisition to pattern recognition and classification. 3) Molecular and
regulatory evolution, focusing on phylogene tic inference and regulatory
network evolution, and 4) Systems biology, concerning how to combine
sequence, expression and other biological data sources to infer the
structure and function of different systems in the cell. From the
computational side this course focuses on modern machine learning
methodologies for computational problems in molecular biology and
genetics, including probabilistic modeling, inference and learning
algorithms, pattern recognition, data integration, time series analysis,
active learning, etc.
HUMAN COMPUTER INTERACTION
05391 Designing Human Centered Software
Spring: 12 units
Why are things so hard to use these days? Why doesn’t this thing I just
bought work? Why is this web site so hard to use? These are frustrations
that we have all faced from systems not designed with people in mind. The
question this course will focus on is: how can we design humancentered
systems that people find useful and usable? This course is an introduction
to designing, prototyping, and evaluating user interfaces. If you take
only one course in HumanComputer Interaction, this is the course for you.
This class is open to all undergrads and grad students, with either
technical or nontechnical backgrounds. We will cover theory as well as
practical application of ideas from HumanComputer Interaction. Course
work includes lectures, class discussion, homework, class presentations,
and group project.
MACHINE LEARNING
10601 Introduction to Machine Learning
Fall and Spring: 12 units
Machine Learning (ML) attempts to design programs that automatically
improve their performance through experience. This includes learning many
types of tasks based on many types of experience, e.g. spotting highrisk
medical patients, recognizing speech, classifying text documents,
detecting credit card fraud, or driving autonomous vehicles. 10601 covers
all or most of: concept learning, version spaces, decision trees, neural
networks, computational learning theory, active learning, estimation & the
biasvariance tradeoff, hypothesis testing, Bayesian learning, the MDL
principle, the Gibbs classifier, Naive Bayes, Bayes Nets & Graphical
Models, the EM algorithm, Hidden Markov Models, KNearestNeighbors and
nonparametric learning, reinforcement learning, genetic algorithms,
bagging, boosting and discriminative training. Grading will be based on
weekly or biweekly assignments (written and/or programming), a midterm, a
final exam, and possibly a project (details may vary depending on the
section). 10601 is recommended for CS Seniors & Juniors, quantitative
Masters students, & nonMLD PhD students.
Prerequisites: 15122 and (15151 or 21127) and college level
probability & statistics course.
LANGUAGE TECNOLOGIES
11411 Natural Language Processing
Spring: 12 units
This course will introduce students to the highly interdisciplinary area
of Artificial Intelligence known alternately as Natural Language
Processing (NLP) and Computational Linguistics. The course aims to cover
the techniques used today in software that does useful things with text in
human languages like English and Chinese. Applications of NLP include
automatic translation between languages, extraction and summarization of
information in documents, question answering and dialog systems, and
conversational agents. This course will focus on core representations and
algorithms, with some time spent on realworld applications. Because
modern NLP relies so heavily on Machine Learning, we'll cover the basics
of discrete classification and probabilistic modeling as we go. Good
computational linguists also know about Linguistics, so topics in
linguistics (phonology, morphology, and syntax) will be covered when
fitting. From a software engineering perspective, there will be an
emphasis on rapid prototyping, a useful skill in many other areas of
Computer Science. In particular, we will introduce some highlevel
languages (e.g., regular expressions and Dyna) and some scripting
languages (e.g., Python and Perl) that can greatly simplify prototype
implementation.
Prerequisite: 15122.
ROBOTICS
16384 Robot Kinematics and Dynamics
Fall: 12 units
Foundations and principles of robotic kinematics. Topics include
transformations, forward kinematics, inverse kinematics, differential
kinematics (Jacobians), manipulability, and basic equations of motion.
Course also include programming on robot arms.
Prerequisite: 15122 or 16311 or 18202 or 21241 or 24311.
16385 Computer Vision
Spring: 9 units
Basic concepts in machine vision, including sensing and perception, 2D
image analysis, pattern classification, physicsbased vision, stereo and
motion, and object recognition.
Prerequisites: (15122 and 21241 and 21259) or (15122 and 18202).
MATHEMATICS
21120 Differential and Integral Calculus
Fall and Spring: 10 units
Functions, limits, derivatives, logarithmic, exponential, and
trigonometric functions, inverse functions; L'Hospital's Rule, curve
sketching, Mean Value Theorem, related rates, linear and quadratic
approximations, maximumminimum problems, inverse functions, definite and
indefinite integrals, and hyperbolic functions; applications of
integration, integration by substitution and by parts.
21122 Integration and Approximation
Fall and Spring: 10 units
Integration by trigonometric substitution and partial fractions;
arclength; improper integrals; Simpson's and Trapezoidal Rules for
numerical integration; separable differential equations, Newton's method,
Euler's method, Taylor's Theorem including a discussion of the remainder,
sequences, series, power series. Parametric curves, polar coordinates,
vectors, dot product.
Prerequisite: 21120.
21127 Concepts of Mathematics
Fall and Spring: 10 units
This course introduces the basic concepts, ideas and tools involved in
doing mathematics. As such, its main focus is on presenting informal
logic, and the methods of mathematical proof. These subjects are closely
related to the application of mathematics in many areas, particularly
computer science. Topics discussed include a basic introduction to
elementary number theory, induction, the algebra of sets, relations,
equivalence relations, congruences, partitions, and functions, including
injections, surjections, and bijections.
21241 Matrices and Linear Transformations
Fall and Spring: 10 units
A first course in linear algebra intended for scientists, engineers,
mathematicians and computer scientists. Students will be required to write
some straightforward proofs. Topics to be covered: complex numbers, real
and complex vectors and matrices, rowspace and columnspace of a matrix,
rank and nullity, solving linear systems by row reduction of a matrix,
inverse matrices and determinants, change of basis, linear
transformations, inner product of vectors, orthonormal bases and the
GramSchmidt process, eigenvectors and eigenvalues, diagonalization of a
matrix, symmetric and orthogonal matrices. 21127 is strongly recommended.
21242 Matrix Theory
Fall and Spring: 10 units
An honors version of 21241 (Matrix Algebra and Linear Transformations)
for students of greater aptitude and motivation. More emphasis will be
placed on writing proofs. Topics to be covered: complex numbers, real and
complex vectors and matrices, rowspace and columnspace of a matrix, rank
and nullity, solving linear systems by row reduction of a matrix, inverse
matrices and determinants, change of basis, linear transformations, inner
product of vectors, orthonormal bases and the GramSchmidt process,
eigenvectors and eigenvalues, diagonalization of a matrix, symmetric and
orthogonal matrices, hermitian and unitary matrices, quadratic forms.
21341 Linear Algebra
Fall and Spring: 9 units
A mathematically rigorous treatment of Linear Algebra over an arbitrary
field. Topics studied will include abstract vector spaces, linear
transformations, determinants, eigenvalues, eigenvectors, inner products,
invariant subspaces, canonical forms, the spectral theorem and the
singular value decomposition. 21373 recommended.
Prerequisite: 21241 or 21242.
21259 Calculus in Three Dimensions
Fall and Spring: 9 units
Vectors, lines, planes, quadratic surfaces, polar, cylindrical and
spherical coordinates, partial derivatives, directional derivatives,
gradient, divergence, curl, chain rule, maximumminimum problems, multiple
integrals, parametric surfaces and curves, line integrals, surface
integrals, GreenGauss theorems.
Prerequisite: 21122.
21300 Basic Logic
Fall: 9 units
Propositional and predicate logic: Syntax, proof theory and semantics up
to completeness theorem, Lowenheim Skolem theorems, and applications of
the compactness theorem.
Prerequisite: 15251 or 21228 or 21373.
21301 Combinatorics
Fall and Spring: 9 units
A major part of the course concentrates on algebraic methods, which are
relevant in the study of error correcting codes, and other areas. Topics
covered in depth include permutations and combinations, generating
functions, recurrence relations, the principle of inclusion and exclusion,
and the Fibonacci sequence and the harmonic series. Additional topics may
include existence proofs, partitions, finite calculus, generating
combinatorial objects, Polya theory, codes, probabilistic methods.
Prerequisites: 21122 and (15251 or 21228).
21325 Probability
Fall: 9 units
This course focuses on the understanding of basic concepts in probability
theory and illustrates how these concepts can be applied to develop and
analyze a variety of models arising in computational biology, finance,
engineering and computer science. The firm grounding in the fundamentals
is aimed at providing students the flexibility to build and analyze models
from diverse applications as well as preparing the interested student for
advanced work in these areas. The course will cover core concepts such as
probability spaces, random variables, random vectors, multivariate
densities, distributions, expectations, sampling and simulation;
independence, conditioning, conditional distributions and expectations;
limit theorems such as the strong law of large numbers and the central
limit theorem; as well as additional topics such as large deviations,
random walks and Markov chains, as time permits.
Prerequisites: 21259 or 21268 or 21269.
21484 Graph Theory
Spring: 9 units
Graph theory uses basic concepts to approach a diversity of problems and
nontrivial applications in operations research, computer science and other
disciplines. It is one of the very few mathematical areas where one is
always close to interesting unsolved problems. Topics include graphs and
subgraphs, trees, connectivity, Euler tours and Hamilton cycles,
matchings, graph colorings, planar graphs and Euler's Formula, directed
graphs, network flows, counting arguments, and graph algorithms.
Prerequisites: (15251 or 21228) and (21241 or 21242).
STATISTICS
36217 Probability Theory and Random Processes
Fall and Spring: 9 units
This course provides an introduction to probability theory. It is designed
for students in electrical and computer engineering. Topics include
elementary probability theory, conditional probability and independence,
random variables, distribution functions, joint and conditional
distributions, limit theorems, and an introduction to random processes.
Some elementary ideas in spectral analysis and information theory will be
given. A grade of C or better is required in order to use this course as a
prerequisite for 36226 and 36410. Not open to students who have
received credit for 36225, or 36625.
Prerequisite: 21112 or 21122 or 21123 or 21256 or 21259.
36225 Introduction to Probability Theory
Fall: 9 units
This course is the first half of a year long course which provides an
introduction to probability and mathematical statistics for students in
economics, mathematics and statistics. The use of probability theory is
illustrated with examples drawn from engineering, the sciences, and
management. Topics include elementary probability theory, conditional
probability and independence, random variables, distribution functions,
joint and conditional distributions, law of large numbers, and the central
limit theorem. A grade of C or better is required in order to advance to
36226 and 36410. Not open to students who have received credit for
36217 or 36625.
PHILOSOPHY
80310 Formal Logic
Fall: 9 units
Among the most significant developments in modern logic is the formal
analysis of the notions of provability and logical consequence for the
logic of relations and quantification, known as firstorder logic. These
notions are related by the soundness and completeness theorems: a logical
formula is provable if and only if it is true under every interpretation.
This course provides a formal specification of the syntax and semantics of
firstorder logic and then proves the soundness and completeness theorems.
Other topics may include: basic model theory, intuitionistic, modal, and
higherorder logics.
Prerequisite: 15251 or 80210 or 80211 or 80212.
80311 Undecidability and Incompleteness
Spring: 9 units
This course focuses on two central problems of mathematical logic: the
undecidability of predicate logic (established by Church and Turing) and
the incompleteness of formal theories (discovered by Gödel for theories
that contain a modicum of set or number theory). The mathematical
solutions of these problems involve a rigorous concept of computability or
calculability that turned out to be fundamental for computer science, but
also cognitive science. We first discuss predicate logic and systematic
ways of constructing proofs; that is followed by the formal development of
elementary set theory. The concept of Turing machine computation is
introduced and shown to be equivalent to the concept of recursive
function. That provides the mathematical, methodologically adequate tools
for establishing the results mentioned above. The mathematical and
computational notions and results are among the most significant
contributions of logic, not just to the solution of internal logical
questions and to the foundations of computer science, but also to (the
beginnings of) a deeper understanding of the human mind and mental
processes. In addition to the mathematical developments, we will discuss
historical and philosophical aspects of the subject.
Prerequisite: 15251 or 21300 or 80210 or 80211 or 80310.
Maintained by Catharine
Fichtner, CS Undergraduate Program Administrator.
