The courses listed below are relevant for computer science majors as required courses or constrained electives. See the Undergraduate Catalog for information about additional SCS courses including available electives.

**COMPUTER SCIENCE**

15-050 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.

15-075
Computer Science Co-Op

Fall and Spring

This course is meant for CS undergraduate students with a full-time internship that encompasses a summer and a contiguous semester, either Spring-Summer or Summer-Fall who wish to have this recorded on their academic transcript. Units posted for this course do not count toward any requirement for the CS undergraduate degree including free elective units. This course is not available to international students; consult with the Office for International Education for more information.

15-090
Computer Science Practicum

Summer: 3 units

This course is for Computer Science students who wish to have an internship experience as part of their curriculum. Students are required to write a one-page summary statement prior to registration that explains how their internship connects with their CS curriculum, specifically on how it uses material they have learned as well as prepares them for future courses. Near the end of the internship, students will be required to submit a reflection paper that describes the work they did in more detail, including lessons learned about the work experience and how they utilized their CS education to work effectively. International students should consult with the Office of International Education for appropriate paperwork and additional requirements before registration. Units earned count toward the total required units necessary for degree completion; students should speak with an academic advisor for details. This course may be taken at most 3 times for a total of 9 units maximum. Students normally register for this course for use during the summer semester.

15-112 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
top-down 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 web-based applications. This
course assumes no prior programming experience. Even so, it is a
fast-paced and rigorous preparation for 15-122. Students seeking a more
gentle introduction to computer science should consider first taking
15-110. *NOTE: students must achieve a C or better in order to use this
course to satisfy the pre-requisite for any subsequent Computer Science
course.*

15-122 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 high-level 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
15-213 and 15-210. *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: 15-112. Corequisite: 21-127 or 15-151.

15-128 Freshman Immigration Course (Pittsburgh)

Fall: 1 unit

The Freshman Immigration Course is taken by first-semester 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.

15-129 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 subject-oriented
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
subject-specific search engines; discover valuable resources to help keep
you up-to-date in this fast-changing environment.

15-131 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 so-called "tools of the trade." This
course is intended to help you learn what you need to know in a friendly,
low-stress, high-support way. We will discuss UNIX, LaTeX, debugging and
many other essential tools. Laptop required. (Laptops will be available
for those without their own laptops.)

15-150 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 inputs---that is, as a function. But instead of being
confined to real- or complex-valued 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 pre-requisite for any subsequent Computer Science
course.*
Prerequisites: (21-127 or 15-151) and (15-112).

15-151 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 pre-requisite for any subsequent Computer Science course.
*

15-210 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 15-122 and
15-150 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.

15-213 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 systems-level issues is
required. Topics covered include: machine-level 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.

15-214 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 multi-player game systems and frameworks for graphical user
interaction.
Prerequisites: (15-121 or 15-122) and (21-127 or 15-151).

15-221 Technical Communications for Computer Scientists (Doha, Qatar)

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 multi-level 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 faculty-supervised research, including SURG projects prior
to enrollment.
Prerequisite: 76-101.

15-251 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.

15-300 Research and Innovation in Computer Science

Fall: 9 units

This Fall course is the first part of a two-course sequence that is designed to help prepare students to invent the future state-of-the-art in the field of computer science. Course topics will include the following: an overview of important things to know about how research and innovation works in the field of computer science; a survey of the current cutting- edge of computer science research, both here at Carnegie Mellon and elsewhere; critical thinking skills when reading research publications that disagree with each other; strategies for coping with open-ended problems; and technical communication skills for computer scientists. Students will also match up with a faculty mentor for a potential Technology Innovation Project (to be performed in the Spring), put together a detailed plan of attack for that project, and start to get up to speed (including background reading, etc.). This course can be used to satisfy the Technical Communications requirement for the CS major.
Prerequisites: 15-210. 15-213. 15-251 and 76-101.

15-312 Foundations of Programming Languages

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: 15-210 and 15-251.

15-313 Foundations of Software Engineering

Fall: 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: 15-214.

15-317 Constructive Logic

Fall: 9 units

This multidisciplinary junior-level 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: 15-150.

15-322 Introduction to Computer Music

Fall: 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 high-level
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
sound-processing technique.
Prerequisite: 15-112.

15-323 Computer Music Systems and Information Processing

Spring: 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 run-time
systems for event scheduling, tempo control, and interactive processing.
The MIDI protocol is used to capture real-time performance information and
to generate sound. The course will also cover non-real-time processing of
music data, including Markov models, style recognition, computer
accompaniment, query-by-humming, and algorithmic composition. This course
is independent of, and complementary to 15-322, Introduction to Computer
Music, which focuses on sound synthesis and signal processing.
Prerequisite: 15-122.

15-354 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: 15-251 or 21-228.

15-355 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 hands-on 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: 15-251.

15-359 Probability and Computing

Once every three semesters: 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 3-D calculus and linear
algebra.
Prerequisite: 15-251 and 21-241 and 21-259.

15-381 Artificial Intelligence: Representation and Problem Solving

Fall: 9 units

This course is about the theory and practice of Artificial Intelligence.
We will study modern techniques for computers to represent task-relevant
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 near-optimal 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 big-picture aspects of developing
fully autonomous intelligent agents. Other lectures will introduce
additional aspects of AI, including natural language processing, web-based
search engines, industrial applications, autonomous robotics, and
economic/game-theoretic decision making.
Prerequisite: 15-122.

15-400 Research Practicum in Computer Science

Spring: 12 units

This Spring course is the second part of a two-course sequence that is designed to help prepare students to invent the future state-of-the-art in the field of computer science. Building directly upon 15-300 (the prerequisite for this course), students will conduct a semester-long independent research project, under the guidance of both the course staff and a faculty project mentor. The course does not meet for lecture or recitations. Instead, the students will spend their time working on their research projects, and will also meet with course staff on a bi-weekly basis to discuss their progress. Students will prepare a written report and a poster presentation at the end of the semester to describe what they have accomplished.
Prerequisite: 15-300.

15-410 Operating System Design and Implementation

Fall and Spring: 12 units

Operating System Design and Implementation is a rigorous hands-on
introduction to the principles and practice of operating systems. The core
experience is writing a small Unix-inspired 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 two-person 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
higher-level 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's-complement 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: 15-213.

15-411 Compiler Design

Fall: 12 units

This course covers the design and implementation of compiler and run-time
systems for high-level languages, and examines the interaction between
language design, compiler design, and run-time organization. Topics
covered include syntactic and lexical analysis, handling of user-defined
types and type-checking, context analysis, code generation and
optimization, and memory management and run-time organization.
Prerequisite: 15-213.

15-414 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: 15-122 and 15-251.

15-415 Database Applications

Fall: 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 (entity-relationship 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, B-trees, hashing), Query Processing (execution of
sort, join, and aggregation operators), and Transaction Processing
(recovery and concurrency control).
Prerequisite: 15-210 or 15-213.

15-418 Parallel Computer Architecture and Programming

Fall and 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 shared-memory, message-passing,
data-parallel 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: 15-213.

15-424 Foundations of Cyber-Physical Systems

Spring: 12 units

Cyber-physical 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 safety-critical 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 real-valued variables
representing real quantities and specify their dynamics as part of the HP.
Prerequisites: (15-122) and (21-122) and (15-251 or 21-241 or 18-202)

15-440 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: 15-213.

15-441 Computer Networks

Fall: 12 units

The emphasis in this course will be on the basic performance and
engineering trade-offs in the design and implementation of computer
networks. To make the issues more concrete, the class includes several
multi-week 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,
peer-to-peer and the web, internetworking, and network security.
Prerequisite: 15-213.

15-451 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
NP-completeness. 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: 15-210 and 15-251 and 21-241.

15-453 Formal Languages, Automata and Complexity

Spring: 9 units

An introduction to the fundamental ideas and models underlying computing:
finite automata, regular sets, pushdown automata, context-free grammars,
Turing machines, undecidability, and complexity theory.
Prerequisite: 15-251 or 21-228.

15-455 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, co-NP, 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: 15-251.

15-456 Computational Geometry

Spring (every other year): 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 15-451, for those who want to learn
about algorithmic problems in higher dimensions.
Prerequisite: 15-451.

15-462 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, 3-D viewing, visibility algorithms, shading, and ray
tracing.
Prerequisite: (21-259 and 15-213 and 21-240) or (21-259 and 15-213 and
21-241) or (18-202 and 18-213)

15-591 Independent Study in Computer Science

Fall and Spring: 3-12 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.

15-599 Undergraduate Thesis Research

Fall and Spring: 36 units total over 2 semesters (18
+ 18)

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**

02-510 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**

05-391 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 human-centered
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 Human-Computer Interaction, this is the course for you.
This class is open to all undergrads and grad students, with either
technical or non-technical backgrounds. We will cover theory as well as
practical application of ideas from Human-Computer Interaction. Course
work includes lectures, class discussion, homework, class presentations,
and group project.

**MACHINE LEARNING**

10-401 Introduction to Machine Learning

Fall and Spring: 12 units

Machine learning is subfield of computer science with the goal of exploring, studying, and developing learning systems, methods, and algorithms that can improve their performance with learning from data. This course is designed to give undergraduate students a one-semester-long introduction to the main principles, algorithms, and applications of machine learning. Topics. The topics of this course will be in part parallel with those covered in the graduate machine learning courses (10-715, 10-701, 10-601), but with a greater emphasis on applications and case studies in machine learning. After completing the course, students will be able to: *select and apply an appropriate supervised learning algorithm for classification problems (e.g., naive Bayes, perceptron, support vector machine, logistic regression). *select and apply an appropriate supervised learning algorithm for regression problems (e.g., linear regression, ridge regression). *recognize different types of unsupervised learning problems, and select and apply appropriate algorithms (e.g., clustering, linear and nonlinear dimensionality reduction). *work with probabilities (Bayes rule, conditioning, expectations, independence), linear algebra (vector and matrix operations, eigenvectors, SVD), and calculus (gradients, Jacobians) to derive machine learning methods such as linear regression, naive Bayes, and principal components analysis. *understand machine learning principles such as model selection, overfitting, and underfitting, and techniques such as cross-validation and regularization. *implement machine learning algorithms such as logistic regression via stochastic gradient descent, linear regression (using a linear algebra toolbox), perceptron, or k-means clustering. *run appropriate supervised and unsupervised learning algorithms on real and synthetic data sets and interpret the results.
Prerequisites: 15-122 and (15-151 or 21-127).
Corequisite: 15-359 or 36-217 or 36-225 or 21-325.

**LANGUAGE TECNOLOGIES**

11-411 Natural Language Processing

Fall and 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 real-world 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 high-level
languages (e.g., regular expressions and Dyna) and some scripting
languages (e.g., Python and Perl) that can greatly simplify prototype
implementation.
Prerequisite: 15-122.

**ROBOTICS**

16-384 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: 15-122 or 16-311 or 18-202 or 21-241 or 24-311.

16-385 Computer Vision

Spring: 9 units

Basic concepts in machine vision, including sensing and perception, 2D
image analysis, pattern classification, physics-based vision, stereo and
motion, and object recognition.
Prerequisites: (15-122 and 21-241 and 21-259) or (15-122 and 18-202).

**MATHEMATICS**

21-120 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, maximum-minimum problems, inverse functions, definite and
indefinite integrals, and hyperbolic functions; applications of
integration, integration by substitution and by parts.

21-122 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: 21-120.

21-127 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.

21-241 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
Gram-Schmidt process, eigenvectors and eigenvalues, diagonalization of a
matrix, symmetric and orthogonal matrices. 21-127 is strongly recommended.

21-242 Matrix Theory

Fall and Spring: 10 units

An honors version of 21-241 (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 Gram-Schmidt process,
eigenvectors and eigenvalues, diagonalization of a matrix, symmetric and
orthogonal matrices, hermitian and unitary matrices, quadratic forms.

21-341 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. 21-373 recommended.
Prerequisite: 21-241 or 21-242.

21-259 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, maximum-minimum problems, multiple
integrals, parametric surfaces and curves, line integrals, surface
integrals, Green-Gauss theorems.
Prerequisite: 21-122.

21-300 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: 15-251 or 21-228 or 21-373.

21-301 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: 21-122 and (15-251 or 21-228).

21-325 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: 21-259 or 21-268 or 21-269.

21-484 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: (15-251 or 21-228) and (21-241 or 21-242).

**STATISTICS**

36-217 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
pre-requisite for 36-226 and 36-410. Not open to students who have
received credit for 36-225, or 36-625.
Prerequisite: 21-112 or 21-122 or 21-123 or 21-256 or 21-259.

36-225 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
36-226 and 36-410. Not open to students who have received credit for
36-217 or 36-625.

**PHILOSOPHY**

80-310 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 first-order 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
first-order logic and then proves the soundness and completeness theorems.
Other topics may include: basic model theory, intuitionistic, modal, and
higher-order logics.
Prerequisite: 15-251 or 80-210 or 80-211 or 80-212.

80-311 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: 15-251 or 21-300 or 80-210 or 80-211 or 80-310.

Maintained by Catharine
Fichtner, CS Undergraduate Program Administrator.