Computer Science
Web site: http://www.cs.ucsb.edu (will open in a new browser window)
Chair: Divyakant Agrawal
Vice Chair: Ambuj Singh
Anurag Acharya, Ph.D., Carnegie Mellon University, Assistant Professor (operating systems, architecture, compilers)
Divyakant Agrawal, Ph.D., SUNY at Stony Brook, Professor (distributed systems, and distributed databases)
Kevin Almeroth, Ph.D., Georgia Institute of Technology, Assistant Professor (computer networks and protocols, large-scale multimedia systems, performance evaluation and distributed systems)
Tevfik Bultan, Ph.D., University of Maryland, College Park, Assistant Professor (specification and automated analysis of concurrent systems, computer aided verification, model checking)
Peter R. Cappello, Ph.D., Princeton University, Professor (JAVA/Internet-based parallel computing, multiprocessor scheduling, market-based resource allocation, self-directed learning)
Ö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, Professor (fault-tolerant distributed systems, distributed databases, operating systems)
Teofilo Gonzalez, Ph.D., University of Minnesota, Professor (multimessage multicasting, VLSI placement and routing algorithms, scheduling theory; design and analysis of algorithms)
Urs Hölzle, Ph.D., Stanford, Associate 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)
Ming Li, Ph.D., Cornell University, Professor (computational biology, bioinformatics; design and analysis of algorithms)
** Linda R. Petzold, Ph.D., University of Illinois at Urbana-Champaign, Professor (numerical differential equations, numerical optimization, mathematical software, parallel computing, scientific computing)
Klaus E. Schauser, Ph.D., UC Berkeley, Associate Professor (parallel computing, parallel programming languages, compilers, computer architecture)
Ambuj Singh, Ph.D., University of Texas at Austin, Associate Professor (databases, 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, Professor (computer vision, computer graphics, artificial intelligence)
Tao Yang, Ph.D., Rutgers University, Associate Professor (algorithms and programming systems for parallel and distributed processing, program scheduling and compilation, parallel scientific computing)
John Bruno, Ph.D., The City College of New York, Professor Emeritus (applications of digital systems to engineering problems, distributed systems, scheduling theory, networks and graphs)
Marvin Marcus, Ph.D., UC Berkeley, Professor Emeritus (linear and multilinear algebra, scientific computation, numerical algorithms)
* Roger C. Wood, Ph.D., UC Los Angeles, Professor Emeritus (computer system modeling, design and analysis, computer architecture)
* 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.
P. Michael Melliar-Smith, Ph.D. (Electrical and Computer Engineering)
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. Campus Instructional Computing 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. 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 is also available to help
with academic program planning. A department publication, Undergraduate Studies
in Computer Science, describes degree offerings, new courses, and requirement
changes.
Computer Engineering
This major is offered jointly by the Department of Computer Science and
the Department of Electrical and Computer Engineering. For information about
this major, refer to the section on Computer Engineering.
The pre-major requirements for the B.A. and the B.S. degrees in computer science are the same. Students intending to major in computer science should declare a pre-major when applying for admission to the university. It is strongly recommended that incoming freshmen complete a programming class prior to enrollment at UCSB. We recommend a Java course with emphasis in programming or a C++ programming course. Students who declare a pre-major are responsible for satisfying degree requirements in effect at the time of their declaration. When students have completed the preparation courses, they must petition to declare a change from pre-major to major status.
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.
Courses required for the pre-major or major, lower- or upper-division, inside or outside of the Department of Computer Science, cannot be taken for the passed/not passed grading option. They must be taken for letter grades.
Preparation for the major-B.S. and B.A.
Required: Mathematics 3A-B-C and 5A-B; Computer Science 10, 20, 30, 40, 50, and 60; and Probability and Statistics 120A. Courses identified as options within the preparation are considered equivalent; students may take one of them to satisfy the requirement but may not take more of them for credit.
Bachelor of Science -- Computer Science
Upper-division major
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.
Bachelor of Arts -- Computer Science
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.
Five-Year Bachelor of Science/Master of Science Program
A combined B.S./M.S. program in computer science provides an opportunity for
outstanding undergraduates to earn both degrees in five years. Additional information
about this program is available from the undergraduate office or from the computer
science graduate program assistant. Interested students should make their interest
known to the department early in their junior year. In addition to fulfilling
undergraduate degree requirements, B.S./M.S. degree candidates must meet Graduate
Division degree requirements, including university requirements for academic
residence and units of coursework as described in the section "Graduate
Education at UCSB."
In addition to departmental requirements, program applicants and candidates for graduate degrees must fulfill University requirements described in the section "Graduate Education at UCSB."
Admission
In addition to fulfilling the Graduate Division requirements for admission found in the section "Graduate Education at UCSB," the Department of Computer Science requires a bachelor's degree in some discipline of science, engineering, or mathematics.
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 (250 on the computer-based test) 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 Test of Spoken English is strongly recommended for international students applying for teaching assistant positions.
All fall application materials must be received by April 1. If an applicant wishes to be considered for fellowships and assistantships, all application materials must be received by January 1.
Master of Science Degree -- Computer Science
Degree Requirements
The average time for completion of the M.S. degree is two years. Students must take 42 units of upper-division (excluding 190+ level courses) or graduate level courses (200+, 595, 596, 598). A major area of study has to be chosen. The major areas of study are (1) Foundations of computer science, (2) Systems, and (3) Applications. Four computer science graduate courses (200 level) must be taken from the major area and one computer science graduate course (200 level) must be taken from each of the other two major areas. The same course cannot be used to satisfy both major area and breadth requirements. The grade-point average over the major area courses should be at least 3.0. At least two units and at most six units of Computer Science 595 should be used towards the unit requirements.
Each student must complete a study plan that details the courses that will be taken in order to fulfill the course requirements. The study plan must be approved by the student's faculty advisor and departmental graduate advisor.
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.
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. A maximum of 12 units of Computer Science 596 and 598 combined can be used toward unit requirements.
Plan 2 (examination option). Students must complete 42 units of coursework approved by a computer science advisor and pass a comprehensive examination. In addition to the six courses required for Plan 1 and Plan 2, 12 units of coursework also need to be completed. These 12 units must be computer science 100 level (excluding 190+) and 200 level courses. Of these additional units, eight must be 200 level courses. Plan 2 is available only to students who initially joined the graduate program as master of science candidates.
The comprehensive examination will be offered twice a year, in the eighth week of fall and spring quarters. Each student will list four courses, and a question from each of these courses will be asked on the examination. Three questions must be successfully answered.
Doctor of Philosophy -- Computer Science
Admission
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.
Objective
The purpose of the Doctor of Philosophy program in computer science is to prepare students for research and teaching positions in universities and colleges, and for research and leadership positions in industry and government. The primary aim of the program is to train students in the methods of scientific inquiry and independent research. This is accomplished through advanced coursework and active participation with the faculty in their research programs. Doctor of Philosophy students are expected to have a broad knowledge of all fields of computer science and have a deep understanding of at least one of its areas. In addition to this requirement, a Doctor of Philosophy student must be up to date in all the developments in his/her major area of specialization. The most important component of the Doctor of Philosophy program is learning to perform independent and significant research in one's area of specialization.
Requirements for the Doctor of Philosophy degree typically are completed in four to six years, depending on whether or not a student enters the program with an M.S. in computer science. Students entering this program should be committed to completing a Ph.D. Switching to the master's program is strongly discouraged and will be approved only under special circumstances.
Course Requirements
To ensure sufficient breadth at the graduate level, Ph.D. students must complete at least eight graduate courses with a grade of B or better. Students are expected to be well-rounded in the following subject areas: foundations of computer science, systems, and applications. The set of courses that students plan to take must be endorsed by the academic advisor and another Department of Computer Science faculty member. A graduate level course taken in another department or another university can be counted if endorsed by the academic advisor and another faculty member.
Exam Requirements
To earn a Ph.D., students must successfully complete four examinations: the screening examination; the oral major area examination (qualifying examination); the thesis proposal; and the dissertation defense.
The screening exam, which consists of ten subject areas (see table on previous page), is to ensure the student's breadth of knowledge 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 better 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. Students on financial support should pass the exam within the first year in order to be considered for second-year support. The exam is offered twice a year: once during the fall quarter and once during 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 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 may also be members. In special circumstances, non-UCSB faculty may be members. After the doctoral committee approves a student's proposed major area, the major area examination tests the student's knowledge of this area and any supporting areas (e.g., mathematics and electrical engineering). As a part of this examination, a student submits a set of relevant papers from the major area and prepares a brief presentation. Passing this oral examination allows this student to advance to candidacy for the doctoral degree.
After passing the major area 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 thesis proposal examination, which is oral, determines the feasibility of the research plan and the appropriateness of the research topic. The 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 and an evaluation 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
Not open for credit to students who have completed Computer Science 10 or
Engineering 1A-B-C or 2A-B-C or 3. 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:
C. C Programming
PA. Pascal
JA. Java
10. Introduction to Computer Programming
(4) Gonzalez, Su
Students with no prior programming background are encouraged to take Computer
Science 5JA before 10.
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
Different sections may be repeated. Sections not always offered.
Recommended preparation: knowledge of at least one programming language.
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
Prerequisites: Computer Science 5 or 10 or Engineering 1A-B-C or Engineering
2A-B-C or Engineering 3.
Not open for credit by computer science majors or pre-majors. Not open for credit
to students who have completed Computer Science 11C, 22, or 60.
Introduction to the UNIX system, C programming language, and data structures.
Topics include: introduction to the UNIX system, C shell and shell scripts;
UNIX file system and utilities; stacks, queues, lists, and trees.
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. Students write several medium-sized
object-oriented programs.
30. Introduction to Computer Systems
(4) Konheim
Prerequisite: Engineering 3 or Computer Science 5 or 10; and, Mathematics
3C.
Not open for credit to students who have completed ECE 15 or 15A or 15B.
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) Konheim
Prerequisites: Computer Science 10 or 12; and Mathematics 3C.
Not open for credit to students who have completed Computer Science 26.
Propositional predicate logic, set theory, functions and relations, counting,
mathematical induction and recursion (generating functions).
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 design, implement, and test one or two extensive object-oriented
programs.
60. Introduction to C, C++, and UNIX
(4) Bruno
Prerequisites: Computer Science 10 and 20.
Reduced credit of 2 units will be given 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 complete several small projects that exercise their understanding
of the material presented in class.
Engineering 100. Engineering Economic Analysis
(3) Staff
Prerequisite: upper-division standing in engineering.
Engineering feasibility factors and engineering economic analysis. Analysis
of alternatives and estimates of demands and costs in engineering. (F,W)
Engineering 101. Ethics in Engineering
(3) Staff
Prerequisite: upper-division standing in engineering.
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 or 2 or 2LK or 50 or
50LK; 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 8 or Computer Science 40 for Computer Science
109A; Computer Science 109A for Computer Science 109B; Computer Science 109B
for Computer Science 109C.
Same course as Mathematics 109A-B-C.
An introduction to mathematical logic with applications in computer science
and mathematics. 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; and, 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; and, 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 or 60; and, Computer Science 26
or 40; and, Computer Science 20; open to computer science and computer engineering
majors only.
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 or 40; and Computer Science 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
Prerequisites: Computer Science 26 or 40; open to computer science and computer
engineering majors only.
Finite automata and regular expressions; properties of regular languages; pushdown
automata and context free grammars/languages; properties of context-free languages.
153A. Hardware/Software Interface
(4) Bruno
Prerequisite: ECE 152A.
Same course as ECE 153A.
Machine-level structures implementing the operating system abstraction; memory-mappers,
multi-level interrupts, direct memory access techniques. Lowest-level software/firmware
structures: micro-kernels, interpreters, emulators, threaded-code, real-time
scheduling. Compilation and cross-compilation techniques; system initialization;
validation and debugging; in-circuit testing. (first offered 2002-2003)
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 and
computer engineering majors only, or by 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) Hölzle
Prerequisite: Computer Science 130A; open to computer science and computer
engineering majors only, or by 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, Computer Science 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, Computer Science 154; open
to computer science, computer engineering, 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.
171. Distributed Systems
(4) El Abbadi
Prerequisite: Computer Science 170.
Not open for credit to students who have completed ECE 151.
Distributed systems architecture, distributed programming, network of computers,
message passing, remote procedure calls, group communication, naming and membership
problems, asynchrony, logical time, consistency, fault-tolerance, and recovery.
(first offered 2004-2005)
172. Software Engineering
(4) Kemmerer
Prerequisites: Computer Science 130A; open to computer science majors only
or by consent of department.
Recommended preparation: Computer Science 130B.
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 by 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.
176A. Introduction to Computer Communication Networks
(4) Konheim
Prerequisites: PSTAT 120A or ECE 139; open to computer science, computer
engineering, and electrical engineering majors only.
Not open for credit to students who have completed Computer Science 176 or ECE
155 or ECE 155A.
Recommended preparation: PSTAT 120B.
Basic concepts in networking, the OSI model, error detection codes, flow control,
routing, medium access control, and high-speed networks.
176B. Network Computing
(4) Almeroth
Prerequisite: Computer Science 176A.
Not open for credit to students who have completed ECE 155B or 194W.
Creating networked application systems, distributed objects, CORBA, JAVA, applets,
mobile agents, naming, resource management, network security, internet multicasting
and multimedia, wireless networks. (first offered 2001-2002)
177. Computer Security
(4) Kemmerer
Prerequisite: Computer Science 170.
Introduction to the basics of computer security and privacy. Analysis of technical
difficulties of producing secure computer information systems that provide guaranteed
controlled sharing. Examination and critique of current systems, methods, certification.
178. Introduction to Cryptography
(4) Konheim
Prerequisites: Computer Science 10; and, Probability and Statistics 120A
or 121A.
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.
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.
182. Multimedia Computing
(4) Almeroth
Prerequisites: Computer Science 176A and 176B.
Not open for credit to students who have completed ECE 160.
Introduction to multimedia and applications, including video conferencing, WWW,
digital libraries, video on demand. Digital video and audio communication architectures,
standards (including JPEG and MPEG2), multimedia storage and retrieval. Multimedia
computing on the Internet and digital libraries. (first offered 2003-2004)
186. Theory of Computation
(4) Ibarra
Prerequisite: Computer Science 136; open to computer science majors only
or by consent of department.
Not open for credit to students who have completed Mathematics 150A.
Turing machines; computability and unsolvability; computational complexity;
intractability and NP-completeness.
189. Senior Computer Systems Project
(4) gonzalez
Prerequisite: consent of instructor; senior standing in computer engineering,
computer science or ECE.
Not open for credit to students who have completed ECE 189A-B.
Student groups design a significant computer-based project. Multiple groups
may cooperate toward one large project. Each group works independently; interaction
amoung groups is via interface specifications and informal meetings.
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.
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: upper-division standing, consent of the instructor.
Must have a minimum 3.0 grade-point average for the preceding three quarters.
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: upper-division standing; (2) ; (3) have completed at least
two upper-division courses in computer science.
Must have a minimum 3.0 grade-point average for the preceding three quarters.
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.
211A. Matrix Analysis and Computation
(4) Petzold
Prerequisite: consent of instructor.
Same course as ECE 210A, ME 210A, Mathematics 206A, and Chemical Engineering
211A.
Recommended preparation: Students should be proficient in basic numerical methods,
linear algebra, mathematically rigorous proofs, and some programming language.
Graduate level-matrix theory with introduction to matrix computations. SVD's,
pseudoinverses, variational characterization of eigenvalues, perturbation theory,
direct and iterative methods for matrix computations.
211B. Numerical Simulation
(4) Petzold
Prerequisite: consent of instructor.
Same course as ECE 210B, ME 210B, Mathematics 206B, and Chemical Engineering
211B.
Recommended preparation: Students should be proficient in basic numerical methods,
linear algebra, mathematically rigorous proofs, and some programming language.
Linear multistep methods and Runge-Kutta methods for ordinary differential equations:
stability, order, and convergence. Stiffness. Differential algebraic equations.
Numerical solution of boundary value problems.
211C. Numerical Solution of Partial Differential Equations-Finite Difference
Methods
(4) Petzold
Prerequisite: consent of instructor.
Same course as ECE 210C, ME 210C, Mathematics 206C, and Chemical Engineering
211C.
Recommended preparation: Students should be proficient in basic numerical methods,
linear algebra, mathematically rigorous proofs, and some programming language.
Finite difference methods for hyperbolic, parabolic and elliptic PDEs, with
application to problems in science and engineering. Convergence, consistency,
order and stability of finite difference methods. Dissipation and dispersion.
Finite volume methods. Software design and adaptivity.
211D. Numerical Solution of Partial Differential Equations-Finite Element
Methods
(4) Petzold
Prerequisite: consent of instructor.
Same course as ECE 210D, ME 210D, Mathematics 206D, and Chemical Engineering
211D.
Recommended preparation: Students should be proficient in basic numerical methods,
linear algebra, mathematically rigorous proofs, and some programming language.
Weighted residual and finite element methods for the solution of hyperbolic,
parabolic, and elliptical partial differential equations, with application to
problems in science and engineering. Error estimates. Standard and discontinuous
Galerkin methods.
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.
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.
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.
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) Schauser
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) Staff
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.
Recommended preparation: Computer Science 260.
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.
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.
Recommended preparation: Computer Science 262 is.
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) Staff
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.
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.
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)
278. Discrete Event Simulation
(4) Staff
Prerequisites: Probability and Statistics 120A or 121A; and 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.
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
N. Computer Networks
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 (may be taken concurrently).
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.
594. Seminar in Computer Science
(1-5) Staff
Prerequisite: consent of instructor and department.
A seminar course offered on an irregular basis. Provides an in-depth discussion
of advanced topics of general interest and broadens the scope of knowledge in
computer science.
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
N. Computer Networks
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.
Return to Top of Page
UCSB Home
| Office of the Registrar
| No Frames Version
Catalog Introduction | Past
Catalogs | Other UC Catalogs