Department of Computer Science,
Engineering I, Room 2106;
Telephone (805) 893-4321
Chair: Oscar H. Ibarra
Vice Chair: Peter R. Cappello
Open a new browser window to view the departmental page for Computer Science.
John L. Bruno, Ph.D., The City College of New York, Professor, Director of Engineering Computing Infrastructure (applications of digital systems to engineering problems, distributed systems, scheduling theory, networks and graphs)
Peter R. Cappello, Ph.D., Princeton University, Professor (concurrent computation, information retrieval)
Laura Dillon, Ph.D., University of Massachusetts, Amherst, Professor (analysis of concurrent systems, semantics of programming languages, formal specification and verification, software systems)
Ömer Egecioglu, Ph.D., UC San Diego, Professor (bijective and enumerative combinatorics, parallel algorithms, approximation algorithms, combinatorial algorithms)
Amr El Abbadi, Ph.D., Cornell University, Associate Professor (fault-tolerant distributed systems, distributed databases, operating systems)
Teofilo Gonzalez, Ph.D., University of Minnesota, Professor (computer-aided design, VLSI placement and routing algorithms, scheduling theory; design and analysis of algorithms)
Urs Hölzle, Ph.D., Stanford, Assistant Professor (object-oriented programming languages and systems, compilers, computer architecture, garbage collection)
Oscar H. Ibarra, Ph.D., UC Berkeley, Professor (theory of computation, design and analysis of algorithms, computational complexity, parallel computing, VLSI, computer-aided design)
Richard A. Kemmerer, Ph.D., UC Los Angeles, Professor (specification and verification of systems, computer system security and reliability, programming and specification language design, software engineering)
Alan G. Konheim, Ph.D., Cornell University, Professor (computer communications, computer systems, modeling and analysis, cryptography)
Marvin Marcus, Ph.D., UC Berkeley, Professor Emeritus
** Linda R. Petzold, Ph.D., University of Illinois at Urbana-Champaign, Professor (numerical differential equations, numerical optimization, mathematical software, parallel computing, scientific computing)
Martin C. Rinard, Ph.D., Stanford University, Assistant Professor (parallelizing compilers, parallel and distributed computation, parallel programming languages)
Klaus E. Schauser, Ph.D., UC Berkeley, Assistant Professor (parallel computing, parallel programming languages, compilers, computer architecture)
Ambuj Singh, Ph.D., University of Texas at Austin, Associate Professor (parallel and distributed systems, formal specification and verification)
§ Terence R. Smith, Ph.D., Johns Hopkins University, Professor, Director of Center for Computational Modeling and Systems (spatial databases, techniques in artificial machine intelligence)
Jianwen Su, Ph.D., University of Southern California, Associate Professor (database systems, theory, and applications)
Yuan-Fang Wang, Ph.D., University of Texas at Austin, Associate Professor (computer vision, computer graphics, artificial intelligence)
* Roger C. Wood, Ph.D., UC Los Angeles, Professor Emeritus
Tao Yang, Ph.D., Rutgers University, Assistant Professor (algorithms and programming systems for parallel and distributed processing, program scheduling and compilation, parallel scientific computing)
* Joint appointment with the Department of Electrical and Computer Engineering.
** Joint appointment with the Department of Mechanical and Environmental Engineering.
§ Joint appointment with the Department of Geography.
The Department of Computer Science offers programs leading to the degrees of bachelor of arts and bachelor of science in computer science, and the M.S. and Ph.D. in computer science. The B.A. is a College of Letters and Science major; the B.S. is a College of Engineering major. Both the B.A. and B.S. degree programs in computer science are accredited by the Computer Science Accreditation Commission of the Computing Sciences Accreditation Board.
One of the most important aspects of the Computer Science program at UCSB is the wealth of "hands-on" opportunities for students. UCSB has excellent computer facilities. The campus Micro Computer Laboratory makes accounts available to all students. Their facilities include late model PCs and MACs as well as NeXT workstations. Computer Science majors use the UNIX workstations in the Computer Science Instructional Lab and Engineering Computing Infrastructure computing facilities. The Department of Computer Science also operates a 64-node Meiko CS-2 parallel computer which is used in some upper-division courses. Students doing special projects can gain access to machines at the NSF Supercomputing Centers via the Internet.
Graduate students have the additional computing facilities available in the Graduate Student Laboratory. Students working with faculty have access to the specialized research facilities within the Department of Computer Science: the Reliable Software, Theory of Computation, Distributed Systems, Parallel Systems, and Vision Laboratories.
The undergraduate major in computer science has a dual purpose: to prepare students for advanced studies and research and to provide training for a variety of careers in business, industry, and government.
Undergraduate counseling is provided under the direction of the assistant to the dean for undergraduate studies. A faculty advisor and a peer advisor are also available to help with academic program planning. A department publication, Undergraduate Studies in Computer Science, describes degree offerings, new courses, and requirement changes.
Undergraduate students enrolled in other majors may petition to enter the pre-computer science major at any time Option A below has been met or they may petition to enter the full major when Option B has been met:
Option A: Satisfactory completion at UCSB of at least four 4-unit courses required for the computer science pre-major (listed below), including at least two in computer science, with a pre-major grade-point average of at least 3.0.
Option B: Satisfactory completion of all the pre-major requirements with a University of California grade-point average of at least 2.75.
Please note: Pre-major status does not guarantee admission to major status. No course required for the preparation may be taken on a passed/not passed basis. To be admitted to the major, the student must complete the preparation with a minimum grade-point average of 2.75.
The following courses are required: Computer Science 110A or 110B, 130A-B, 136, 154, 160, 162, 170, 186; Electrical and Computer Engineering 152A; and Probability and Statistics 120B. In addition, at least 16 units of major field electives are required. Prior approval of these electives must be obtained from the faculty advisor. In addition, the following courses are required: Physics 1, 2, 3, 3L and at least 8 units of science, mathematics, and engineering electives. Lists of approved science, mathematics, and engineering electives are available in the computer science office. All computer science majors are strongly encouraged to take Engineering 101, although it may not be used as an elective in the upper-division major.
The courses required for the B.A. are the same as for the B.S. degree, with the following exceptions: Computer Science 160 is not required; 7, rather than 16, units of major field electives are required; a science sequence and two additional science courses are required. The science sequence should be selected from: Chemistry 1A-B-C and labs, or Physics 1, 2, 3, 3L or Physics 6A-B-C and labs. A list of approved additional science courses is available in the Computer Science office. All computer science majors are strongly encouraged to take Engineering 101, although it may not be used as an elective in the upper-division major.
Applicants must have a grade-point average of at least 3.0 in their last two years of undergraduate study. Satisfactory performance in the verbal, quantitative, analytical sections of the Graduate Record Examination is required of all applicants. Applicants whose native language is not English must receive a score of at least 600 on the Test of English as a Foreign Language (TOEFL) prior to admission to UCSB. Applicants who have received a bachelor's or master's degree from a U.S. college or university are exempt from this requirement.
The average time for completion of the M.S. degree is two years. Students must take (and receive a grade of B or higher in each) three computer science graduate courses: Algorithms (Computer Science 230A), Theory (Computer Science 220), and Systems (Computer Science 262 or 270A or 270B). Students who have taken an equivalent course, or know the material, may take the course by special examination. There are two options to obtain the master's degree: Thesis (Plan 1) and Examination (Plan 2). The specific requirements for the thesis and the comprehensive examination options are given below. Plan 2 is not available to students whose initial degree objective was the Ph.D. degree.
Major areas of study are (1) foundations of computer science track, (2) systems track, and (3) applications track.
Plan 1 (thesis option). Students must complete 42 units of coursework approved by a computer science graduate advisor. Students must submit an acceptable thesis, completed under the supervision of a permanent computer science faculty member and approved by a thesis committee composed of three ladder faculty members from the Department of Computer Science. Plan 1 students enroll in Computer Science 598, for which they may receive 8 units of credit toward the 42 unit requirement. The remaining 34 required units are subject to a number of restrictions designed to ensure program coherence, depth, breadth, and quality: (1) at least 8 upper-division (100 series) and graduate level (200 series) courses must be completed, of which at least 5 are graduate level (200 series) courses; (2) a set of courses constituting a major area of study must be completed with an average grade of B or higher. Major areas are defined above.
Plan 2 (examination option). Students must complete 42 units of coursework approved by a computer science advisor and pass a comprehensive examination. The 42 required units are subject to a number of restrictions designed to ensure program coherence, depth, breadth, and quality: (1) at least 9 upper-division (100 series) and graduate level (200 series) courses must be completed, of which at least 7 are graduate level (200 series) courses; (2) a set of courses constituting a major area of study must be completed with an average grade of B or higher.
Students may apply directly to the Ph.D. program without a master's degree. However, a solid background in computer science or one or more fields of science and engineering is expected. Applicants to the Ph.D. program must have a grade-point average of at least 3.5 in their last two years of study. Requirements for the Ph.D. are typically completed in three to five years, depending on whether the student enters the program with an M.S. in computer science. Students entering this program should be committed to completing a Ph.D. The department discourages students petitioning to switch to the master's program; such petitions are approved only under exceptional circumstances.
Exam requirements. To earn a Ph.D., students must successfully complete four examinations: the screening examination; the major area examination; the oral qualifying examination; and the dissertation defense.
The screening exam, which consists of ten subject areas, is to ensure the student's breadth at the undergraduate level. A subject area can be passed with either a passing grade in the screening examination or with a grade of A- or higher in the course taught at UCSB. Although students are not required to pass all the subject exams at the same time, students are strongly encouraged to successfully complete all the subject areas as early in their graduate careers as possible. A student must satisfy this requirement within the first six quarters of residence in the Ph.D. program. In order to be considered for second-year support, a student should pass the exam within the first year. The exam is offered twice a year: once in the fall quarter and once in the spring quarter. Although the exam material is chosen from the upper-division undergraduate curriculum, students must show a level of skill, and a perspective, that is appropriate for graduate work.
After passing the screening examination, a student forms a doctoral committee to supervise dissertation research. The doctoral committee must be chaired by a ladder faculty member from the department, although faculty from other UCSB departments also may be members. In special circumstances, non-UCSB faculty may be members. After the doctoral committee approves a student's proposed major area, it tests the student's knowledge of this area and any supporting areas (e.g., mathematics and electrical engineering). This test is called the major area examination.
After passing the major area examination, but before taking the qualifying examination, a student prepares a dissertation proposal that describes the dissertation topic, summarizes the relevant background literature and presents a comprehensive research plan for the doctoral dissertation. The qualifying examination, which is oral, determines the feasibility of the research plan and the appropriateness of the research topic. This examination is administered by the student's doctoral committee.
The final examination is the defense of the candidate's dissertation, which consists of a public seminar-like lecture, questions from the audience, and a decision by the candidate's doctoral committee on whether the student has successfully defended the dissertation.
5AA-ZZ. Introduction to Computer Programming and Organization
(4) Staff
Prerequisites: not open for credit to students who
have completed Computer Science 10 or Engineering 1A-B-C or Engineering
2A-B-C or equivalent. May not be repeated with a different suffix.
Introduction to programming and the organization of computers.
Basic programming concepts, algorithms, data and control structures, debugging,
program design, documentation, structured programming. Sections are:
FO. Fortran
JA. Java
PA. Pascal
10. Introduction to Computer Programming
(4) Gonzalez, Su
Introduction to programming and computers. Basic programming
concepts: algorithms, data and control structures, debugging, program design,
documentation, structured programming, object oriented programming.
11AA-ZZ. Programming Language Laboratory
(1) Staff
Prerequisite: knowledge of at least one programming
language. Different sections may be repeated. Sections not always offered.
A self-paced course to allow a student who already possesses
a working knowledge of at least one programming language an opportunity
to learn other languages of interest. Each section studies a different
language. Sections are:
FO. Fortran
JA. Java
LI. Lisp (2 units)
PA. Pascal
12. Introduction to C and UNIX
(4) Bruno
Prerequisite: knowledge of at least one programming
language or consent of instructor. Cannot be taken for credit by computer
science majors or pre-majors or by students who have received credit for
Computer Science 11C or Computer Science 22.
Introduction to the UNIX system and the C programming
language. Topics include: basic introduction to the UNIX system, and the
C programming language; vi editor; C shell and shell scripts; the UNIX
file system and other UNIX utility programs.
20. Programming Methods
(4) Singh
Prerequisite: Computer Science 10.
Programming techniques as follows: specification, representation,
and manipulation of basic data structures such as stacks, queues, lists,
trees, sets, arrays, etc. Searching and sorting techniques; predicate logic
and program correctness; induction and recursion; running time analysis.
22. C and UNIX
(4) Bruno
Prerequisite: Computer Science 20 or consent of instructor.
This course may not be taken for credit by students who have received credit
for Computer Science 11C or 12.
Topics include: study of the C programming language with
an emphasis on dynamic storage allocation, pointer, and implementation
of data structures such as stacks, queues, lists, and trees. Debugging
tools; editors, C shell, shell scripts; UNIX file system, other UNIX utility
programs.
26. Foundations of Computer Science
(4) Cappello
Prerequisite: Mathematics 8, and 5B or 10B; or consent
of instructor.
Theory and computer science applications of sets, relations,
functions, propositional logic, elementary first order logic, mathematical
induction, pigeon-hole principle, addition and multiplication counting
principles, permutations, combinations, distributions, binomial/multinomial
coefficients and theorems, inclusion-exclusion principle, elementary generating
functions, recurrence relations.
30. Introduction to Computer Systems
(4) Konheim
Prerequisite: knowledge of at least one high-level
programming language. Not open for credit to students who have completed
ECE 15 or equivalent.
Basic computer organization; MC68000 assembly language
programming. Gates, combinational circuits, flip-flops and the design and
analysis of sequential circuits.
40. Foundations of Computer Science
(4) Cappello
Prerequisites: Computer Science 20 and Mathematics
3B. Not open for credit to students who have completed Computer Science
26.
Theory and computer science applications of: iteration,
induction, and recursion; the running time of programs; combinatorics;
relations and functions; propositional logic; and predicate logic.
50. Programming Project
(4) Hölzle
Prerequisites: Computer Science 10 and 20.
Program design (modularization, designing for changeability,
robustness, and testability), basic software engineering practices, principles
of user interface design. Students will design, implement, and test one
or two medium-sized programs.
60. Introduction to C, C++, and UNIX
(4) Rinard
Prerequisites: Computer Science 10 and 20. Not open
for credit to students who have completed Computer Science 12 or 22.
Syntax and semantics of C and C++. Introduction to basic
UNIX utilities and tools. Students will complete several small projects
that exercise their understanding of the material presented in class.
Engineering 101. Ethics in Engineering
(3) Staff
Prerequisite: upper-division standing in engineering
or consent of instructor.
The nature of moral value, normative judgment and moral
reasoning. Theories of moral value. The engineer's role in society. Ethics
in professional practice. Safety, risk, responsibility. Morality and career
choice. Code of ethics. Case studies will facilitate the comprehension
of the concepts introduced. (W,S)
Engineering 103. Advanced Engineering Writing
(4) Staff
Prerequisite: Engineering 2A-B-C or Writing 1 or 1LK,
2 or 2LK, and 50 or 50LK, or equivalents, and upper-division standing.
Analysis and practice of the forms of technical writing-reports,
proposals, journal papers, abstracts, and presentations-that engineers
and scientists will encounter in professional careers. Attention to research
methods, document design, effective graphics, technical style, and electronic
document preparation.
109A-B-C. Introduction to Mathematical Logic
(4-4-4) Staff
Prerequisites: Mathematics 3A, 8 and 31A-B or Computer
Science 26. Same course as Mathematics 109A-B-C.
An introduction to mathematical logic with applications
in computer science and mathematics. Possible topics include propositional
and predicate calculi, models, proof systems, decidability and undecidability,
automated theorem proving, unification, logic programming, and program
verification.
110A. Foundations of Scientific Computing
(4) Yang
Prerequisites: Mathematics 5B; Computer Science 12
or 22 or 60.
Introduction to the design and analysis of algorithms
for basic numerical problems in computational science. Emphasis on appropriate
data structures, languages, programming methodology, and performance evaluation
of numerical software.
110B. Parallel Scientific Computing
(4) Yang
Prerequisites: Mathematics 5B; Computer Science 20;
Computer Science 12 or 22 or 60.
Fundamentals of parallel computing, algorithm design
for numerical computation on parallel architectures, parallel languages
and tools for scientific computing. Emphasis on appropriate data structures,
languages, programming methodology and performance evaluation of numerical
software.
125. Introduction to Data Structures and Algorithms
(4) Agrawal
Prerequisite: Computer Science 12 or 11C. Not open
to computer science pre-majors or majors.
Data structures and applications. Mathematical induction,
recursion. Analysis of algorithms, space and time complexity. Stacks, queues,
deques, singly- and doubly-linked lists. Complex linked structures. Binary
trees, traversals, basic operations on trees. Sorting, searching.
130A. Data Structures and Algorithms I
(4) Gonzalez
Prerequisites: Computer Science 12 or 22; Computer
Science 20 and 26.
The study of data structures and applications. Correctness
proofs and techniques for the design of correct programs. Internal and
external searching. Hashing and height balanced trees. Analysis of sorting
algorithms. Memory management. Graph traversal techniques and their applications.
130B. Data Structures and Algorithms II
(4) Gonzalez
Prerequisites: Computer Science 26 and 130A.
Design and analysis of computer algorithms. Correctness
proofs and techniques for the design of correct programs. Solution of recurrence
relations. Design techniques: divide and conquer, greedy strategies, dynamic
programming, backtracking, and local search. Applications of techniques
to problems from several disciplines.
136. Automata and Formal Languages
(4) Egecioglu
Prerequisite: Computer Science 26. Not open for credit
to students who have received credit for Computer Science 185.
Finite automata and regular expressions; properties of
regular languages; pushdown automata and context free grammars/languages;
properties of context-free languages.
154. Computer Architecture
(4) Schauser
Prerequisite: ECE 152A. Not open for credit to students
who have received credit for ECE 154.
Introduction to the architecture of computer systems.
Topics include: central processing units, memory systems, channels and
controllers, peripheral devices, interrupt systems, software versus hardware
trade-offs.
160. Translation of Programming Languages
(4) El Abbadi
Prerequisites: Computer Science 130B and 136. Open
to computer science majors only or consent of department.
Study of the structure of compilers. Topics include:
lexical analysis; syntax analysis including LL and LR parsars; type checking;
run-time environments; intermediate code generation; and compiler-construction
tools.
162. Programming Languages
(4) Dillon, Hölzle
Prerequisite: Computer Science 130A. Open to computer
science majors only or consent of department.
Concepts of programming languages: scopes, parameter
passing, storage management; control flow, exception handling; encapsulation
and modularization mechanism; reusability through genericity and inheritance;
type systems; procedural, object-oriented, functional, and logic programming
languages.
165. Machine Intelligence
(4) Smith
Prerequisites: Computer Science 20, and 26 or 40.
Machine intelligence is concerned with computational
techniques for representing and reasoning about complex objects. Topics
covered include some of the machine intelligence programming languages,
data structures, control structures, and problem solving techniques used
in both research and application.
170. Operating Systems
(4) Agrawal
Prerequisites: Computer Science 130A or 125, and 154.
Open to computer science majors, or ECE majors, or by consent of department.
Basic concepts of operating systems. The notion of a
process; interprocess communication and synchronization; input-output,
file systems, memory management.
172. Software Engineering
(4) Kemmerer
Prerequisites: Computer Science 130A; Computer Science
130B is desirable. Open to computer science majors only or by consent of
department.
Software engineering is concerned with long-term, large-scale
programming projects. Software management, cost estimates, problem specification
and analysis, system design techniques, system testing and performance
evaluation, and system maintenance. Students will design, manage, and implement
a medium-sized project.
174. Data Base Management Systems
(4) Su
Prerequisite: Computer Science 130B. Open to computer
science majors only or consent of department.
Database system architectures, relational and object-oriented
databases, relational algebra, relational calculus, SQL, QBE, integrity
constraints, normal forms and database design, query processing and optimization,
indexing, transactions, concurrency control, and crash recovery.
176. Introduction to Computer Communication Networks
(4) Konheim
Prerequisite: PSTAT 120B. Open to computer science
and electrical and computer engineering majors only.
Basic concepts in networking, the OSI model, error detection
codes, flow control, routing, medium access control, and high-speed networks.
178. Introduction to Cryptography
(4) Konheim
Prerequisites: Computer Science 10 and Probability
and Statistics 120A or 121A, or equivalent courses.
An introduction to the basic concepts and techniques
of cryptography and cryptanalysis. Topics include: the Shannon Theory,
classical systems, the Enigma machine, the Data Encryption Standard, public
key systems, digital signatures, file security.
180. Computer Graphics
(4) Wang
Prerequisite: Computer Science 130B or consent of
instructor.
X Window System; Xlib and widget programming; 2D drawing
and painting algorithms; 2D transform and clipping; 3D transform, viewing,
and clipping; overview of PHIGS graphics standard; graphics hardware; interactive
devices and techniques; half-tone and dithering techniques; hidden surface
removal algorithms.
181B. Introduction to Computer Vision
(4) Wang
Same course as ECE 181B.
Overview of image processing, pattern recognition; image
formation, binary images; edge detection, image segmentation, introduction
to textured image analysis, optical flow, depth from stereo, shape from
shading, shape from motion, shape representation techniques, issues in
object recognition, case study of some vision systems.
186. Theory of Computation
(4) Ibarra
Prerequisite: Computer Science 136 or 185. Open to
computer science majors only or consent of department. Not open for credit
to students who have received credit for Mathematics 151.
Turing machines; computability and unsolvability; computational
complexity; intractability and NP-completeness.
190AA-ZZ. Special Topics in Computer Science
(1-5) Staff
Prerequisite: consent of instructor. Sections may
not be repeated without the consent of the chair.
These variable unit courses provide for the study of
topics of current interest in computer science.
A. Artificial Intelligence
B. Computer Graphics
C. Pattern Recognition
D. Program Verification
E. Computer Architectures
F. Algorithms and Complexity
G. Mathematical Theory of Computation
H. Semantic Models
I. Software Systems
J. General
K. Computer Systems Modeling and Analysis
L. Scientific Computation
192. Projects in Computer Science
(4) Staff
Prerequisite: consent of instructor. May be repeated
once for credit but only 4 units may be applied to the major.
Projects in computer science for advanced undergraduate
students.
193. Internship in Industry
(1-4) Staff
Prerequisites: consent of instructor and department
chair. Not more than 4 units per quarter; may not be applied as science,
mathematics, and engineering electives. May be repeated with faculty/chair
approval.
Special projects for selected students. Offered in conjunction
with selected industrial and research firms under direct faculty supervision.
Prior departmental approval required.
194. Group Studies in Computer Science
(1-5) Staff
May be repeated for credit to a maximum of 8 units
but only 4 units may be applied to the major.
Group studies intended for small number of advanced students
who share an interest in a topic not included in the regular department
curriculum.
196. Undergraduate Research
(2-4) Staff
Prerequisites: students must (1) have attained upper-division
standing, (2) have a minimum 3.0 grade-point average for the preceding
three quarters, (3) have consent of the instructor. May be repeated for
up to 12 units. No more than 4 units may be applied to departmental electives.
Research opportunities for undergraduate students. Students
will be expected to give regular oral presentations, actively participate
in a weekly seminar, and prepare at least one written report on their research.
199A-B-C. Independent Studies in Computer Science
(1-5, 1-5, 1-5) Staff
Prerequisites: students must (1) have attained upper-division
standing; (2) have a minimum 3.0 grade-point average for the preceding
three quarters; (3) have completed at least two upper-division courses
in computer science. Students are limited to 5 units per quarter and 30
units total in all 98/99/198/199/199RA courses combined. Computer Science
199A-B is a two-quarter in-progress course with grades for both quarters
assigned upon completion of 199B. Computer Science 199C is a one-quarter
course with grade assigned at the end of the quarter.
210C. Topics in Scientific Computation
(4) Yang
Prerequisite: consent of instructor. Students should
be proficient in linear algebra, mathematically rigorous proofs, and some
programming language.
Topics may include one or more of the following: interpolation
and approximation, quadrature, ordinary differential equations, iterative
methods for solving linear and nonlinear problems, sparse matrix theory
and applications, parallel algorithms in numerical analysis. Consult the
instructor for the exact course content. (May not be offered each year)
220. Automata-Based Complexity
(4) Ibarra
Prerequisite: Computer Science 186.
Topics include: models of computation; time and space
complexity classes (e.g., P, NP, Co-NP, and PSPACE), efficient reducibilities,
complete problems; lower bounds; the polynomial hierarchy. (May not be
offered each year)
230A-B. Design and Analysis of Algorithms
(4-4) Gonzalez
Prerequisites: Computer Science 130A-B. Not open for
credit to students who have received credit for Mathematics 254.
Topics include: NP-completeness and reducibility; approximation
algorithms; polynomial and fully polynomial time approximation schemes;
amortized complexity; graph algorithms; lower bound techniques; probabilistic
analysis of algorithms; randomized algorithms; linear programming.
232. Complexity of Parallel Algorithms
(4) Egecioglu
Prerequisite: Computer Science 186.
Current research topics in the area of parallel algorithms
and complexity. Topics include: models of parallel computation, Boolean
circuits, complexity classes, the class NC, parallel arithmetic operations,
graph algorithms, and matrix operations.
240A. High-Performance Parallel Systems and Languages
(4) Schauser
Prerequisites: Computer Science 154 and 160, or consent
of instructor.
Overview of parallel architectures and communication;
parallel programming paradigms; performance models of parallel computation;
parallel algorithms and applications; systems and compilers for parallel
languages.
240B. Parallel Computing and Program Parallelization
(4) Yang
Prerequisites: Computer Science 130A and 160, or consent
of instructor.
Parallel programming; representation of parallelism,
program dependence analysis, loop transformation; program and data partitioning,
locality optimization; task scheduling and load balancing; parallelizing
compilers and run-time support.
260. Advanced Topics in Translation
(4) Rinard
Prerequisites: Computer Science 160 and 162.
Theoretical aspects of translation. Topics include: parsing
algorithms for LR and LL grammars, intermediate code generation, flow analysis,
optimization; run-time environments, attributed grammars, error processing.
(May not be offered each year)
262. Semantics of Programming Languages
(4) Dillon
Prerequisites: Computer Science 160 and 162.
Methods for the formal description of programming languages;
various approaches to formal semantics: operational, denotational, axiomatic,
attribute grammars; complimentary definitions.
263. Modern Programming Languages and Their Implementation
(4) Hölzle
Prerequisites: Computer Science 154, 160, and 162.
Computer Science 260 recommended.
Topics central to modern programming languages and their
implementation: garbage collection; memory system performance; characteristics
and optimization of object-oriented languages; type systems and type inference;
run-time compilation.
265. Advanced Topics in Machine Intelligence
(4) Smith
Prerequisite: Computer Science 165 or consent of instructor.
Course may be repeated for credit.
Topics covered include advanced programming techniques
for representing and reasoning about complex objects, and various applications
of such techniques including expert systems, natural language processors,
image understanding systems, and machine learning.
266. Formal Specification and Verification
(4) Kemmerer
Prerequisites: Computer Science 130A-B; Computer Science
186. Computer Science 262 is recommended.
Introduction to existing specification and verification
systems, and the underlying theory and techniques of verifying the correctness
of algorithms with respect to specifications. This subject can be considered
as the combination of specification and verification techniques, programming
language semantics, and formal logic.
270A. Advanced Topics in Operating Systems
(4) Bruno
Prerequisite: undergraduate course in operating systems
and computer architecture.
Operating system implementation issues. Topics include
process and storage management, file systems, I/O subsystems, multiprocessor
and distributed operating systems, computer networking.
270B. Principles of Distributed Systems
(4) El Abbadi
Prerequisite: Computer Science 170.
This course provides an introduction to the basic problems
in distributed systems and the various tools used to solve them. Of primary
interest is the issue of fault-tolerance. Topics include event ordering,
clocks, synchronization, mutual exclusion, agreement, and fault-tolerance.
272. Software Engineering
(4) Kemmerer
Prerequisite: Computer Science 172.
Principles of software engineering disciplines emphasizing
requirements analysis, specification design, coding, testing and correctness
proofs, maintenance, and management. Students will use a number of software
engineering tools.
273. Data and Knowledge Bases
(4) Su
Prerequisite: Computer Science 186 or consent of instructor.
The focus is on the study of relational and post-relational
data models and their query languages of different styles (algebraic, calculus,
and deductive): complexity, expressive power, optimization, and database
design.
274. Transaction Management in Distributed Databases
(4) El Abbadi
Prerequisite: Computer Science 170 or consent of instructor.
Topics include: data models, semantics; data integrity;
database design; serializability theory, concurrency control, recovery,
distributed databases.
276. Distributed Computing and Computer Networks
(4) Konheim
Prerequisite: Computer Science 270A.
Distributed processing: task partitioning, interprocess
communication, synchronization, reconfiguration, file allocation, and deadlock
problems; computer communication network models, analysis and synthesis.
(May not be offered each year)
277. Computer Security
(4) Kemmerer
Prerequisite: Computer Science 170 or consent of instructor.
Analysis of technical difficulties of producing secure
computer information systems that provide guaranteed controlled sharing.
Examination and critique of current systems, methods; certification.
278. Discrete Event Simulation
(4) Staff
Prerequisites: Probability and Statistics 120A or
121A and Computer Science 130A.
Discrete-event simulation for performance evaluation
of complex systems. Design of simulation models, random numbers, simulation
of discrete and continuous random variates and random processes, statistical
analysis of output data, variance reduction techniques.
280. Computer Graphics
(4) Wang
Prerequisite: Computer Science 180.
Special topics in computer graphics including: curves
and curved surfaces, visual perception of colors and color models; shading
models; shadow generation; texture mapping; solid textures; stereographics;
helmet-mounted display; graphics hardware/architecture; solid modeling;
physically-based modeling; fractals and graphtals; volume rendering; scientific
visualization.
281B. Advanced Topics in Computer Vision
(4) Wang
Prerequisite: Computer Science 181B or consent of
instructor. Same course as ECE 281B.
Advanced topics in computer vision: image sequence analysis,
spatio-temporal filtering, camera calibration and hand-eye coordination,
robot navigation, shape representation, physically-based modeling, multi-sensory
fusion, biological models, expert vision systems, and other topics selected
from recent research papers.
290AA-ZZ. Special Topics in Computer Science
(1-5) Staff
Prerequisite: consent of instructor.
These variable-unit courses provide for the study of
topics of current interest in computer science. Special topics are coded
as follows.
A. Artificial Intelligence
B. Computer Graphics
C. Pattern Recognition
D. Program Verification
E. Computer Architectures
F. Algorithms and Complexity
G. Mathematical Theory of Computation
H. Semantic Models
I. Software Systems
J. General
K. Computer Systems Modeling and Analysis
L. Scientific Computation
501. Techniques of Engineering Teaching
(2) Staff
Prerequisite: consent of graduate advisor. This course
is required for new teaching assistants, and may be taken only once. No
unit credit allowed toward advanced degree.
An initial 1-2 day workshop on teaching techniques followed
by practical experience in teaching, videotaping, and meetings with instructional
consultation staff to improve techniques.
502. Teaching of Computer Science
(1-4) Staff
Prerequisite: Computer Science 501 or consent of instructor.
May be taken concurrently with Computer Science 501. No unit credit allowed
toward advanced degree.
Procedures and techniques for teaching computer science
gained through actual teaching of lecture courses, leading discussion sections,
and/or teaching laboratories. Meetings will be held as needed to discuss
problems, methods and procedures.
595AA-ZZ. Group Studies in Computer Science
(1-5) Staff
Prerequisite: consent of instructor. May be repeated
for credit provided letter designations are different.
Special seminars focusing on topics of interest to faculty
and graduate students. These seminars provide critical review of research
in various areas of computer science.
A. Artificial Intelligence
B. Computer Graphics
C. Pattern Recognition
D. Program Verification
E. Computer Architectures
F. Algorithms and Complexity
G. Mathematical Theory of Computation
H. Semantic Models
I. Software Systems
J. General
K. Computer Systems Modeling and Analysis
L. Scientific Computation
596A-B-C. Directed Research
(2-12, 2-12, 2-12) Staff
Computer Science 596A-B is a two-quarter in-progress
course with grades for both quarters assigned upon completion of 596B.
Computer Science 596C is a one-quarter course with grade assigned at the
end of the quarter.
Research, either experimental or theoretical, may be
undertaken by properly qualified graduate students under the direction
of a faculty member.
597. Individual Studies for M.S. Comprehensive Examinations
and Ph.D. Examinations
(1-12) Staff
No unit credit allowed toward advanced degree. Enrollment
limited to 24 units per examination. Maximum of 12 units per quarter. Instructor
is normally student's major professor or chair of doctoral committee. S/U
grading.
Individual studies for M.S. comprehensive examination
and Ph.D. examinations.
598. Master's Thesis Research and Preparation
(1-12) Staff
Prerequisite: consent of graduate advisor.
For research underlying the thesis and writing of the
thesis.
599. Ph.D. Dissertation Research and Preparation
(1-12) Staff
Prerequisite: consent of chair of student's doctoral
committee.
Research and preparation of dissertation.