CPSC 421a Compilers and Interpreters Zhong Shao
MW 1:00-2:15
Compiler organization and implementation: lexical analysis, formal syntax
specification, parsing techniques, execution environment, storage
management, code generation and optimization, procedure linkage, and
address binding. The effect of language-design decisions on compiler
construction.
After Computer Science 323a.
CPSC 422b Operating Systems Zhong Shao
(Not taught in 2008-2009)
The design and implementation of operating systems. Topics include
synchronization, deadlock, process management, storage management, file
systems, security, protection, and networking.
After Computer Science 323a.
CPSC 424b Parallel Programming Techniques David Gelernter
(Not taught in 2008-2009)
Software structures, architectures, and algorithms for parallel and
distributed applications, focusing on coordination frameworks for
asynchronous concurrency (that is, on the code that creates and manages
multiple processes and performs the interprocess communication necessary
to create integrated ensembles). Coordination languages and
program-development environments. The fast-changing WAN-software
picture. Parallel and distributed programming exercises on LANs.
After Computer Science 323a.
Not taught every year.
CPSC 425b Theory of Distributed Systems James Aspnes
(Not taught in 2008-2009)
Models of asynchronous distributed computing systems. Fundamental concepts
of concurrency and synchronization, communication, reliability, topological
and geometric constraints, time and space complexity, and distributed
algorithms.
After Computer Science 323a and 365b.
Taught in alternate years.
CPSC 428b Language-Based Security Zhong Shao
TTh 2:30-3:45
Basic design and implementation of language-based approaches for
increasing the security and reliability of systems software. Topics include
proof-carrying code; certifying compilation; typed assembly languages;
runtime checking and monitoring; high-confidence embedded systems and drivers;
and language support for verification of safety and liveness properties.
After Computer Science 202a and 323a and
Mathematics 222a or b, or equivalent.
Not taught every year.
CPSC 430a Formal Semantics Paul Hudak
(Not taught in 2008-2009)
Introduction to formal approaches to programming language design and
implementation. Topics include the lambda-calculus, type theory, denotational
semantics, type-directed compilation, higher-order modules, and application of
formal methods to systems software and Internet programming.
After Computer Science 202a and 323a.
Not taught every year.
CPSC 431a Computer Music--Algorithmic and Heuristic Composition Paul Hudak
MW 2:30-3:45
Beginning with high-level representations of music, various
deterministic and stochastic algorithms and heuristics are
studied for synthesizing music. Similarly, with suitable
encodings of harmonic structure and aesthetics, automated
methods for analyzing music are studied. Many of the ideas
have connections to conventional music theory, but many do not,
instead drawing their inspiration from mathematics,
computation, and nature (such as fractals, L-systems, and
stochastic methods). A key idea underlying the course is the
use of a high-level functional language to express the
theoretical concepts in a practical manner. Regular
programming assignments lead toward a final project that is a
software realization of a student-designed concept.
After Computer Science 202a and 223b.
Assumes ability to read music.
Taught in alternate years.
CPSC 432a Computer Music--Sound Representation and Synthesis Paul Hudak
(Not taught in 2008-2009)
Beginning with low-level representations of sound,
various methods for synthesizing musical sounds are
studied, including additive synthesis, subtractive
synthesis, frequency modulation, granular synthesis,
and physical modeling. The goal is to both simulate as
accurately as possible existing musical instruments,
and to create new sounds and musical soundscapes.
Scales and tuning systems are also studied, as is basic
acoustic signal processing (filtering, reverb, sound
effects, etc). A key idea underlying the course is the
use of a high-level functional language to express the
theoretical concepts in a practical manner. Regular
programming assignments lead toward a final project
that is a software realization of a student-designed
concept.
After Computer Science 202a and 223b.
Assumes ability to read music.
Taught in alternate years.
CPSC 433b Computer Networks Yang Richard Yang
(Not taught in 2008-2009)
An introduction to the design, implementation, analysis, and evaluation
of computer networks and their protocols.
Topics include layered network architectures, applications, transport,
congestion, routing, data link protocols, local area networks,
performance analysis, multimedia networking, network security, and
network management.
Emphasis on protocols used in the Internet.
After Computer Science 323a.
Taught in alternate years.
CPSC 434b Mobile Computing and Wireless Networking Yang Richard Yang
TTh 1:00-2:30
An introduction to the principles of mobile computing and its enabling
technologies. Topics include principles of mobile computing; wireless
systems; information management; location-independent/dependent
computing models; disconnected and weakly connected operation models;
human-computer interactions; mobile applications and
services; security; power management; and sensor networks.
After Computer Science 202a and 323a.
Taught in alternate years.
CPSC 436b/EENG 460b Networked Embedded Systems and Sensor Networks Andreas Savvides
TTh 1:00-2:15
Introduction to the fundamental concepts of networked embedded systems
and wireless sensor networks, presenting a cross-disciplinary approach
to the design and implementation of smart wireless embedded systems. Topics
include embedded systems programming concepts; low-power and power-aware
design; radio technologies; communication protocols for ubiquitous computing
systems; and mathematical foundations of sensor behavior. Laboratory work
includes programming assignments on low-power wireless devices.
After Computer Science 223b or with equivalent programming
experience in a high-level language.
Open to seniors in Computer Science or Electrical Engineering only.
CPSC 437a Introduction to Database Systems Avi Silberschatz
TTh 2:30-3:45
An introduction to database systems. Data modeling. The relational model
and the SQL query language. Relational database design, integrity
constraints, functional dependencies, and normal forms. Object-oriented
databases. Database data structures: files, B-trees, hash indexes.
After Computer Science 202a and 223b.
CPSC 438b Database System Implementation and Architectures Daniel Abadi
MW 2:30-3:45
A study of systems programming techniques, with a focus on
database systems. Half the course is spent studying the design
of a traditional DBMS, supplemented by a hands-on exercise where
students build various components (e.g., a catalog-manager, a
buffer-manager, and a query execution engine) of a DBMS
prototype. The other half is spent on non-traditional
architectures (parallel databases, data warehouses, stream
databases, Web databases).
After Computer Science 202a and 223b.
CPSC 440b Numerical Computation I Vladimir Rokhlin
MW 2:30-3:45
Algorithms for numerical problems in the physical, biological, and social
sciences: solution of linear and nonlinear systems of equations,
interpolation and approximation of functions, numerical differentiation and
integration, optimization.
After Computer Science 112a or b or an equivalent
introductory programming course; Mathematics 120a or b;
and Mathematics 222a or b or 225a or b
or Computer Science 202a.
CPSC 445b Introduction to Data Mining Martin Schultz
TTh 2:30-3:45
A study of algorithms and systems that allow computers to find
patterns and regularities in databases, to perform prediction and forecasting,
and to improve their performance generally through interaction with data.
After Computer Science 202a and 223b and
Mathematics 222a or b, or equivalents.
CPSC 452b/MB&B 452b
/MCDB 452b Genomics and Bioinformatics Mark Gerstein, Michael Snyder, and Dieter Söll
MW 1:00-2:15
Genomics describes the determination of the nucleotide sequence as
well as many further analyses used to discover functional and
structural gene information about all the genes of an organism. Topics
include the methods and results of analysis on a genome-wide scale as
well as a discussion of the implications of this research.
Bioinformatics describes the computational analysis of gene sequences
and protein structures on a large scale. Topics include sequence
alignment, biological database design, geometric analysis of protein
structure, and macromolecular simulation.
After MB&B 301b and MATH 115a or b, or with permission of the instructor.
CPSC 455a/ECON 425a Economics and Computation Joan Feigenbaum and Dirk Bergeman
TTh 2:30-3:45
A mathematically rigorous investigation of the interplay of economic
theory and computer science with an emphasis on the relationship of
incentive-compatibility and algorithmic efficiency. Particular attention
will be paid to the formulation and solution of mechanism-design problems
that are relevant to data networking and Internet-based commerce.
Some familiarity with basic algorithmics and basic microeconomic
theory will be helpful.
Not taught every year.
CPSC 462a/AMTH 462a Graphs and Networks Daniel Spielman
(Not taught in 2008-2009)
A mathematical examination of graphs and their applications in the
sciences. Families of graphs include social networks, small-world
graphs, Internet graphs, planar graphs, well-shaped meshes, power-law
graphs, and classic random graphs. Phenomena include connectivity,
clustering, communication, ranking, and iterative processes.
Prerequisites: Linear algebra and discrete mathematics; a course in
probability is recommended.
CPSC 463b Introduction to Machine Learning Dana Angluin
MWF 11:35-12:25
Paradigms and algorithms for learning classification rules and more
complex behaviors from examples and other kinds of data. Topics may
include version spaces, decision trees, artificial neural networks,
Bayesian networks, instance-based learning, genetic algorithms,
reinforcement learning, inductive logic programming, the MDL
principle, the PAC model, VC dimension, sample bounds, boosting,
support vector machines, queries, grammatical inference, and
transductive and inductive inference.
After Computer Science 202a and 223b,
or with permission of the instructor. Computer Science 365b
is recommended.
Taught in alternate years.
CPSC 465a Topics in Algorithms Maxim Sviridenko
(Not taught in 2008-2009)
Introduction to the fundamental tools used in approximation algorithms:
linear, convex, and semi-definite programming; dynamic programming; and
geometric tools. Recent progress in the design of approximation
algorithms for graph problems, combinatorial problems, and other NP-hard
optimization problems. Results on the hardness of approximation based on
probabilistically checkable proofs.
After Computer Science 365b.
Taught in alternate years.
CPSC 467a Cryptography and Computer Security Michael Fischer
MW 2:30-3:45
A survey of such private and public key cryptographic techniques as
DES, RSA,
and zero-knowledge proofs, and their application to problems of maintaining
privacy and security in computer networks. Focus on technology,
with consideration of such societal issues as balancing
individual privacy concerns against the needs of law enforcement,
vulnerability of societal institutions to electronic attack, export
regulations and international competitiveness, and development of secure
information systems.
Some programming may be required. After Computer Science 202a
and 223b.
CPSC 468a Computational Complexity Joan Feigenbaum
TTh 1:00-2:15
Introduction to the theory of computational complexity. Basic complexity
classes, including Polynomial Time, Nondeterministic Polynomial Time,
Probabilistic Polynomial Time, Polynomial Space, Logarithmic Space, and
Nondeterminstic Logarithmic Space. The roles of reductions, completeness,
randomness, and interaction in the formal study of computation.
After Computer Science 365b or with permission of the instructor.
CPSC 469b Randomized Algorithms James Aspnes
MW 1:00-2:15
Beginning with an introduction to tools from probability theory including
some inequalities like Chernoff bounds, the course will cover randomized
algorithms from several areas: graph algorithms, algorithms in algebra,
approximate counting, probabilistically checkable proofs, and matrix
algorithms.
After Computer Science 365b; a solid background in
probability is desirable.
Taught in alternate years.
CPSC 470a Artificial Intelligence Drew McDermott
MWF 10:30-11:20
An introduction to artificial intelligence research, focusing on reasoning
and perception. Topics include knowledge representation, predicate calculus,
temporal reasoning, vision, robotics, planning, and learning.
After Computer Science 201a or b and 202a.
CPSC 473b Intelligent Robotics Brian Scassellati
MWF 10:30-11:20
An introduction to the construction of intelligent, autonomous
systems. Sensory-motor coordination and task-based perception.
Implementation techniques for behavior selection and arbitration,
including behavior-based design, evolutionary design, dynamical
systems, and hybrid deliberative-reactive systems. Situated
learning and adaptive behavior.
After Computer Science 202a and 223b.
CPSC 475b/EENG 475b Computational Vision and Biological Perception Steven Zucker
TTh 1:00-2:15
An overview of computational vision with a biological emphasis.
Suitable as an introduction to biological perception for
computer science and engineering students, as well as an introduction to
computational vision for mathematics, psychology, and physiology students.
After Computer Science 112a or b and
Mathematics 120a or b, or with
permission of the instructor.
CPSC 477a Neural Networks for Computing Willard Miranker
TTh 11:35-12:50
Artificial neural networks as a computational paradigm studied with
application to problems in associative memory, learning, pattern
recognition, perception, robotics, and other areas.
Development of models for the
dynamics of neurons and methods such as learning for designing neural
networks. Concepts, designs, and methods compared and tested in
software simulation. Brain and consciousness studies are optional topics.
Programming and knowledge of linear algebra and calculus required.
CPSC 478b Computer Graphics Julie Dorsey
MW 1:00-2:15
An introduction to the basic concepts of two- and three-dimensional computer
graphics. Topics include affine and projective transformations, clipping
and windowing, visual perception, scene modeling and animation, algorithms
for visible surface determination, reflection models, illumination
algorithms, and color theory.
Assumes solid C or C++ programming skills and a
basic knowledge of calculus and linear algebra.
After Computer Science 202a and 223b.
CPSC 479a Advanced Topics in Computer Graphics Holly Rushmeier
(Not taught in 2008-2009)
An in-depth study of advanced algorithms and systems for rendering,
modeling, and animation in computer graphics. Topics vary and may include
reflectance modeling, global illumination, subdivision surfaces, NURBS,
physically-based fluids systems, and character animation.
After Computer Science 202a and 223b.
CPSC 480a or b Directed Reading By arrangement with faculty
Individual study for qualified students who wish to investigate an
area of computer science not covered in regular courses. A student
must be sponsored by a faculty member who sets the requirements and
meets regularly with the student. Requires a written plan of study
approved by the faculty advisor and the director of undergraduate
studies. May be taken more than once for credit.
CPSC 490a or b Special Projects By arrangement with faculty
Individual research. Requires a faculty supervisor and the
permission of the class advisor or the director of undergraduate
studies. The student must submit a written report about the results
of the project. May be taken more than once for credit.