Computer Science

UCLA
4732 Boelter Hall
Box 951596
Los Angeles, CA 90095-1596

 

(310) 825-3886
fax: (310) 825-2273
http://www.cs.ucla.edu

Jason (Jingsheng) Cong, Ph.D., Chair
Richard R. Muntz, Ph.D., Vice Chair
Jens Palsberg, Ph.D., Vice Chair

Professors

Rajive L. Bagrodia, Ph.D.

Alfonso F. Cardenas, Ph.D.

Wesley W. Chu, Ph.D.

Jason (Jingsheng) Cong, Ph.D.

Adnan Y. Darwiche, Ph.D.

Joseph J. DiStefano III, Ph.D.

Michael G. Dyer, Ph.D.

Milos D. Ercegovac, Ph.D.

Deborah L. Estrin, Ph.D. (Jonathan B. Postel Professor of Networking)

Eliezer M. Gafni, Ph.D.

Mario Gerla, Ph.D.

Sheila A. Greibach, Ph.D.

Richard E. Korf, Ph.D.

Richard R. Muntz, Ph.D.

Rafail Ostrovsky, Ph.D.

Jens Palsberg, Ph.D.

D. Stott Parker, Jr., Ph.D.

Miodrag Potkonjak, Ph.D.

Stefano Soatto, Ph.D.

Majid Sarrafzadeh, Ph.D.

Demetri Terzopoulos, Ph.D. (Chancellor's Professor)

Carlo Zaniolo, Ph.D. (Norman E. Friedmann Professor of Knowledge Sciences)

Lixia Zhang, Ph.D.

Professors Emeriti

Algirdas A. Avizienis, Ph.D.

Bertram Bussell, Ph.D.

Jack W. Carlyle, Ph.D.

Gerald Estrin, Ph.D.

Thelma Estrin, Ph.D.

Leonard Kleinrock, Ph.D.

Allen Klinger, Ph.D.

Lawrence P. McNamee, Ph.D.

Michel A. Melkanoff, Ph.D.

Judea Pearl, Ph.D.

Jacques J. Vidal, Ph.D.

Associate Professors

Songwu Lu, Ph.D.

David A. Rennels, Ph.D.

Amit Sahai, Ph.D.

Yuval Tamir, Ph.D.

Song-Chung Zhu, Ph.D.

Assistant Professors

Junghoo (John) Cho, Ph.D.

Petros Faloutsos, Ph.D.

Edward Kohler, Ph.D.

Rupak Majumdar, Ph.D.

Todd Millstein, Ph.D.

Glenn D. Reinman, Ph.D.

Senior Lecturer

Leon Levine, M.S., Emeritus

Lecturers P.S.O.E.

Paul R. Eggert, Ph.D.

David A. Smallberg, M.S.

Adjunct Professors

Alan Kay, Ph.D.

Boris Kogan, Ph.D.

Gerald J. Popek, Ph.D.

M. Yahya "Medy" Sanadidi, Ph.D.

Adjunct Associate Professors

Leon Alkalai, Ph.D.

Peter L. Reiher, Ph.D.

Scope and Objectives

Computer science is concerned with the design, modeling, analysis, and applications of computer-related systems. Its study at UCLA provides education at the undergraduate and graduate levels necessary to understand, design, implement, and use the software and hardware of digital computers and digital systems. The programs provide comprehensive and integrated studies of subjects in computer system architecture, computer networks, distributed computer systems, programming languages and systems, information and data management, artificial intelligence, computer science theory, and computer vision and graphics.

The undergraduate and graduate studies and research projects in computer science are supported by significant computing resources. In addition to the departmental computing facility, there are over a dozen laboratories specializing in areas such as distributed systems, multimedia computer communications, distributed sensor networks, VLSI systems, VLSI CAD, embedded and reconfigurable systems, computer graphics, and artificial intelligence. Also, the Cognitive Systems Laboratory is engaged in studying computer systems that emulate or support human reasoning. The Biocybernetics Laboratory is devoted to multidisciplinary research involving the application of engineering and computer science methods to problems in biology and medicine.

The B.S. degree may be attained either through the Computer Science and Engineering major or through the Computer Science major described below.

In addition to the B.S. in Computer Science and Engineering and the B.S. in Computer Science, HSSEAS offers M.S. and Ph.D. degrees in Computer Science, as well as minor fields for graduate students seeking engineering degrees. In cooperation with the John E. Anderson Graduate School of Management, the Computer Science Department offers a concurrent degree program that enables students to obtain the M.S. in Computer Science and the M.B.A. (Master of Business Administration).

Department Mission

The Computer Science Department strives for excellence in creating, applying, and imparting knowledge in computer science and engineering through comprehensive educational programs, research in collaboration with industry and government, dissemination through scholarly publications, and service to professional societies, the community, state, and nation.

Computer Science and Engineering Undergraduate Program Objectives

The educational goal of the computer science and engineering program is to produce graduates who are well grounded in core computer science knowledge, but who also have an understanding of electrical and electronic circuits. They should have the problem-solving and other professional skills that will enable them to achieve their full potential and to excel in their chosen career paths.

The overall objective of the program is to graduate students who are (1) prepared for entry-level positions as practicing computer scientists or computer engineers or for continued education in graduate programs through core scientific and engineering knowledge, laboratory and design experience, a solid grounding in the principal areas of computer science and engineering, and exposure to the current state of the art, (2) positioned for sustained career achievement through cultivation of critical professional skills, including teamwork, written and oral communications, problem-solving abilities, a commitment to lifelong learning, core ethical values, and an understanding of the implications of one's work on society, and (3) prepared for practice in computer systems engineering at the interface of digital hardware and software and the electronic circuits that interface computers to the analog world. Students will be prepared to contribute in the fertile application areas where computing and other technical fields intersect through substantial knowledge of at least one additional engineering discipline or technical application area.

Computer Science Undergraduate Program Objectives

The educational goal of the computer science program is to produce graduates who are well grounded in core computer science knowledge and have the problem-solving and other professional skills that will enable them to achieve their full potential and to excel in their chosen career paths.

The overall objective of the program is to graduate students who are (1) prepared for entry-level positions as practicing computer scientists or for continued education in graduate programs through core scientific and engineering knowledge, laboratory and design experience, a solid grounding in the principal areas of computer science, and exposure to the current state of the art, (2) positioned for sustained career achievement through cultivation of critical professional skills, including teamwork, written and oral communications, problem-solving abilities, a commitment to lifelong learning, core ethical values, and an understanding of the implications of one's work on society, and (3) prepared for practice in one of the fertile application areas where computing and other technical fields intersect through in-depth knowledge of at least one related engineering discipline or application area.

Undergraduate Study

Computer Science and Engineering B.S.

The ABET-accredited computer science and engineering curriculum at UCLA provides the education and training necessary to design, implement, test, and utilize the hardware and software of digital computers and digital systems. The curriculum has components spanning both the Computer Science and Electrical Engineering Departments. Within the curriculum students study all aspects of computer systems from electronic design through logic design, MSI, LSI, and VLSI concepts and device utilization, machine language design, implementation and programming, operating system concepts, systems programming, networking fundamentals, higher-level language skills, and application of these to systems. Students are prepared for employment in a wide spectrum of high-technology industries.

The computer science and engineering curriculum is also accredited by the Computing Accreditation Commission of ABET, 111 Market Place, Suite 1050, Baltimore, MD 21202-4012, (410) 347-7700.

Preparation for the Major

Required: Chemistry and Biochemistry 20A; Computer Science 1, 31, 32, 33, 35L, M51A (or Electrical Engineering M16); Electrical Engineering 1, 2, 10; Mathematics 31A, 31B, 32A, 32B, 33A, 33B, 61; Physics 1A, 1B, 4AL, 4BL.

The Major

Required: Computer Science 101, 111, 118, 131, M151B (or Electrical Engineering M116C), M152A (or Electrical Engineering M116L), M152B (or Electrical Engineering M116D), 180, 181, Electrical Engineering 102, 110, 110L, 115A, 115C, Statistics 110A; three breadth courses (12 units) selected from an approved list available in the Office of Academic and Student Affairs; and three upper division computer science elective courses (12 units), one of which must be selected from Computer Science 143 or 161 or 174A. Electrical Engineering 103 may be substituted for one elective (credit is not given for both Computer Science 170A and Electrical Engineering 103), and either Computer Science 194 or one 4-unit 199 course may be applied as an elective by petition.

For information on University and general education requirements, see Requirements for B.S. Degrees on page 21 or http://www.registrar.ucla.edu/ge/GE-ENGRNew06-07.pdf.

Computer Science B.S.

The computer science curriculum is designed to accommodate students who want professional preparation in computer science but do not necessarily have a strong interest in computer systems hardware. The curriculum consists of components in computer science, a minor or technical support area, and a core of courses from the social sciences, life sciences, and humanities. Within the curriculum, students study subject matter in software engineering, principles of programming languages, data structures, computer architecture, theory of computation and formal languages, operating systems, distributed systems, computer modeling, computer networks, compiler construction, and artificial intelligence. Majors are prepared for employment in a wide range of industrial and business environments.

The computer science curriculum is accredited by the Computing Accreditation Commission of ABET, 111 Market Place, Suite 1050, Baltimore, MD 21202-4012, (410) 347-7700.

Preparation for the Major

Required: Chemistry and Biochemistry 20A; Computer Science 1, 31, 32, 33, 35L, M51A (or Electrical Engineering M16); Electrical Engineering 1; Mathematics 31A, 31B, 32A, 32B, 33A, 33B, 61; Physics 1A, 1B, 4AL, 4BL.

The Major

Required: Computer Science 101, 111, 118, 130 (or M152B or Electrical Engineering M116D), 131, M151B (or Electrical Engineering M116C), M152A (or Electrical Engineering M116L), 180, 181, Statistics 110A; three upper division science and technology courses (12 units) not used to satisfy other requirements, which may include three computer science courses, three courses to augment the breadth courses requirement, or three courses selected from one of the following: astronomy, atmospheric and oceanic sciences, biological chemistry, biomathematics, chemical and biomolecular engineering, chemistry and biochemistry, civil and environmental engineering, Earth and space sciences, economics, electrical engineering, information studies, linguistics, management, materials science and engineering, mathematics, mechanical and aerospace engineering, microbiology, immunology, and molecular genetics, molecular biology, molecular, cell, and developmental biology, physics -- courses selected from outside the school must be approved by petition; three breadth courses (12 units) selected from an approved list available in the Office of Academic and Student Affairs; and six upper division computer science elective courses (24 units), two of which must be selected from Computer Science 143, 161, 174A and one of which must be from 112 or 170A or Electrical Engineering 103 (credit is not given for both Computer Science 170A and Electrical Engineering 103). Students who select Electrical Engineering 103 may not receive credit for Mathematics 151A under the science and technology electives; if students have not taken Computer Science 130, one elective course must be 132; and either Computer Science 194 or one 4-unit 199 course may be applied as an elective by petition.

For information on University and general education requirements, see Requirements for B.S. Degrees on page 21 or http://www.registrar.ucla.edu/ge/GE-ENGRNew06-07.pdf.

Graduate Study

For information on graduate admission, see Graduate Programs, page 24.

The following introductory information is based on the 2006-07 edition of Program Requirements for UCLA Graduate Degrees. Complete annual editions of Program Requirements are available from the "Publications" link at http://www.gdnet.ucla.edu. Students are subject to the degree requirements as published in Program Requirements for the year in which they matriculate.

The Department of Computer Science offers Master of Science (M.S.) and Doctor of Philosophy (Ph.D.) degrees in Computer Science and participates in a concurrent degree program with the John E. Anderson Graduate School of Management.

Computer Science M.S.

Course Requirements

Course Requirement. A total of nine courses is required for the M.S. degree, including a minimum of five graduate courses. No specific courses are required, but a majority of both the total number of formal courses and the total number of graduate courses must consist of courses offered by the Computer Science Department.

Undergraduate Courses. No lower division courses may be applied toward graduate degrees. In addition, the following upper division courses are not applicable toward graduate degrees: Chemical Engineering 102A, 199; Civil and Environmental Engineering 106A, 108, 199; Computer Science M152A, M152B, M171L, 199; Electrical Engineering 100, 101, 102, 103, 110L, M116D, M116L, M171L, 199; Materials Science and Engineering 110, 120, 130, 131, 131L, 132, 140, 141L, 150, 160, 161L, 199; Mechanical and Aerospace Engineering 102, 103, 105A, 105D, 199.

Breadth Requirement. Candidates for the M.S. in Computer Science must satisfy the computer science breadth requirement by the end of the fourth quarter in graduate residence at UCLA. The requirement is satisfied by mastering the contents of six undergraduate courses in computer science chosen from the following two groups:

Group I: Four required courses or equivalent from Computer Science M51A, 143 or 180, M151B, 181.

Group II: Two required courses or equivalent from Computer Science 111, 112 or 118, 131 or 132, 161, 170A or 174A.

In addition, for each degree students must complete at least one course per quarter for three quarters of Computer Science 201 with grades of Satisfactory.

Competence in any or all courses may be demonstrated in one of three ways:

1. Satisfactory completion of the course at UCLA with a grade of B- or better

2. Satisfactory completion of an equivalent course at another university with a grade of B- or better

3. Satisfactory completion of a final examination in the course at UCLA

Comprehensive Examination Plan. In the comprehensive examination plan, at least five of the nine courses must be 200-series courses. The remaining four courses may be either 200-series or upper division courses. No units of 500-series courses may be applied toward the comprehensive examination plan requirements.

Thesis Plan. In the thesis plan, seven of the nine courses must be formal courses, including at least four from the 200 series, and three may be in the 100 or 200 series. The remaining two courses must be 598 courses involving work on the thesis.

Comprehensive Examination Plan

Consult the department.

Thesis Plan

The thesis is a report on the results of the investigation of a problem in the major field of study under the supervision of the thesis committee, which approves the subject and plan of the thesis and reads and approves the complete manuscript. While the problem may be one of narrow scope, the thesis must show significant style, organization, and depth of understanding of the subject. Students should normally start to plan the thesis at least one year before the award of the M.S. degree is expected. There is no examination under the thesis plan.

Computer Science M.S./Management M.B.A.

The Department of Computer Science and the John E. Anderson Graduate School of Management offer a concurrent degree program that enables students to complete the requirements for the M.S. in Computer Science and the M.B.A. (Master of Business Administration) in three academic years. Students should request application materials from both the M.B.A. Admissions Office, John E. Anderson Graduate School of Management, and the Department of Computer Science.

Computer Science Ph.D.

Major Fields or Subdisciplines

Artificial intelligence; computational systems biology (formerly biomedical systems/computational biology); computer networks; computer science theory; computer system architecture; information and data management; software systems.

Course Requirements

The basic program of study for the Ph.D. degree is built around one major field and two minor fields; the major and at least one minor must be in computer science. The major field corresponds to a body of knowledge contained in six courses, at least four of which are graduate courses.

Breadth Requirement. Candidates for the Ph.D. in Computer Science must satisfy the computer science breadth requirement by the end of the fourth quarter in graduate residence at UCLA. The requirement is satisfied by mastering the contents of six undergraduate courses in computer science chosen from the following two groups:

Group I: Four required courses or equivalent from Computer Science M51A, 143 or 180, M151B, 181.

Group II: Two required courses or equivalent from Computer Science 111, 112 or 118, 131 or 132, 161, 170A or 174A.

In addition, for each degree students must complete at least one course per quarter for three quarters of Computer Science 201 with grades of Satisfactory.

Competence in any or all courses may be demonstrated in one of three ways:

1. Satisfactory completion of the course at UCLA with a grade of B- or better

2. Satisfactory completion of an equivalent course at another university with a grade of B- or better

3. Satisfactory completion of a final examination in the course at UCLA

For requirements for the Graduate Certificate of Specialization, see Engineering Schoolwide Programs.

Written and Oral Qualifying Examinations

After mastering the body of knowledge defined in the three fields and passing the breadth requirement, students take a written qualifying examination. After passing the written qualifying examination, students should form a doctoral committee and prepare to take the University Oral Qualifying Examination. The nature and content of the examination are at the discretion of the doctoral committee but ordinarily include a broad inquiry into the student's preparation for research. The doctoral committee also reviews the prospectus of the dissertation at the oral qualifying examination.

Note: Doctoral Committees. A doctoral committee consists of a minimum of four members. Three members, including the chair, are "inside" members and must hold appointments at UCLA in the student's major department in HSSEAS. The "outside" member must be a UCLA faculty member outside the student's major department.

Fields of Study

Artificial Intelligence

Artificial intelligence (AI) is the study of intelligent behavior. While other fields such as philosophy, psychology, neuroscience, and linguistics are also concerned with the study of intelligence, the distinguishing feature of AI is that it deals primarily with information processing models. Thus the central scientific question of artificial intelligence is how intelligent behavior can be reduced to information processing. Since even the simplest computer is a completely general information processing device, the test of whether some behavior can be explained by information processing mechanisms is whether a computer can be programmed to produce the same behavior. Just as human intelligence involves gathering sensory input and producing physical action in the world, in addition to purely mental activity, the computer for AI purposes is extended to include sense organs such as cameras and microphones, and output devices such as wheels, robotic arms, and speakers.

The predominant research paradigm in artificial intelligence is to select some behavior which seems to require intelligence on the part of humans, to theorize about how the behavior might be accounted for, and to implement the theory in a computer program to produce the same behavior. If successful, such an experiment lends support to the claim that the selected behavior is reducible to information processing terms, and may suggest the program's architecture as a candidate explanation of the corresponding human process.

The UCLA Computer Science Department has active research in the following major subfields of artificial intelligence:

Problem Solving. Analysis of tasks, such as playing chess or proving theorems, that require reasoning about relatively long sequences of primitive actions, deductions, or inferences

Knowledge representation and qualitative reasoning. Analysis of tasks such as commonsense reasoning and qualitative physics. Here the deductive chains are short, but the amount of knowledge that potentially may be brought to bear is very large

Expert systems. Study of large amounts of specialized or highly technical knowledge that is often probabilistic in nature. Typical domains include medical diagnosis and engineering design

Natural language processing. Symbolic, statistical, and artificial neural network approaches to text comprehension and generation

Computer vision. Processing of images, as from a TV camera, to infer spatial properties of the objects in the scene (three-dimensional shape), their dynamics (motion), their photometry (material and light), and their identity (recognition)

Robotics. Translation of a high-level command, such as picking up a particular object, into a sequence of low-level control signals that might move the joints of a robotic arm/hand combination to accomplish the task; often this involves using a computer vision system to locate objects and provide feedback

Machine learning. Study of the means by which a computer can automatically improve its performance on a task by acquiring knowledge about the domain

Parallel architecture. Design and programming of a machine with thousands or even millions of simple processing elements to produce intelligent behavior; the human brain is an example of such a machine

Computational Systems Biology

This field can be selected as a major or minor field for the Ph.D. in Computer Science.

Subject Matter and Course Offerings

Emphasis is on integrative computational and mathematical modeling methodologies, algorithms, and quantitative methods for life sciences applications, both basic and applied. Integrative here puts the focus on biological (or medical) systems (systems biology), that is, computational mathematical modeling and simulation approaches to biological systems. Research topics typically involve one or more of the following areas:

Integrated computational and biological approaches to organismic, cellular, and mechanism-level studies of biological, including biomedical, systems. Modeling and simulation of cancer and other disease processes: neural, neuroendocrine, immune, and metabolic systems

Pharmacokinetics (PK), pharmacodynamics (PD), and physiologically-based PK modeling (PBPK)

Optimization of clinical therapy models

Modeling methodology for life science research, including experiment design simulation and optimization

Software development for modeling and model selection, and for kinetic analysis of biological systems, with emphasis on expert systems, user-friendly interfaces and universally available world wide web based software systems

Integrated modeling and experimental research in physiology, pharmacology, biochemistry, genomics, bioinformatics and related fields, developing the interface between (theoretical) modeling and laboratory experimentation and data analysis

Computational cardiology

Genomics, proteomics, metabolomics, and microarray data modeling

Computer Networks

The computer networks field involves the study of computer networks of different types, in different media (wired, wireless), and for different applications. Besides the study of network architectures and protocols, this field also emphasizes distributed algorithms, distributed systems, and the ability to evaluate system performance at various levels of granularity (but principally at the systems level). In order to understand and predict systems behavior, mathematical models are pursued that lead to the evaluation of system throughput, response time, utilization of devices, flow of jobs and messages, bottlenecks, speedup, power, etc. In addition, students are taught to design and implement computer networks using formal design methodologies subject to appropriate cost and objective functions. The tools required to carry out this design include probability theory, queueing theory, distributed systems theory, mathematical programming, control theory, operating systems design, simulation methods, measurement tools, and heuristic design procedures. The outcome of these studies is provide the following:

An appropriate model of the computer system under study

An adequate (exact or approximate) analysis of the behavior of this model

The validation of the model as compared to simulation and/or measurement of the system

Interpretation of the analytical results in order to obtain behavioral patterns and key parameters of the system

Design methodology

Resource Allocation

A central problem in the design and evaluation of computer networks deals with the allocation of resources among competing demands (e.g., wireless channel bandwidth allocation to backlogged stations). In fact, resource allocation is a significant element in most of the technical (and nontechnical) problems we face today.

Most of our resource allocation problems arise from the unpredictability of the demand for the use of these resources, as well as from the fact that the resources are geographically distributed (as in computer networks). The computer networks field encounters such resource allocation problems in many forms and in many different computer system configurations. Our goal is to find allocation schemes that permit suitable concurrency in the use of devices (resources) so as to achieve efficiency and equitable allocation. A very popular approach in distributed systems is allocation on demand, as opposed to prescheduled allocation. On-demand allocation is found to be effective, since it takes advantage of statistical averaging effects. It comes in many forms in computer networks and is known by names such as asynchronous time division multiplexing, packet switching, frame relay, random access, and so forth.

Areas Included in the Computer Networks Field
Typical Systems Studied Tools Used

• Computer networks
• Packet switching
• Multiprogramming systems
• Parallel processing systems
• High-performance computers
• Distributed processing systems
• Time-shared systems
• Satellite and ground radio
packet switching systems
• Cellular radio systems
• Personal communication
networks

• Local-area networks
• Communication processors
• High-speed networks
• Photonic networks
• Neural networks
• Communication protocols
• Network control procedures
(centralized and distributed)
• Mobile networks

• Probability theory
• Queueing theory
• Queueing networks
• Graph theory
• Network flow theory
• Optimization theory
• Mathematical programming
• Heuristic design algorithms
• Simulation
• Distributed algorithms
• Measurement
• Information theory
• Control theory

Computer Science Theory

Computer science is in large measure concerned with information processing systems, their applications, and the corresponding problems of representation, transformation, and communication. The computer science fields are concerned with different aspects of such systems, and each has its own "theoretical component" with appropriate models for description and analysis, algorithms for solving the related problems, and mathematical tools. Thus in a certain sense "computer science theory" involves all of computer science and participates in all disciplines.

The term theoretical computer science has come to be applied nationally and intentionally to a certain body of knowledge emphasizing the interweaving themes of computability and algorithms , interpreted in the broadest sense. Under computability, one includes questions concerning which tasks can and cannot be performed by information systems of different types restricted in various ways, as well as the mathematical analysis of such systems, their computations, and the languages for communication with them. Under algorithms, one includes questions concerning (1) how a task can be performed efficiently under reasonable assumptions on available resources (e.g., time, storage, type of processor), (2) how efficiently a proposed system performs a task in terms of resources used, and (3) the limits on how efficiently a task can be performed. These questions are often addressed by first developing models of the relevant parts of an information processing system (e.g., the processors, their interconnections, their rules of operation, the means by which instructions are conveyed to the system, or the way the data is handled) or of the input/output behavior of the system as a whole. The properties of such models are studied both for their own interest and as tools for understanding the system and improving its performance or applications.

Emphasis of Computer Science Theory

• Design and analysis of algorithms
• Distributed and parallel algorithms
• Models for parallel and concurrent computation
• Online and randomized algorithms
• Computational complexity
• Automata and formal languages
• Cryptography and interactive proofs

Computer System Architecture

Computer system architecture deals with

The study of the structure and behavior of computer systems

The development of new algorithms and computing structures to be implemented in hardware, firmware, and software

The development of tools to enable system designers to describe, model, fabricate, and test highly complex computer systems

Computer systems are among the most complex systems ever developed and as such are the subject of intensive study. The computer architect must be able to define the functions to be provided by a computing system and the way in which they are implemented. Due to their complexity, computer systems must be decomposed into subsystems. This decomposition is carried out at several levels until the desired system can be composed from well-understood reusable hardware and software elements. One way to categorize these subsystems is by processor, memory, data transmission and interconnection, control, input/output, and operating system elements. The subsystems must be precisely specified and their interactions modeled and thoroughly understood before a system can be fabricated.

Properties of a well-engineered system include ease and efficiency of programming and behavior that is predictable to a user. Moreover, a well-engineered system is one that satisfies cost, performance, and reliability constraints.

A comprehensive set of courses is offered in the areas of advanced computer architecture, arithmetic processor systems, fault-tolerant systems, memory systems, operating systems, data communications, VLSI-based architectures, computer-aided design of VLSI circuits and systems, distributed computing, and parallel processing. The courses are intended to prepare students for advanced engineering and continuing research. Advanced courses are also offered to introduce students to research areas being pursued by the faculty.

The computer architecture field at UCLA offers strong emphasis on systems issues of design, performance modeling, and algorithms. Some of the areas of current interest are described below:

Fault-tolerant computing involves the design of systems that can continue operation in the presence of faults. This includes errors in specification, operator errors, software faults, and random failures of hardware components. Design techniques and modeling tools are being studied for several levels of system design, including specification, software fault-tolerance, and fault-tolerance techniques for VLSI.

Novel architectures encompass the study of computations which are performed in ways that are quite different than those used by conventional machines. Examples include various domain-specific architectures characterized by high computational rates, low power, and reconfigurable hardware implementations.

The study of high-performance processing algorithms deals with algorithms for very high-performance numerical processing. Techniques such as redundant-digit representations of number systems, fast arithmetic, and the use of highly parallel arrays of processing elements are studied with the goal of providing the extremely high processing speeds required in a number of upcoming computer applications.

The study of computational algorithms and structures deals with the relationship between computational algorithms and the physical structures which can be employed to carry them out. It includes the study of interconnection networks, and the way that algorithms can be formulated for efficient implementation where regularity of structure and simplicity of interconnections are required.

Computer-aided design of VLSI circuits is an active research area which develops techniques for the automated synthesis of large-scale systems. Topics include logic synthesis, physical design, testing, and yield enhancement for various VLSI technologies such as standard cells, gate arrays, field programmable gate arrays (FPGAs), and multichip modules (MCMs). Other areas of study include a structural theory of the large-scale global optimizations which arise in VLSI CAD.

VLSI architectures and implementation is an area of current interest and collaboration between the Electrical Engineering and Computer Science Departments that addresses the impact of large-scale integration on the issues of computer architecture. In addition to detailed studies of these issues there is an active program in the design of MOS large-scale integrated circuits.

Information and Data Management

The information and data management field focuses on basic problems of modeling and managing data and knowledge, and their relation with other fundamental areas of computer science, such as operating systems and networking, programming languages, and human-computer interface design.

A data management system embodies a collection of data, devices in which the data are stored, and logic or programs used to manipulate that data. Information management is a generalization of data management in which the "data" being stored are permitted to be arbitrarily complex data structures, such as rules and trees. In addition, information management goes beyond simple data manipulation and query, and includes inference mechanisms, explanation facilities, and support for distributed and web-based access.

The need for rapid, accurate information is pervasive in all aspects of modern life. Modern systems are based on the coordination and integration of multiple

levels of data representation, from characteristics of storage devices to conceptual and abstract levels. As human enterprises have become more complex, involving more complicated decisions and trade-offs among decisions, the need for sophisticated information and data management has become essential.

Software Systems

The programming languages and systems field is concerned with the study of theory and practice in the development of software systems. Well-engineered systems require appreciation of both principles and architectural trade-offs. Principles provide abstractions and rigor that lead to clean designs, while systems-level understanding is essential for effective design.

Principles here encompass the use of programming systems to achieve specified goals, the identification of useful programming abstractions or paradigms, the development of comprehensive models of software systems, and so forth. The thrust is to identify and clarify concepts that apply in many programming contexts.

Development of software systems requires an understanding of many methodological and architectural issues. The complex systems developed today rely on concepts and lessons that have been extracted from years of research on programming languages, operating systems, database systems, knowledge-based systems, real-time systems, and distributed and parallel systems.

Facilities

Departmental laboratory facilities for instruction and research include:

Artificial Intelligence Laboratories

Artificial Intelligence Laboratory

The Artificial Intelligence Laboratory is used for investigating knowledge representation systems, pattern recognition, expert systems, intelligent user agents, planning, problem solving, heuristic search, and related areas.

Cognitive Systems Laboratory

The Cognitive Systems Laboratory is used for studying systems that emulate human cognition, especially learning, planning, and reasoning under uncertainty. Topics include causal reasoning, knowledge discovery, knowledge compilation, physical systems diagnosis, and automated explanation. See http://singapore.cs.ucla.edu.

Collaborative Design Laboratory

The Collaborative Design Laboratory is used for investigating methods for effective computer support of small teams involved in design and research.

UCLA Vision Laboratory

The UCLA Vision Laboratory is used for computer vision research, in particular the processing of sensory information to retrieve mathematical models of the environment in order for machines to interact with it. Applications include shape analysis, visual motion analysis, visual recognition, 3-D reconstruction, and vision-based control (for instance, autonomous vehicle navigation). See http://vision.ucla.edu.

Computational System Biology Laboratories

Biocybernetics Laboratory

The Biocybernetics Laboratory emphasizes integrative, interdisciplinary computational biology and experimentation in life sciences, medicine, physiology, and pharmacology. Laboratory pedagogy involves development and exploitation of the synergistic and methodologic interface between modeling and laboratory data and experimentation, and integrated approaches for solving complex biosystem problems from sparse biodata. See http://biocyb.cs.ucla.edu.

Biomedical Engineering Laboratory

The Biomedical Engineering Laboratory was established jointly by HSSEAS and the School of Medicine to support courses and research projects in health care information systems, covering issues in user requirement specifications, image data processing and retrieval, feature abstraction, simulation and analysis, visualization, and systems integration.

Computational Cardiology Laboratory

The Computational Cardiology Laboratory is a computational laboratory for mathematical modeling and computer simulation of cardiac systems in normal and pathological conditions. The goals of laboratory researchers are two-fold: to find the mechanism of heart fibrillation, the main cause of sudden cardiac death; and to improve the efficiency of computer simulation by using parallel computer architecture with specially-developed numerical algorithms. All research is carried out in collaboration with the UCLA Cardiology Department.

Human/Computer Interface Laboratory

The Human/Computer Interface Laboratory focuses on the use of cognitive science concepts to design more reliable user-friendly interfaces with computer and communication systems and the modeling and visualization of scientific data. See http://www.cs.ucla.edu/hcip/.

MAGIX: Modeling Animation and Graphics Laboratory

The MAGIX: Modeling Animation and Graphics Laboratory is used for research on computer graphics, physics-based animation, robotics, and biomechanics. See http://www.Magix.ucla.edu.

Computer Networks Laboratories

CENS Systems Laboratory

The CENS Systems Laboratory is used for research on the architectural challenges posed by massively distributed, large-scale, physically coupled, and usually untethered and small-form-factor computing systems. Through prototype implementations and simulation, such issues as data diffusion protocols, localization, time synchronization, low-power wireless communications, and self-configuration are explored. See http://lecs.cs.ucla.edu.

Computer Communications Laboratory

The Computer Communications Laboratory is used for investigating local-area networks, packet-switching networks, and packet-radio networks.

High-Performance Internet Laboratory

The High-Performance Internet Laboratory is used for investigating high-performance quality of service (QoS) techniques in the Internet, including QoS routing in Internet domains, QoS fault-tolerant multicast, TCP congestion control, and gigabit network measurements. See http://www.cs.ucla.edu/NRL/hpi/.

Internet Research Laboratory

The Internet Research Laboratory is used for exploring the forefront of current Internet architecture and protocol development, including fault tolerance in large-scale distributed systems such as the Internet routing infrastructure, Internet distance measurement, scalable IP multicast delivery in absence of network multicast support, distributed Internet information discovery, and protocol design principles for large-scale self-organizing systems and their applications to sensor networking. See http://irl.cs.ucla.edu.

Wireless Adaptive Mobility Laboratory

The Wireless Adaptive Mobility Laboratory is used for investigating wireless local-area networks (with specific interest in ad-hoc networks, vehicular networks, and personal-area networks) and the interaction between wired and wireless network layers, middleware, and applications. Activities include protocol development, protocol analysis and simulation, and wireless testbed experiments. See http://www.cs.ucla.edu/NRL/wireless/.

Computer Science Theory Laboratories

Center for Information and Computation Security (CICS)

The Center for Information and Computation Security (CICS) promotes all aspects of research and education in cryptography and computer security. See http://www.cs.ucla.edu/security/.

Theory Laboratory

The Theory Laboratory is used for developing theoretical foundations for all areas of computer science. Activities include fundamental research into algorithms, computational complexity, distributed computing, cryptography, hardware and software security, quantum computing, biological computing, machine learning, and computational geometry.

Computer Systems Architecture Laboratories

Concurrent Systems Laboratory

The Concurrent Systems Laboratory is used for investigating the design, implementation, and evaluation of computer systems that use state-of-the-art technology to achieve high performance and high reliability. Projects involve both software and hardware, and often focus on parallel and distributed systems in the context of general-purpose as well as embedded applications. See http://www.cs.ucla.edu/csd/research/labs/csl/.

Digital Arithmetic and Reconfigurable Architecture Laboratory

The Digital Arithmetic and Reconfigurable Architecture Laboratory is used for fast digital arithmetic (theory, algorithms, and design) and numerically intensive computing on reconfigurable hardware. Research includes floating-point arithmetic, online arithmetic, application-specific architectures, and design tools. See http://arith.cs.ucla.edu

Embedded and Reconfigurable System Design Laboratory

The Embedded and Reconfigurable System Design Laboratory is used for studying reconfigurable cores in embedded systems that provide the required adaptability and reconfigurability, and the design and CAD aspects of low-power embedded systems. See http://er.cs.ucla.edu.

VLSI CAD Laboratory

The VLSI CAD Laboratory is used for computer-aided design of VLSI circuits and systems. Areas include high-level and logic-level synthesis, technology mapping, physical design, interconnect modeling and optimization of various VLSI technologies such as full-custom designs, standard cells, programmable logic devices (PLDs), multichip modules (MCMs), system-on-a-chip (SOCs), and system-in-a-package (SIPs). See http://cadlab.cs.ucla.edu.

Information and Data Management Laboratories

Data Mining Laboratory

The Data Mining Laboratory is used for extraction of patterns, anomalies, concepts, classification rules, and other forms of high-level relationships that are latent in large commercial and scientific databases. See http://dml.cs.ucla.edu/main.html.

Knowledge-Based Multimedia Medical Distributed Database Systems Laboratory

The Knowledge-Based Multimedia Medical Distributed Database Systems Laboratory is used for developing new methodologies to access multimedia (numeric, text, image/picture) data by content and feature rather than by artificial keys such as patient ID. See http://kme-www.cs.ucla.edu.

Multimedia Stream System Laboratory

The Multimedia Stream System Laboratory is used for investigation and development of stream-based data model constructs and the corresponding querying facilities in response to the growing requirements of advanced multimedia database applications. See http://www.Mmss.cs.ucla.edu.

Multimedia Systems Laboratory

The Multimedia Systems Laboratory is used for research on all aspects of multimedia: physical and logical modeling of multimedia objects, real-time delivery of continuous multimedia, operating systems and networking issues in multimedia systems, and development of multimedia courseware. See http://www.Mmsl.cs.ucla.edu.

UCLA Web Information Systems Laboratory

The UCLA Web Information Systems Laboratory is used for investigating Web-based information systems. The laboratory seeks to develop the enabling technology for such systems by integrating the Web with database systems. Current projects focus on the preservation and warehousing of XML and database information to support temporal queries on historical archives, and data systems management systems to support advanced queries and data mining applications on the massive streams of information that are continuously flowing through the Web. See http://wis.cs.ucla.edu.

Software Systems Laboratories

Compilers Laboratory

The Compilers Laboratory is used for research into compilers, embedded systems, and programming languages.

Distributed Simulation Laboratory

The Distributed Simulation Laboratory is used for research on operating system support and applications and utilization of special architectures such as the Intel Hypercube.

Laboratory for Advanced System Research

The Laboratory for Advanced System Research is used for developing advanced operating systems, distributed systems, and middleware and conducting research in systems security.

Parallel Computing Laboratory

The Parallel Computing Laboratory is used for research in scalable simulation, providing an efficient lightweight simulation language, as well as tools for large-scale parallel simulation on modern supercomputers. See http://pcl.cs.ucla.edu.

Software Systems Laboratory

The Software Systems Laboratory is used for research into the design, implementation, and evaluation of operating systems, networked systems, programming languages, and software engineering tools.

Some of these research laboratories also provide support for upper division and/or graduate courses.

Computing Resources

In summarizing the resources now available to conduct experimentally based research in the UCLA Computer Science Department, it is useful to identify the major components of the research environment: the departmental computing facility, other hardware and software systems, administrative structure, and technical support staff.

Hardware

Computing facilities range from large campus-operated supercomputers to a major local network of servers and workstations that are administered by the department computing facilities (DCF) or school network (SEASnet).

The departmental research network includes at least 30 Sun servers and shared workstations, on the school's own ethernet TCP/IP local network. A wide variety of peripheral equipment is also part of the facility, and many more research-group workstations share the network; the total number of machines exceeds 700, the majority running the UNIX operating system. The network consists of switched10/100/1000 ethernet to the desktop with a gigabit backbone connection. The department LAN is connected to the campus gigabit backbone. An 802.11b wireless network is also available to faculty, staff, and graduate students.

Administrative Structure

The central facilities and wide-area networking are operated by the campuswide Communications Technology Services. Access to the departmental and SEASnet machines is controlled so as to maximize the usefulness of these computers for education and research, but no direct charges are involved.

Technical Support Staff

The support staff consists of hardware and software specialists. The hardware laboratory supports network connections, configures routers, switches, and network monitoring tools. The software group administers the department UNIX servers, providing storage space and backup for department users.

Faculty Areas of Thesis Guidance

Professors

Rajive L. Bagrodia, Ph.D. (U. Texas, 1987)

Wireless networks, nomadic computing, parallel programming, performance evaluation of computer and communication systems

Alfonso F. Cardenas, Ph.D. (UCLA, 1969)

Database management, distributed heterogeneous and multimedia (text, image/picture, video, voice) systems, information systems planning and development methodologies, software engineering, medical informatics, legal and intellectual property issues

Wesley W. Chu, Ph.D. (Stanford, 1966)

Distributed computing, distributed database, memory management, computer communications, performance measurement and evaluation for distributed systems and multiaccess packet-switched systems

Jason (Jingsheng) Cong, Ph.D. (Illinois, 1990)

Computer-aided design of VLSI circuits, fault-tolerant design of VLSI systems, design and analysis of algorithms, computer architecture, reconfigurable computing

Adnan Y. Darwiche, Ph.D. (Stanford, 1993)

Knowledge representation and automated reasoning (symbolic and probabilistic), applications to diagnosis, prediction, planning, and verification

Joseph J. DiStefano III, Ph.D. (UCLA, 1966)*

Biocybernetics; computational systems biology; dynamic biosystems modeling, simulation, clinical therapy and experiment design optimization methodologies; pharmacokinetic (PK), pharmacodynamic (PD), and physiologically-based PK (PKPD) modeling; knowledge-based (expert) systems for life science research

Michael G. Dyer, Ph.D. (Yale, 1982)

Artificial intelligence; natural language processing; connectionist, cognitive, and animat-based modeling

Milos D. Ercegovac, Ph.D. (Illinois, 1975)

Application-specific architectures, digital computer arithmetic, digital design, low-power systems, reconfigurable systems

Deborah L. Estrin, Ph.D. (MIT, 1985)

Sensor networks, embedded network sensing, environmental monitoring, computer networks

Mario Gerla, Ph.D. (UCLA, 1973)

Wireless ad-hoc networks: MAC, routing and transport protocols, vehicular communications, peer-to-peer mobile networks, personal-area networks (Bluetooth and Zigbee), underwater sensor networks, Internet transport protocols (TCP, streaming), Internet path characterization, capacity and bandwidth estimates, analytic and simulation models for network and protocol performance evaluation

Sheila A. Greibach, Ph.D. (Harvard, 1963)

Theoretical computer science, computational complexity, program schemes and semantics, formal languages, automata, computability

Richard E. Korf, Ph.D. (Carnegie Mellon, 1983)

Problem solving, heuristic search, planning in artificial intelligence

Richard R. Muntz, Ph.D. (Princeton, 1969)

Multimedia systems, database systems, data mining

Rafail Ostrovsky, Ph.D. (MIT, 1992)**

Theoretical computer science, cryptography, complexity theory, randomization, network protocols, geometric algorithms, data mining

Jens Palsberg, Ph.D. (Aarhus U., Denmark, 1992)

Compilers, embedded systems, programming languages

D. Stott Parker, Jr., Ph.D. (Illinois, 1978)

Data mining, information modeling, scientific computing, bioinformatics, database and knowledge-based systems

Miodrag Potkonjak, Ph.D. (UC Berkeley, 1991)

Computer-aided analysis and synthesis of system level designs, behavioral synthesis, and interaction between high-performance application-specific computations and communications

Majid Sarrafzadeh, Ph.D. (Illinois, 1987)

Computer engineering, embedded systems, VLSI CAD, algorithms

Stefano Soatto, Ph.D. (Cal Tech, 1996)

Computer vision; shape analysis, motion analysis, texture analysis, 3-D reconstruction, vision-based control; computer graphics: image-based modeling and rendering; medical imaging: registration, segmentation, statistical shape analysis; autonomous systems: sensor-based control, planning non-linear filtering; human-computer interaction: vision-based interfaces, visibility, visualization

Carlo Zaniolo, Ph.D. (UCLA, 1976)

Knowledge bases and deductive databases, parallel execution of PROLOG programs, formal software specifications, distributed systems, artificial intelligence, and computational biology

Lixia Zhang, Ph.D. (MIT, 1989)

Computer network, data networking, network architectures and protocols

Professors Emeriti

Algirdas A. Avizienis, Ph.D. (Illinois, 1960)

Digital computer architecture and design, fault-tolerant computing, digital arithmetic

Bertram Bussell, Ph.D. (UCLA, 1962)

Computer systems architecture, interactive computer graphics

Jack W. Carlyle, Ph.D. (UC Berkeley, 1961)

Communication, computation theory and practice, algorithms and complexity, discrete system theory, developmental and probabilistic systems

Gerald Estrin, Ph.D. (Wisconsin, 1951)

Computer systems architecture, methodology and supporting tools for design of concurrent systems, automating design teamwork, restructurable architectures

Thelma Estrin, Ph.D. (Wisconsin, 1951)

Biomedical engineering, application of technology and computers to health care, computer methods in neuroscience, engineering education

Leonard Kleinrock, Ph.D. (MIT, 1963)

Computer networks, computer-communication systems, resource sharing and allocation, computer systems modeling analysis and design, queueing systems theory and applications, performance evaluation of congestion-prone systems, performance evaluation and design of distributed multiaccess packet-switching systems, wireless networks, mobile computing, nomadic computing, and distributed and parallel processing systems

Allen Klinger, Ph.D. (UC Berkeley, 1966)

Pattern recognition, picture processing, biomedical applications, mathematical modeling

Lawrence P. McNamee, Ph.D. (Pittsburgh, 1964)

Computer graphics, discrete simulation, digital filtering, computer-aided design, LSI fabrication techniques, printed circuit board design

Michel A. Melkanoff, Ph.D. (UCLA, 1955)

Programming languages, data structures, database design, relational models, simulation systems, robotics, computer-aided design and manufacturing, numerical-controlled machinery

Judea Pearl, Ph.D. (Polytechnic Institute of Brooklyn, 1965)

Artificial intelligence, philosophy of science, reasoning under uncertainty, causal inference, causal and counterfactual analysis

Jacques J. Vidal, Ph.D. (U. Paris, Sorbonne, 1961)***

Information processing in biological systems, with emphasis on neuroscience, cybernetics, online laboratory computer systems, and pattern recognition, analog and hybrid systems/signal processing

Associate Professors

Eliezer M. Gafni, Ph.D. (MIT, 1982)

Computer communication, networks, mathematical programming algorithms

Songwu Lu, Ph.D. (Illinois, 1999)

Integrated-service support over heterogeneous networks, e.g. mobile computing environments, Internet and Activenet: networking and computing, wireless communications and networks, computer communication networks, dynamic game theory, dynamic systems, neural networks, and information economics

David A. Rennels, Ph.D. (UCLA, 1973)

Digital computer architecture and design, fault-tolerant computing, digital arithmetic

Yuval Tamir, Ph.D. (UC Berkeley, 1985)

Computer systems, computer architecture, software systems, parallel and distributed systems, dependable systems, cluster computing, reliable network services, interconnection networks and switches, multi-core architectures, reconfigurable systems

Song-Chun Zhu, Ph.D. (Harvard, 1996)

Computer vision, statistical modeling and computing, vision and visual arts

Assistant Professors

Junghoo (John) Cho, Ph.D. (Stanford, 2002)

Databases, web technologies, information discovery and integration

Petros Faloutsos, Ph.D. (Toronto, 2002)

Computer graphics, computer animation

Edward Kohler, Ph.D. (MIT, 2001)

Operating systems, software systems, programming languages and systems, networking systems

Rupak Majumdar, Ph.D. (UC Berkeley, 2003)

Computer-aided verification of hardware and software systems; logic and automata theory; embedded, hybrid, and probabilistic systems

Todd Millstein, Ph.D. (U. Washington, 2003)

Programming language design, static type systems, formal methods, software model checking, compilers

Glenn D. Reinman, Ph.D. (UC San Diego, 2001)

Microprocessor architecture, exploitation of instruction/thread/memory-level parallelism, power-efficient design, hardware/software co-design, multicore and multiprocessor design

Senior Lecturer

Leon Levine, M.S. (MIT, 1949), Emeritus

Computer methodology

Lecturers P.S.O.E.

Paul R. Eggert, Ph.D. (UCLA, 1980)

Programming languages, operating systems principles, compilers, Internet

David A. Smallberg, M.S. (UCLA, 1998)

Programming languages, software development

Adjunct Professors

Alan Kay, Ph.D. (Utah, 1969)

Smalltalk programming language, object-oriented programming, GUI, computers and technology in general

Boris Kogan, Ph.D. (Moscow, Russia, 1962)

Application of multiprocessor systems with massive parallelism to simulation of dynamic phenomena in excitable biological tissues

Gerald J. Popek, Ph.D. (Harvard, 1973)

Privacy and security in information systems, operating system software design, representation for design and evaluation of databases

M. Yahya "Medy" Sanadidi, Ph.D. (UCLA, 1982)

Computer networking, path characteristics estimation and applications in flow control, adaptive streaming and overlays design, probability models of computing systems, algorithms and networks

Adjunct Associate Professors

Leon Alkalai, Ph.D. (UCLA, 1989)

Computer architecture

Peter L. Reiher, Ph.D. (UCLA, 1987)

Computer and network security, ubiquitous computing, file systems, distributed systems

*Also Professor of Medicine
**Also Professor of Mathematics
***Member of Brain Research Institute

Lower Division Courses

1. Freshman Computer Science Seminar. (1)

Seminar, one hour; discussion, one hour. Introduction to department resources and principal topics and key ideas in computer science and computer engineering. Assignments given to bolster independent study and writing skills. Letter grading. Mr. Muntz (F)

2. Great Ideas in Computer Science. (4)

Lecture, four hours; outside study, eight hours. Broad coverage for liberal arts and social sciences students of computer science theory, technology, and implications, including artificial and neural machine intelligence, computability limits, virtual reality, cellular automata, artificial life, programming languages survey, and philosophical and societal implications. P/NP or letter grading. Mr. Dyer (Sp)

19. Fiat Lux Freshman Seminars. (1)

Seminar, one hour. Discussion of and critical thinking about topics of current intellectual importance, taught by faculty members in their areas of expertise and illuminating many paths of discovery at UCLA. P/NP grading.

31. Introduction to Computer Science I. (4)

Lecture, four hours; discussion, two hours; outside study, six hours. Introduction to computer science via theory, applications, and programming. Basic data types, operators and control structures. Input/output. Procedural and data abstraction. Introduction to object-oriented software development. Functions, recursion. Arrays, strings, pointers. Abstract data types, object-oriented programming. Examples and exercises from computer science theory and applications. Letter grading. Mr. Palsberg, Mr. Smallberg (F,W)

32. Introduction to Computer Science II. (4)

Lecture, four hours; discussion, two hours; outside study, six hours. Requisite: course 31. Object-oriented software development. Abstract data type definition and use. Overloading, inheritance, polymorphism. Object-oriented view of data structures: stacks, queues, lists. Algorithm analysis. Trees, graphs, and associated algorithms. Searching and sorting. Case studies and exercises from computer science applications. Letter grading. Mr. Palsberg, Mr. Smallberg (W,Sp)

33. Introduction to Computer Organization. (5)

Lecture, four hours; discussion, two hours; outside study, nine hours. Enforced requisite: course 32. Introductory course on computer architecture, assembly language, and operating systems fundamentals. Number systems, machine language, and assembly language. Procedure calls, stacks, interrupts, and traps. Assemblers, linkers, and loaders. Operating systems concepts: processes and process management, input/output (I/O) programming, memory management, file systems. Letter grading. Mr. Palsberg, Mr. Smallberg (F,Sp)

35L. Software Construction Laboratory. (2)

(Formerly numbered 35.) Laboratory, four hours; outside study, two hours. Requisite: course 31. Fundamentals of commonly used software tools and environments, particularly open-source tools to be used in upper division computer science courses. Letter grading. Mr. Eggert, Mr. Palsberg (F,W)

M51A. Logic Design of Digital Systems. (4)

(Same as Electrical Engineering M16.) Lecture, four hours; discussion, two hours; outside study, six hours. Introduction to digital systems. Specification and implementation of combinational and sequential systems. Standard logic modules and programmable logic arrays. Specification and implementation of algorithmic systems: data and control sections. Number systems and arithmetic algorithms. Error control codes for digital information. Letter grading. Mr. Ercegovac, Mr. Potkonjak (F,W,Sp)

99. Student Research Program. (1 to 2)

Tutorial (supervised research or other scholarly work), three hours per week per unit. Entry-level research for lower division students under guidance of faculty mentor. Students must be in good academic standing and enrolled in minimum of 12 units (excluding this course). Individual contract required; consult Undergraduate Research Center. May be repeated. P/NP grading.

Upper Division Courses

101. Upper Division Computer Science Seminar. (1)

Seminar, one hour. Introduction to current research, trends, emerging areas, and contemporary issues in computer science and engineering. Assignments given to bolster independent study and writing skills. Letter grading. Mr. Muntz (Sp)

111. Operating Systems Principles. (4)

Lecture, four hours; laboratory, two hours; outside study, six hours. Requisites: courses 32, 33. Introduction to operating systems design and evaluation. Computer software systems performance, robustness, and functionality. Kernel structure, bootstrapping, input/output (I/O) devices and interrupts. Processes and threads; address spaces, memory management, and virtual memory. Scheduling, synchronization. File systems: layout, performance, robustness. Distributed systems: networking, remote procedure call (RPC), asynchronous RPC, distributed file systems, transactions. Protection and security. Exercises involving applications using, and internals of, real-world operating systems. Letter grading. Mr. Eggert, Mr. Kohler (F,W,Sp)

112. Computer System Modeling Fundamentals. (4)

Lecture, four hours; outside study, eight hours. Requisite: Statistics 110A. Designed for juniors/seniors. Probability and stochastic process models as applied in computer science. Basic methodological tools include random variables, conditional probability, expectation and higher moments, Bayes theorem, Markov chains. Applications include probabilistic algorithms, evidential reasoning, analysis of algorithms and data structures, reliability, communication protocol and queueing models. Letter grading. Mr. Gerla, Mr. Muntz (F,W)

113. Introduction to Distributed Embedded Systems. (4)

Lecture, four hours; laboratory, four hours; outside study, four hours. Requisites: courses 111, 118. Introduction to basic concepts needed to understand, design, and implement wireless distributed embedded systems. Topics include design implications of energy and otherwise resource-constrained nodes, network self-configuration and adaptation, localization and time synchronization, applications, and usage issues such as human interfaces, safety, and security. Heavily project based. Letter grading. Ms. Estrin (W)

M117. Computer Networks: Physical Layer. (6)

(Formerly numbered 117.) (Same as Electrical Engineering M117.) Lecture, four hours; discussion, four hours; outside study, 10 hours. Not open to students with credit for course M171L. Introduction to fundamental data communication concepts underlying and supporting modern networks, with focus on physical and media access layers of network protocol stack. Systems include high-speed LANs (e.g., fast and giga Ethernet), optical DWDM (dense wavelength division multiplexing), time division SONET networks, wireless LANs (IEEE802.11), and ad hoc wireless and personal area networks (e.g., Bluetooth). Experimental laboratory sessions included. Letter grading. Mr. Gerla (W)

118. Computer Network Fundamentals. (4)

Lecture, four hours; discussion, two hours; outside study, six hours. Requisites: courses 32, 33. Highly recommended: course 111. Designed for juniors/seniors. Introduction to design and performance evaluation of computer networks, including such topics as what protocols are, layered network architecture, Internet protocol architecture, network applications, transport protocols, routing algorithms and protocols, internetworking, congestion control, and link layer protocols including Ethernet and wireless channels. Letter grading. Mr. Gerla, Ms. Zhang (F,W,Sp)

130. Software Engineering. (4)

Lecture, four hours; laboratory, two hours; outside study, six hours. Requisite: course 32. Recommended: Engineering 183 or 185. Structured programming, program specification, program proving, modularity, abstract data types, composite design, software tools, software control systems, program testing, team programming. Letter grading.

Mr. Eggert, Mr. Majumdar (W,Sp)

131. Programming Languages. (4)

Lecture, four hours; laboratory, two hours; outside study, six hours. Requisites: courses 32, 33. Basic concepts in design and use of programming languages, including abstraction, modularity, control mechanisms, types, declarations, syntax, and semantics. Study of several different language paradigms, including functional, object-oriented, and logic programming. Letter grading. Mr. Eggert, Mr. Millstein (F,W,Sp)

132. Compiler Construction. (4)

Lecture, four hours; discussion, two hours; outside study, six hours. Requisites: courses 32, 131, 181. Compiler structure; lexical and syntactic analysis; semantic analysis and code generation; theory of parsing. Letter grading. Mr. Eggert, Mr. Palsberg (F,W)

133. Parallel and Distributed Computing. (4)

Lecture, four hours; discussion, two hours; outside study, six hours. Requisites: courses 111 (may be taken concurrently), 131. Distributed memory and shared memory parallel architectures; asynchronous parallel languages: MPI, Maisie; primitives for parallel computation: specification of parallelism, interprocess communication and synchronization; design of parallel programs for scientific computation and distributed systems. Letter grading. Mr. Bagrodia (F)

143. Database Systems. (4)

Lecture, four hours; laboratory, two hours; outside study, six hours. Requisite: course 32. Information systems and database systems in enterprises. File organization and secondary storage structures. Relational model and relational database systems. Network, hierarchical, and other models. Query languages. Database design principles. Transactions, concurrency, and recovery. Integrity and authorization. Letter grading. Mr. Cardenas, Mr. Zaniolo (F,W)

M151B. Computer Systems Architecture. (4)

(Same as Electrical Engineering M116C.) Lecture, four hours; discussion, two hours; outside study, six hours. Requisites: courses 33, and M51A or Electrical Engineering M16. Recommended: courses 111, and M152A or Electrical Engineering M116L. Computer system organization and design, implementation of CPU datapath and control, instruction set design, memory hierarchy (caches, main memory, virtual memory) organization and management, input/output subsystems (bus structures, interrupts, DMA), performance evaluation, pipelined processors. Letter grading. Mr. Reinman, Mr. Tamir (F,Sp)

151C. Design of Digital Systems. (4)

Lecture, four hours; discussion, two hours. Requisites: courses M51A, M151B, M152A. Design of complex digital systems using hierarchal approaches and regular structures. Combinational, sequential, and algorithmic systems. Microprogramming and firmware engineering. Cost/performance measures and technology constraints. Use of design tools. Design project. Letter grading. Mr. Ercegovac (F, odd years)

M152A. Introductory Digital Design Laboratory. (2)

(Same as Electrical Engineering M116L.) Laboratory, four hours; outside study, two hours. Requisite: course M51A or Electrical Engineering M16. Hands-on design, implementation, and debugging of digital logic circuits, use of computer-aided design tools for schematic capture and simulation, implementation of complex circuits using programmed array logic, design projects. Letter grading. Mr. Sarrafzadeh (F,W,Sp)

M152B. Digital Design Project Laboratory. (4)

(Same as Electrical Engineering M116D.) Laboratory, four hours; discussion, two hours; outside study, six hours. Requisite: course M151B or Electrical Engineering M116C. Design and implementation of complex digital subsystems using field-programmable gate arrays (e.g., processors, special-purpose processors, device controllers, and input/output interfaces). Students work in teams to develop and implement designs and to document and give oral presentations of their work. Letter grading. Mr. Sarrafzadeh (F,W,Sp)

161. Fundamentals of Artificial Intelligence. (4)

Lecture, four hours; laboratory, two hours; outside study, six hours. Requisite: course 32. Introduction to fundamental problem solving and knowledge representation paradigms of artificial intelligence. Introduction to Lisp with regular programming assignments. State-space and problem reduction methods, brute-force and heuristic search, planning techniques, two-player games. Knowledge structures including predicate logic, production systems, semantic nets and primitives, frames, scripts. Special topics in natural language processing, expert systems, vision, and parallel architectures. Letter grading. Mr. Darwiche, Mr. Korf (F,W,Sp)

170A. Mathematical Modeling and Methods for Computer Science. (4)

Lecture, four hours; laboratory, two hours; outside study, six hours. Requisite: Mathematics 33B. Introduction to methods for modeling and simulation using interactive computing environments. Extensive coverage of methods for numeric and symbolic computation, matrix algebra, statistics, floating point, optimization, and spectral analysis. Emphasis on applications in simulation of physical systems. Letter grading. Mr. Parker (W)

M171L. Data Communication Systems Laboratory. (2 to 4)

(Same as Electrical Engineering M171L.) Laboratory, four to eight hours; outside study, two to four hours. Recommended preparation: course M152A. Limited to seniors. Interpretation of analog-signaling aspects of digital systems and data communications through experience in using contemporary test instruments to generate and display signals in relevant laboratory setups. Use of oscilloscopes, pulse and function generators, baseband spectrum analyzers, desktop computers, terminals, modems, PCs, and workstations in experiments on pulse transmission impairments, waveforms and their spectra, modem and terminal characteristics, and interfaces. Letter grading. Mr. Gerla (F,W,Sp)

174A. Introduction to Computer Graphics. (4)

(Formerly numbered 174.) Lecture, four hours; discussion, two hours. Requisite: course 32. Basic principles behind modern two- and three-dimensional computer graphics systems, including complete set of steps that modern graphics pipelines use to create realistic images in real time. How to position and manipulate objects in scene using geometric and camera transformations. How to create final image using perspective and orthographic transformations. Basics of modeling primitives such as polygonal models and implicit and parametric surfaces. Basic ideas behind color spaces, illumination models, shading, and texture mapping. Letter grading. Mr. Faloutsos, Mr. Soatto (F,W)

174B. Introduction to Computer Graphics: Three-Dimensional Photography and Rendering. (4)

Lecture, four hours; discussion, two hours. Requisite: course 174A. State of art in three-dimensional photography and image-based rendering. How to use cameras and light to capture shape and appearance of real objects and scenes. Process provides simple way to acquire three-dimensional models of unparalleled detail and realism. Applications of techniques from entertainment (reverse engineering and postprocessing of movies, generation of realistic synthetic objects and characters) to medicine (modeling of biological structures from imaging data), mixed reality (augmentation of video), and security (visual surveillance). Fundamental analytical tools for modeling and inferring geometric (shape) and photometric (reflectance, illumination) properties of objects and scenes, and for rendering and manipulating novel views. Letter grading. Mr. Faloutsos, Mr. Soatto (W)

C174C. Computer Animation. (4)

Lecture, four hours; discussion, two hours. Requisite: course 174A. Designed for juniors/seniors. Introduction to computer animation, including basic principles of character modeling, forward and inverse kinematics, forward and inverse dynamics, motion capture animation techniques, physics-based animation of particles and systems, and motor control. Concurrently scheduled with course C274C. Letter grading. Mr. Faloutsos (Sp, alternate years)

180. Introduction to Algorithms and Complexity. (4)

Lecture, four hours; discussion, two hours; outside study, six hours. Requisites: course 32, and Mathematics 61 or 113. Designed for junior/senior Computer Science majors. Introduction to design and analysis of algorithms. Design techniques: divide-and-conquer, greedy method, dynamic programming; selection of prototypical algorithms; choice of data structures and representations; complexity measures: time, space, upper, lower bounds, asymptotic complexity; NP-completeness. Letter grading. Mr. Gafni, Mr. Meyerson (F,W,Sp)

181. Introduction to Formal Languages and Automata Theory. (4)

Lecture, four hours; discussion, two hours; outside study, six hours. Requisites: course 32, and Mathematics 61 or 113. Designed for junior/senior Computer Science majors. Grammars, automata, and languages. Finite-state languages and finite-state automata. Context-free languages and pushdown story automata. Unrestricted rewriting systems, recursively enumerable and recursive languages, and Turing machines. Closure properties, pumping lemmas, and decision algorithms. Introduction to computability. Letter grading. Ms. Greibach, Mr. Ostrovsky, Mr. Sahai (F,W,Sp)

183. Introduction to Cryptography. (4)

Lecture, four hours; outside study, eight hours. Preparation: knowledge of basic probability theory. Requisite: course 180. Introduction to cryptography, computer security, and basic concepts and techniques. Topics include notions of hardness, one-way functions, hard-core bits, pseudorandom generators, pseudorandom functions and pseudorandom permutations, semantic security, public-key and private-key encryption, key-agreement, homomorphic encryption, private information retrieval and voting protocols, message authentication, digital signatures, interactive proofs, zero-knowledge proofs, collision-resistant hash functions, commitment protocols, and two-party secure computation with static security. Letter grading. Mr. Ostrovsky (W, odd years)

M186A. Introduction to Cybernetics, Biomodeling, and Biomedical Computing. (2)

(Formerly numbered M196A.) (Same as Biomedical Engineering M186A and Computational and Systems Biology M186A.) Lecture, two hours. Requisites: Mathematics 31A, 31B, Program in Computing 10A. Strongly recommended for students with potential interest in biomedical engineering/biocomputing fields or in Computational and Systems Biology as a major. Introduction and survey of topics in cybernetics, biomodeling, biocomputing, and related bioengineering disciplines. Lectures presented by faculty currently performing research in one of the areas; some sessions include laboratory tours. P/NP grading. Mr. DiStefano (F)

CM186B. Computational Systems Biology: Modeling and Simulation of Biological Systems. (5)

(Formerly numbered M186B.) (Same as Biomedical Engineering CM186B and Computational and Systems Biology M186B.) Lecture, four hours; laboratory, three hours. Corequisite: Electrical Engineering 102. Dynamic biosystems modeling and computer simulation methods for studying biological/biomedical processes and systems at multiple levels of organization. Control system, multicompartmental, predator-prey, pharmacokinetic (PK), pharmacodynamic (PD), and other structural modeling methods applied to life sciences problems at molecular, cellular (biochemical pathways/networks), organ, and organismic levels. Both theory- and data-driven modeling, with focus on translating biomodeling goals and data into mathematics models and implementing them for simulation and analysis. Basics of numerical simulation algorithms, with modeling software exercises in class and PC laboratory assignments. Concurrently scheduled with course CM286B. Letter grading. Mr. DiStefano (F)

CM186L. Biomedical Systems/Biocybernetics Research Laboratory. (2 to 4)

(Formerly numbered CM196L.) (Same as Biomedical Engineering CM186L and Computational and Systems Biology M186L.) Laboratory, four hours. Requisite: course CM186B. Special laboratory techniques and experience in biocybernetics research. Laboratory instruments, their use, design, and/or modification for research in life sciences. Special research hardware, firmware, software. Use of simulation in experimental laboratory. Laboratory automation and safety. Comprehensive experiment design. Radioactive isotopes and kinetic studies. Experimental animals, controls. Concurrently scheduled with course CM286L. Letter grading. Mr. DiStefano (Sp)

188. Special Courses in Computer Science. (4)

(Formerly numbered 198.) Lecture, four hours; outside study, eight hours. Special topics in computer science for undergraduate students that are taught on experimental or temporary basis, such as those taught by resident and visiting faculty members. May be repeated once for credit with topic or instructor change. Letter grading.

194. Research Group Seminars: Computer Science. (4)

Seminar, four hours; outside study, eight hours. Designed for undergraduate students who are part of research group. Discussion of research methods and current literature in field or of research of faculty members or students. Letter grading. (F,W,Sp)

199. Directed Research in Computer Science. (2 to 8)

Tutorial, to be arranged. Limited to juniors/seniors. Supervised individual research or investigation under guidance of faculty mentor. Culminating paper or project required. May be repeated for credit with school approval. Individual contract required; enrollment petitions available in Office of Academic and Student Affairs. Letter grading. (F,W,Sp)

Graduate Courses

201. Computer Science Seminar. (2)

Seminar, four hours; outside study, two hours. Designed for graduate computer science students. Seminars on current research topics in computer science. May be repeated for credit. S/U grading. (F,W,Sp)

202. Advanced Computer Science Seminar. (4)

Seminar, four hours; outside study, eight hours. Preparation: completion of major field examination in computer science. Current computer science research into theory of, analysis and synthesis of, and applications of information processing systems. Each member completes one tutorial and one or more original pieces of work in the specialized area. May be repeated for credit. Letter grading. Ms. Estrin (F,W,Sp)

211. Network Protocol and Systems Software Design for Wireless and Mobile Internet. (4)

Lecture, four hours; outside study, eight hours. Requisite: course 118. Designed for graduate students. In-depth study of network protocol and systems software design in area of wireless and mobile Internet. Topics include (1) networking fundamentals: design philosophy of TCP/IP, end-to-end arguments, and protocol design principles, (2) networking protocols: 802.11 MAC standard, packet scheduling, mobile IP, ad hoc routing, and wireless TCP, (3) mobile computing systems software: middleware, file system, services, and applications, and (4) topical studies: energy-efficient design, security, location management, and quality of service. Letter grading. Mr. Lu (F)

212A. Queueing Systems Theory. (4)

Lecture, four hours; outside study, eight hours. Requisites: course 112, Electrical Engineering 131A. Resource sharing issues and theory of queueing (waiting-line) systems. Review of Markov chains and baby queueing theory. Method of stages. M/E r /1. E r /M/1. Bulk arrival and bulk service systems. Series-parallel stages. Fundamentals of open and closed queueing networks. Intermediate queueing theory: M/G/1; G/M/m. Collective marks. Advanced queueing theory: G/G/1; Lindley integral equation; spectral solution. Inequalities, bounds, approximations. Letter grading. Mr. Gerla (W)

212B. Queueing Applications: Scheduling Algorithms and Queueing Networks. (4)

Lecture, four hours; outside study, eight hours. Requisite: course 212A. Priority queueing. Applications to time-sharing scheduling algorithms: FB, Round Robin, Conservation Law, Bounds. Queueing networks: definitions; job flow balance; product form solutions -- local balance, M→M; computational algorithms for performance measures; asymptotic behavior and bounds; approximation techniques -- diffusion -- iterative techniques; applications. Letter grading. Mr. Muntz

M213A. Embedded Systems. (4)

(Formerly numbered 213.) (Same as Electrical Engineering M202A.) Lecture, four hours; outside study, eight hours. Requisite: course 111. Designed for graduate computer science and electrical engineering students. Methodologies and technologies for design of embedded systems. Topics include hardware and software platforms for embedded systems, techniques for modeling and specification of system behavior, software organization, real-time operating system scheduling, real-time communication and packet scheduling, low-power battery and energy-aware system design, timing synchronization, fault tolerance and debugging, and techniques for hardware and software architecture optimization. Theoretical foundations as well as practical design methods. Letter grading. Mr. Potkonjak, Mr. Srivistava (F)

M213B. Distributed Embedded Systems. (4)

(Same as Electrical Engineering M202B.) Lecture, four hours; outside study, eight hours. Requisites: courses 111, and 118 or Electrical Engineering 132B. Designed for graduate computer science and electrical engineering students. Interdisciplinary course with focus on study of distributed embedded systems concepts needed to realize systems such as wireless sensor and actuator networks for monitoring and control of physical world. Topics include network self-configuration with localization and timing synchronization; energy-aware system design and operation; protocols for MAC, routing, transport, disruption tolerance; programming issues and models with language, OS, database, and middleware; in-network collaborative processing; fundamental characteristics such as coverage, connectivity, capacity, latency; techniques for exploitation and management of actuation and mobility; data and system integrity issues with calibration, faults, debugging, and security; and usage issues such as human interfaces and safety. S/U or letter grading. Ms. Estrin, Mr. Srivistava (F,Sp)

214. Data Transmission in Computer Communications. (4)

Lecture, four hours; outside study, eight hours. Requisite: course 112. Limited to graduate computer science students. Discrete data streams, formats, rates, transductions; digital data transmissions via analog signaling in computer communication; media characteristics, systems methodologies, performance analysis; modem designs; physical interfaces in computer communication links; national/international standards; tests and measurements. Letter grading. Mr. Carlyle

215. Computer Communications and Networks. (4)

Lecture, four hours; outside study, eight hours. Requisite: course 112. Resource sharing; computer traffic characterizations; multiplexing; network structure; packet switching and other switching techniques; ARPANET and other computer network examples; network delay and analysis; network design and optimization; network protocols; routing and flow control; satellite and ground radio packet switching; local networks; commercial network services and architectures. Optional topics include extended error control techniques; modems; SDLC, HDLC, X.25, etc.; protocol verification; network simulation and measurement; integrated networks; communication processors. Letter grading. Mr. Chu (F)

216. Distributed Multiaccess Control in Networks. (4)

Lecture, four hours; outside study, eight hours. Requisites: courses 212A, 215. Topics from the field of distributed control and access in computer networks, including terrestrial distributed computer networks; satellite packet switching; ground radio packet switching; local network architecture and control. Letter grading. Mr. Kleinrock (Sp)

217A. Internet Architecture and Protocols. (4)

Lecture, four hours; outside study, eight hours. Requisite: course 118. Focus on mastering existing core set of Internet protocols, including IP, core transport protocols, routing protocols, DNS, NTP, and security protocols such as DNSSEC, to understand principles behind design of these protocols, appreciate their design tradeoffs, and learn lessons from their operations. Letter grading. Ms. Zhang

217B. Advanced Topics in Internet Research. (4)

(Formerly numbered 217.) Lecture, four hours; outside study, eight hours. Requisite: course 217A. Designed for graduate students. Overview of Internet development history and fundamental principles underlying TCP/IP protocol design. Discussion of current Internet research topics, including latest research results in routing protocols, transport protocols, network measurements, network security protocols, and clean-slate approach to network architecture design. Fundamental issues in network protocol design and implementations. Letter grading. Ms. Zhang

218. Advanced Computer Networks. (4)

Lecture, four hours; outside study, eight hours. Requisites: courses 112, 118. Review of seven-layer ISO-OSI model. High-speed networks: LANs, MANs, ATM. Flow and congestion control; bandwidth allocation. Internetting. Letter grading. Mr. Gerla (W)

219. Current Topics in Computer System Modeling Analysis. (2 to 12)

Lecture, four hours; outside study, eight hours. Review of current literature in an area of computer system modeling analysis in which instructor has developed special proficiency as a consequence of research interests. Students report on selected topics. May be repeated for credit with consent of instructor. Letter grading.

M222. Control and Coordination in Economics. (4)

(Same as Economics M222A.) Lecture, three hours. Recommended preparation: appropriate mathematics course. Designed for graduate economics and engineering students. Stabilization policies, short- and long-run dynamics and stability analysis; decentralization, coordination in teams; certainty equivalence and separation theorems; stochastic and learning models. Bayesian approach to price and output rate adjustment. S/U or letter grading.

230A. Models of Information and Computation. (4)

Lecture, four hours; outside study, eight hours. Requisites: courses 131, 181. Paradigms, models, frameworks, and problem solving; UML and metamodeling; basic information and computation models; axiomatic systems; domain theory; least fixed point theory; well-founded induction. Logical models: sentences, axioms and rules, normal forms, derivation and proof, models and semantics, propositional logic, first-order logic, logic programming. Functional models: expressions, equations, evaluation; combinators; lambda calculus; functional programming. Program models: program derivation and verification using Hoare logic, object models, standard templates, design patterns, frameworks. Letter grading. Mr. Bagrodia, Mr. Parker, Mr. Zaniolo

231. Types and Programming Languages. (4)

Lecture, four hours. Requisite: course 131. Introduction to static type systems and their usage in programming language design and software reliability. Operational semantics, simply-typed lambda calculus, type soundness proofs, types for mutable references, types for exceptions. Parametric polymorphism, let-bound polymorphism, polymorphic type inference. Types for objects, subtyping, combining parametric polymorphism and subtyping. Types for modules, parameterized modules. Formal specification and implementation of variety of type systems, as well as readings from recent research literature on modern applications of type systems. Letter grading. Mr. Millstein (F)

232. Static Program Analysis. (4)

Lecture, four hours; outside study, eight hours. Requisite: course 132. Introduction to static analysis of object-oriented programs and its usage for optimization and bug finding. Class hierarchy analysis, rapid type analysis, equality-based analysis, subset-based analysis, flow-insensitive and flow-sensitive analysis, context-insensitive and context-sensitive analysis. Soundness proofs for static analyses. Efficient data structures for static analysis information such as directed graphs and binary decision diagrams. Flow-directed method inlining, type-safe method inlining, synchronization optimization, deadlock detection, security vulnerability detection. Formal specification and implementation of variety of static analyses, as well as readings from recent research literature on modern applications of static analysis. Letter grading. Mr. Palsberg (Sp)

233A. Parallel Programming. (4)

Lecture, four hours; outside study, eight hours. Requisites: courses 111, 131. Mutual exclusion and resource allocation in distributed systems; primitives for parallel computation: specification of parallelism, interprocess communication and synchronization, atomic actions, binary and multiway rendezvous; synchronous and asynchronous languages: CSP, Ada, Linda, Maisie, UC, and others; introduction to parallel program verification. Letter grading. Mr. Bagrodia

233B. Verification of Concurrent Programs. (4)

Lecture, four hours; outside study, eight hours. Requisite: course 233A. Formal techniques for verification of concurrent programs. Topics include safety, liveness, program and state assertion-based techniques, weakest precondition semantics, Hoare logic, temporal logic, UNITY, and axiomatic semantics for selected parallel languages. Letter grading. Mr. Bagrodia

234. Computer-Aided Verification. (4)

Lecture, four hours. Requisite: course 181. Introduction to theory and practice of formal methods for design and analysis of concurrent and embedded systems, with focus on algorithmic techniques for checking logical properties of hardware and software systems. Topics include semantics of reactive systems, invariant verification, temporal logic model checking, theory of omega automata, state-space reduction techniques, compositional and hierarchical reasoning. Letter grading. Mr. Majumdar (F)

235. Advanced Operating Systems. (4)

Lecture, four hours. Preparation: C or C++ programming experience. Requisite: course 111. In-depth investigation of operating systems issues through guided construction of research operating system for PC machines and consideration of recent literature. Memory management and protection, interrupts and traps, processes, interprocess communication, preemptive multitasking, file systems. Virtualization, networking, profiling, research operating systems. Series of laboratory projects, including extra challenge work. Letter grading. Mr. Kohler (F)

236. Computer Security. (4)

Lecture, four hours; outside study, eight hours. Requisites: courses 111, 118. Basic and research material on computer security. Topics include basic principles and goals of computer security, common security tools, use of cryptographic protocols for security, security tools (firewalls, virtual private networks, honeypots), virus and worm protection, security assurance and testing, design of secure programs, privacy, applying security principles to realistic problems, and new and emerging threats and security tools. Letter grading. Mr. Palsberg, Mr. Reiher (W)

239. Current Topics in Computer Science: Programming Languages and Systems. (2 to 12)

Lecture, four hours; outside study, eight hours. Review of current literature in an area of computer science programming languages and systems in which instructor has developed special proficiency as a consequence of research interests. May be repeated for credit with topic change. Letter grading.

240A. Databases and Knowledge Bases. (4)

Lecture, four hours; outside study, eight hours. Requisite: course 143. Theoretical and technological foundation of Intelligent Database Systems, which merge database technology, knowledge-based systems, and advanced programming environments. Rule-based knowledge representation, spatio-temporal reasoning, and logic-based declarative querying/programming are salient features of this technology. Other topics include object-relational systems and data mining techniques. Letter grading. Mr. Zaniolo (F)

240B. Advanced Data and Knowledge Bases. (4)

Lecture, four hours; outside study, eight hours. Requisites: courses 143, 240A. Logical models for data and knowledge representations. Rule-based languages and nonmonotonic reasoning. Temporal queries, spatial queries, and uncertainty in deductive databases and object relational databases (ORDBs). Abstract data types and user-defined column functions in ORDBs. Data mining algorithms. Semistructured information. Letter grading. Mr. Muntz, Mr. Parker, Mr. Zaniolo

241A. Object-Oriented and Semantic Database Systems. (4)

Lecture, three and one-half hours; discussion, 30 minutes; laboratory, one hour; outside study, seven hours. Requisite: course 143. Object database principles and requirements. Data models, accessing, and query languages. Object data management standards. Extended relational-object systems. Database systems architecture and functional components. Systems comparison. Commercial products. Database design, organization, indexing, and performance. Future directions. Other topics at discretion of instructor. Letter grading. Mr. Cardenas

241B. Pictorial and Multimedia Database Systems. (4)

Lecture, three and one-half hours; discussion, 30 minutes; laboratory, one hour; outside study, seven hours. Requisites: courses 143, 241A. Multimedia data: alphanumeric, long text, images/pictures, video, and voice. Multimedia information systems requirements. Data models and accessing. Querying, visual languages, and communication. Database design and organization, logical and physical. Search by content and indexing methods. Internet multimedia streaming. Data heterogeneity and distribution. Other topics at discretion of instructor. Letter grading. Mr. Cardenas

244A. Distributed Database Systems. (4)

Lecture, four hours; outside study, eight hours. Requisites: courses 215 and/or 241A. File allocation, intelligent directory design, transaction management, deadlock, strong and weak concurrency control, commit protocols, semantic query answering, multidatabase systems, fault recovery techniques, network partitioning, examples, trade-offs, and design experiences. Letter grading. Mr. Chu (Sp)

245A. Intelligent Information Systems. (4)

Lecture, four hours; outside study, eight hours. Requisites: courses 241A, 255A. Knowledge discovery in database, knowledge-base maintenance, knowledge-base and database integration architectures, and scale-up issues and applications to cooperative database systems, intelligent decision support systems, and intelligent planning and scheduling systems; computer architecture for processing large-scale knowledge-base/database systems. Letter grading. Mr. Chu

246. Web Information Management. (4)

Lecture, four hours; outside study, eight hours. Requisites: courses 112, 143, 180, 181. Designed for graduate students. Scale of Web data requires novel algorithms and principles for their management and retrieval. Study of Web characteristics and new management techniques needed to build computer systems suitable for Web environment. Topics include Web measuring techniques, large-scale data mining algorithms, efficient page refresh techniques, Web-search ranking algorithms, and query processing techniques on independent data sources. Letter grading. Mr. Cho (F)

249. Current Topics in Data Structures. (2 to 12)

Lecture, four hours; outside study, eight hours. Review of current literature in an area of data structures in which instructor has developed special proficiency as a consequence of research interests. Students report on selected topics. May be repeated for credit with consent of instructor. Letter grading.

251A. Advanced Computer Architecture. (4)

Lecture, four hours; outside study, eight hours. Requisite: course M151B. Recommended: course 111. Design and implementation of high-performance systems, advanced memory hierarchy techniques, static and dynamic pipelining, superscalar and VLIW processors, branch prediction, speculative execution, software support for instruction-level parallelism, simulation-based performance analysis and evaluation, state-of-the-art design examples, introduction to parallel architectures. Letter grading. Mr. Ercegovac, Mr. Tamir (F)

251B. Parallel Computer Architectures. (4)

Lecture, four hours; outside study, eight hours. Requisite: course M151B. Recommended: course 251A. SIMD and MIMD systems, symmetric multiprocessors, distributed-shared-memory systems, messages-passing systems, clusters, interconnection networks, user-level host-network interfaces, switching element design, communication primitives, cache coherency, memory consistency models, synchronization primitives, state-of-the-art design examples. Letter grading. Mr. Ercegovac, Mr. Tamir (W)

252A. Arithmetic Algorithms and Processors. (4)

Lecture, four hours; outside study, eight hours. Requisite: course 251A. Number systems: conventional, redundant, signed-digit, and residue. Types of algorithms and implementations. Complexity measures. Fast algorithms and implementations for two-operand addition, multioperand addition, multiplication, division, and square root. On-line arithmetic. Evaluation of transcendental functions. Floating-point arithmetic and numerical error control. Arithmetic error codes. Residue arithmetic. Examples of contemporary arithmetic ICs and processors. Letter grading. Mr. Ercegovac (F)

253A. Design of Fault-Tolerant Systems. (4)

Lecture, four hours; outside study, eight hours. Requisite or corequisite: course 251A. Fundamental concepts of dependable computing. Design methodology for fault-tolerant systems. Analytic models and measures, modeling tools. Design for critical applications: long-life, real-time, and high-availability systems. Tolerance of design faults: design diversity and fault-tolerant software. Letter grading. Mr. Rennels (W)

253C. Testing and Testable Design of VLSI Systems. (4)

Lecture, four hours; outside study, eight hours. Requisite: course M51A. Detailed study of various problems in testing and testable designs of VLSI systems, including fault modeling, fault simulation, testing for single stuck faults and multiple stuck faults, functional testing, design for testability, compression techniques, and built-in self-test. Letter grading. Mr. Cong

254A. Computer Memories and Memory Systems. (4)

Lecture, four hours; outside study, eight hours. Requisite: course 251A. Generic types of memory systems; control, access modes, hierarchies, and allocation algorithms. Characteristics, system organization, and device considerations of ferrite memories, thin film memories, and semiconductor memories. Letter grading. Mr. Chu, Mr. Rennels (Sp)

255A. Distributed Processing Systems. (4)

Lecture, four hours; outside study, eight hours. Requisites: courses 215 and/or 251A. Task partitioning and allocation, interprocess communications, task response time model, process scheduling, message passing protocols, replicated file systems, interface, cache memory, actor model, fine grain multicomputers, distributed operating system kernel, error recovery strategy, performance monitoring and measurement, scalability and maintainability, prototypes and commercial distributed systems. Letter grading. Mr. Chu (W)

256A. Advanced Scalable Architectures: Systems, Building Blocks, and Technology. (4)

Lecture, four hours; outside study, eight hours. Requisite: course 251A. State-of-the-art scalable multiprocessors and multicomputers. High-performance VLSI building blocks. Capabilities and limitations of VLSI technology. Interdependency among implementation technology, packaging, chip microarchitecture, and system architecture. Mechanisms for exploiting parallelism. Current research areas. Examples of chips and systems. Letter grading. Mr. Tamir (Sp)

M258A. Design of VLSI Circuits and Systems. (4)

(Same as Electrical Engineering M216A.) Lecture, four hours; discussion, one hour; laboratory, four hours; outside study, three hours. Requisites: course M51A or Electrical Engineering M16, and Electrical Engineering 115A. Recommended: Electrical Engineering 115C. LSI/VLSI design and application in computer systems. Fundamental design techniques that can be used to implement complex integrated systems on a chip. Letter grading. Mr. Rennels

M258B-M258C. LSI in Computer System Design. (4-4)

(Same as Electrical Engineering M216B-M216C.) Lecture, four hours; laboratory, four hours. Requisite: course M258A. LSI/VLSI design and application in computer systems. In-depth studies of VLSI architectures and VLSI design tools. In Progress (M258B) and S/U or letter (M258C) grading. Mr. Rennels

258E. Foundations of VLSI CAD Algorithms. (4)

Lecture, four hours; outside study, eight hours. Preparation: one course in analysis and design of algorithms. Basic theory of combinatorial optimization for VLSI physical layout, including mathematical programming, network flows, matching, greedy and heuristic algorithms, and stochastic methods. Emphasis on practical application to computer-aided physical design of VLSI circuits at high-level phases of layout: partitioning, placement, graph folding, floorplanning, and global routing. Letter grading. Mr. Kahng

258F. Physical Design Automation of VLSI Systems. (4)

Lecture, four hours; outside study, eight hours. Detailed study of various physical design automation problems of VLSI circuits, including logic partitioning, floorplanning, placement, global routing, channel and switchbox routing, planar routing and via minimization, compaction and performance-driven layout. Discussion of applications of a number of important optimization techniques, such as network flows, Steiner trees, simulated annealing, and generic algorithms. Letter grading. Mr. Cong (W)

258G. Logic Synthesis of Digital Systems. (4)

Lecture, four hours; outside study, eight hours. Requisites: courses M51A, 180. Detailed study of various problems in logic-level synthesis of VLSI digital systems, including two-level Boolean network optimization; multilevel Boolean network optimization; technology mapping for standard cell designs and field-programmable gate-array (FPGA) designs; retiming for sequential circuits; and applications of binary decision diagrams (BDDS). Letter grading. Mr. Cong

258H. Analysis and Design of High-Speed VLSI Interconnects. (4)

Lecture, four hours; outside study, eight hours. Requisites: courses M258A, 258F. Detailed study of various problems in analysis and design of high-speed VLSI interconnects at both integrated circuit (IC) and packing levels, including interconnect capacitance and resistance, lossless and lossy transmission lines, cross-talk and power distribution noise, delay models and power dissipation models, interconnect topology and geometry optimization, and clocking for high-speed systems. Letter grading. Mr. Cong

259. Current Topics in Computer Science: System Design/Architecture. (2 to 12)

Lecture, four hours; outside study, eight hours. Review of current literature in an area of computer science system design in which instructor has developed special proficiency as a consequence of research interests. Students report on selected topics. May be repeated for credit with topic change. Letter grading.

261A. Problem Solving and Search. (4)

Lecture, four hours; outside study, eight hours. Requisite: course 180. In-depth treatment of systematic problem-solving search algorithms in artificial intelligence, including problem spaces, brute-force search, heuristic search, linear-space algorithms, real-time search, heuristic evaluation functions, two-player games, and constraint-satisfaction problems. Letter grading. Mr. Korf (W)

262A. Reasoning with Partial Beliefs. (4)

Lecture, four hours; outside study, eight hours. Requisite: course 112 or Electrical Engineering 131A. Review of several formalisms for representing and managing uncertainty in reasoning systems; presentation of comprehensive description of Bayesian inference using belief networks representation. Letter grading. Mr. Pearl

262B. Knowledge-Based Systems. (4)

Lecture, four hours; outside study, eight hours. Requisite: course 262A. Machine representation of judgmental knowledge and uncertain relationships. Inference on inexact knowledge bases. Rule-based systems -- principles, advantages, and limitations. Signal understanding. Automated planning systems. Knowledge acquisition and explanation producing techniques. Letter grading. Mr. Pearl

M262C. Causal Inference. (4)

(Same as Statistics M241.) Lecture, four hours; outside study, eight hours. Requisite: course 112 or equivalent probability theory course. Techniques of using computers to interpret, summarize, and form theories of empirical observations. Mathematical analysis of trade-offs between computational complexity, storage requirements, and precision of computerized models. Letter grading. Mr. Pearl

262Z. Current Topics in Cognitive Systems. (4)

Lecture, four hours; outside study, eight hours. Requisite: course 262A. Additional requisites for each offering announced in advance by department. Theory and implementation of systems which emulate or support human reasoning. Current literature and individual studies in artificial intelligence, knowledge-based systems, decision support systems, computational psychology, and heuristic programming theory. May be repeated for credit with topic change. Letter grading. Mr. Pearl

263A. Language and Thought. (4)

Lecture, four hours; outside study, eight hours. Requisite: course 130 or 131 or 161. Introduction to natural language processing (NLP), with emphasis on semantics. Presentation of process models for variety of tasks, including question answering, paraphrasing, machine translation, word-sense disambiguation, narrative and editorial comprehension. Examination of both symbolic and statistical approaches to language processing and acquisition. Letter grading. Mr. Dyer

263B. Connectionist Natural Language Processing. (4)

Lecture, four hours; outside study, eight hours. Requisite: course 161 or 163 or 263A. Examination of connectionist/ANN architectures designed for natural language processing. Issues include localist vs. distributed representations, variable binding, instantiation and inference via spreading activation, acquisition of language and world knowledge (for instance, via back propagation in PDP networks and competitive learning in self-organizing feature maps), and grounding of symbols in sensory/motor experience. Letter grading. Mr. Dyer (Sp)

263C. Animats-Based Modeling. (4)

Lecture, four hours; outside study, eight hours. Requisite: course 130 or 131 or 161. Animats are mobile/sensing animal-like software agents embedded in simulated dynamic environments. Emphasis on modeling: goal-oriented behavior via neurocontrollers, adaptation via reinforcement learning, evolutionary programming. Animat-based tasks include foraging, mate finding, predation, navigation, predator avoidance, cooperative nest construction, communication, and parenting. Letter grading. Mr. Dyer (F)

264A. Automated Reasoning: Theory and Applications. (4)

Lecture, four hours; laboratory, four hours; outside study, four hours. Requisite: course 161. Introduction to theory and practice of automated reasoning using propositional and first-order logic. Topics include syntax and semantics of formal logic; algorithms for logical reasoning, including satisfiability and entailment; syntactic and semantic restrictions on knowledge bases; effect of these restrictions on expressiveness, compactness, and computational tractability; applications of automated reasoning to diagnosis, planning, design, formal verification, and reliability analysis. Letter grading. Mr. Darwiche (F)

265A. Machine Learning. (4)

Lecture, four hours; outside study, eight hours. Requisites: courses 263A, 264A. Introduction to machine learning. Learning by analogy, inductive learning, modeling creativity, learning by experience, role of episodic memory organization in learning. Examination of BACON, AM, Eurisko, HACKER, teachable production systems. Failure-driven learning. Letter grading. Mr. Dyer

267A. Neural Models. (4)

Lecture, four hours; outside study, eight hours. Designed for graduate students. Review of major neurophysiological milestones in understanding brain architecture and processes. Focus on brain theories that are important for modern computer science and, in particular, on models of sensory perception, sensory-motor coordination, and cerebellar and cerebral structure and function. Students required to prepare a paper analyzing research in one area of interest. Letter grading. Mr. Vidal

267B. Artificial Neural Systems and Connectionist Computing. (4)

Lecture, four hours; outside study, eight hours. Designed for graduate students. Analysis of major connectionist computing paradigms and underlying models of biological and physical processes. Examination of past and current implementations of artificial neural networks along with their applications to associative knowledge processing, general multisensor pattern recognition including speed and vision, and adaptive robot control. Students required to prepare a paper analyzing research in one area of interest. Letter grading. Mr. Vidal

268. Machine Perception. (4)

Lecture, four hours; outside study, eight hours. Designed for graduate students. Computational aspects of processing visual and other sensory information. Unified treatment of early vision in man and machine. Integration of symbolic and iconic representations in process of image segmentation. Computing multimodal sensory information by "neural-net" architectures. Letter grading. Mr. Dyer

268S. Seminar: Computational Neuroscience. (2)

Seminar, two hours; outside study, six hours. Designed for students undertaking thesis research. Discussion of advanced topics and current research in computational neuroscience. Neural networks and connectionism as a paradigm for parallel and concurrent computation in application to problems of perception, vision, multimodal sensory integration, and robotics. May be repeated for credit. S/U grading.

269. Seminar: Current Topics in Artificial Intelligence. (2 to 4)

Seminar, to be arranged. Review of current literature and research practicum in an area of artificial intelligence in which instructor has developed special proficiency as a consequence of research interests. Students report on selected topics. May be repeated for credit with topic change. Letter grading.

270A. Computer Methodology: Advanced Numerical Methods. (4)

Lecture, four hours; outside study, eight hours. Requisite: Electrical Engineering 103 or Mathematics 151B or comparable experience with numerical computing. Designed for graduate computer science and engineering students. Principles of computer treatment of selected numerical problems in algebraic and differential systems, transforms and spectra, data acquisition and reduction; emphasis on concepts pertinent to modeling and simulation and the applicability of contemporary developments in numerical software. Computer exercises. Letter grading. Mr. Carlyle (F)

271A. Modeling and Simulation of Lumped Parameter Systems. (4)

Lecture, eight hours. Recommended preparation: course 270A. Characterization of electrical, electromechanical, and other engineering problems by systems of nonlinear ordinary differential equations. Survey of integration algorithms. Digital simulation languages for continuous systems. Real-time simulation using array processor and multiprocessor computer systems. Letter grading. (W)

271B. Modeling and Simulation of Distributed Parameter Systems. (4)

Lecture, eight hours. Recommended preparation: course 270A. Mathematical formulation of engineering field problems governed by partial differential equations. Finite difference and finite element approximations. Principal algorithms for solving elliptic, parabolic, and hyperbolic partial differential equations. Supercomputers, vector processors, multiprocessors, and array processors. Letter grading. (Sp)

271C. Seminar: Advanced Simulation Methods. (2)

Seminar, two hours; outside study, six hours. Requisite: course 271A. Discussion of advanced topics in simulation of systems characterized by ordinary and partial differential equations. Topics include (among others) simulation languages, dataflow machines, array processors, and advanced mathematical modeling techniques. Topics vary each term. May be repeated for credit. S/U grading.

272. Advanced Discrete Event Simulation and Modeling Techniques. (4)

Lecture, four hours; outside study, eight hours. In-depth study in discrete event simulation and modeling techniques, including building valid and credible simulation models, output analysis of systems, comparisons of alternative system configurations. Variance reduction techniques, simulation models of computer systems and manufacturing systems. Letter grading.

273A. Digital Processing of Engineering and Statistical Data. (4)

Lecture, four hours; outside study, eight hours. Computer methods for processing engineering and statistical data. Algorithms to evaluate recursive filter functions, Fourier series, power spectral, analysis correlation computations, and statistical testing. Letter grading.

C274C. Computer Animation. (4)

Lecture, four hours; recitation, two hours. Requisite: course 174A. Introduction to computer animation, including basic principles of character modeling, forward and inverse kinematics, forward and inverse dynamics, motion capture animation techniques, physics-based animation of particles and systems, and motor control. Concurrently scheduled with course C174C. Letter grading. Mr. Faloutsos (Sp, alternate years)

M276A. Pattern Recognition and Machine Learning. (4)

(Formerly numbered 276A.) (Same as Statistics M231.) Lecture, three hours. Designed for graduate students. Fundamental concepts, theories, and algorithms for pattern recognition and machine learning that are used in computer vision, image processing, speech recognition, data mining, statistics, and computational biology. Topics include Bayesian decision theory, parametric and nonparametric learning, clustering, complexity (VC-dimension, MDL, AIC), PCA/ICA/TCA, MDS, SVM, boosting. S/U or letter grading. Mr. Zhu

276B. Structured Computer Vision. (4)

Lecture, four hours; outside study, eight hours. Designed for graduate students. Methods for computer processing of image data. Systems, concepts, and algorithms for image analysis, radiologic and robotic applications. Letter grading. Mr. Klinger

276C. Speech and Language Communication in Artificial Intelligence. (4)

Lecture, four hours; outside study, eight hours. Requisite: course M276A or 276B. Topics in human-computer communication: interaction with pictorial information systems, sound and symbol generation by humans and machines, semantics of data, systems for speech recognition and understanding. Use of speech and text for computer input and output in applications. Letter grading. Mr. Klinger

279. Current Topics in Computer Science: Methodology. (2 to 12)

Lecture, four hours; outside study, eight hours. Review of current literature in an area of computer science methodology in which instructor has developed special proficiency as a consequence of research interests. Students report on selected topics. May be repeated for credit with topic change. Letter grading. (F,W,Sp)

280A-280ZZ. Algorithms. (4 each)

Lecture, four hours; outside study, eight hours. Requisite: course 180. Additional requisites for each offering announced in advance by department. Selections from design, analysis, optimization, and implementation of algorithms; computational complexity and general theory of algorithms; algorithms for particular application areas. Subtitles of some current sections: Principles of Design and Analysis (280A); Distributed Algorithms (280D); Graphs and Networks (280G). May be repeated for credit with consent of instructor and with topic change. Letter grading:

280AP. Approximation Algorithms. (4) Lecture, four hours; outside study, eight hours. Requisite: course 180. Background in discrete mathematics helpful. Theoretically sound techniques for dealing with NP-Hard problems. Inability to solve these problems efficiently means algorithmic techniques are based on approximation -- finding solution that is near to best possible in efficient running time. Coverage of approximation techniques for number of different problems, with algorithm design techniques that include primal-dual method, linear program rounding, greedy algorithms, and local search. Letter grading. Mr. Meyerson (F)

281A. Computability and Complexity. (4)

Lecture, four hours; outside study, eight hours. Requisite: course 181 or compatible background. Concepts fundamental to study of discrete information systems and theory of computing, with emphasis on regular sets of strings, Turing-recognizable (recursively enumerable) sets, closure properties, machine characterizations, nondeterminisms, decidability, unsolvable problems, "easy" and "hard" problems, PTIME/NPTIME. Letter grading. Ms. Greibach, Mr. Parker

281D. Discrete State Systems. (4)

Lecture, four hours; outside study, eight hours. Recommended requisite: course 181. Finite-state machines, transducers, and their generalizations; regular expressions, transduction expressions, realizability; decomposition, synthesis, and design considerations; topics in state and system identification and fault diagnosis, linear machines, probabilistic machines, applications in coding, communication, computing, system modeling, and simulation. Letter grading. Mr. Carlyle

M282A. Cryptography. (4)

(Formerly numbered 282A.) (Same as Mathematics M209A.) Lecture, four hours; outside study, eight hours. Introduction to theory of cryptography, stressing rigorous definitions and proofs of security. Topics include notions of hardness, one-way functions, hard-core bits, pseudorandom generators, pseudorandom functions and pseudorandom permutations, semantic security, public-key and private-key encryption, secret-sharing, message authentication, digital signatures, interactive proofs, zero-knowledge proofs, collision-resistant hash functions, commitment protocols, key-agreement, contract signing, and two-party secure computation with static security. Letter grading. Mr. Ostrovsky (W)

M282B. Cryptographic Protocols. (4)

(Formerly numbered 282B.) (Same as Mathematics M209B.) Lecture, four hours; outside study, eight hours. Requisite: course M282A. Consideration of advanced cryptographic protocol design and analysis. Topics include noninteractive zero-knowledge proofs; zero-knowledge arguments; concurrent and non-black-box zero-knowledge; IP=PSPACE proof, stronger notions of security for public-key encryption, including chosen-ciphertext security; secure multiparty computation; dealing with dynamic adversary; nonmalleability and composability of secure protocols; software protection; threshold cryptography; identity-based cryptography; private information retrieval; protection against man-in-middle attacks; voting protocols; identification protocols; digital cash schemes; lower bounds on use of cryptographic primitives, software obfuscation. May be repeated for credit with topic change. Letter grading. Mr. Ostrovsky (W)

M283A-M283B. Topics in Applied Number Theory. (4-4)

(Same as Mathematics M208A-M208B.) Lecture, three hours. Basic number theory, including congruences and prime numbers. Cryptography: public-key and discrete log cryptosystems. Attacks on cryptosystems. Primality testing and factorization methods. Elliptic curve methods. Topics from coding theory: Hamming codes, cyclic codes, Gilbert/Varshamov bounds, Shannon theorem. S/U or letter grading.

284A-284ZZ. Topics in Automata and Languages. (4 each)

Lecture, four hours; outside study, eight hours. Requisite: course 181. Additional requisites for each offering announced in advance by department. Selections from families of formal languages, grammars, machines, operators; pushdown automata, context-free languages and their generalizations, parsing; multidimensional grammars, developmental systems; machine-based complexity. Subtitles of some current and planned sections: Context-Free Languages (284A), Parsing Algorithms (284P). May be repeated for credit with consent of instructor and with topic change. Letter grading. Ms. Greibach

CM286B. Computational Systems Biology: Modeling and Simulation of Biological Systems. (5)

(Same as Biomedical Engineering CM286B.) Lecture, four hours; laboratory, three hours. Corequisite: Electrical Engineering 102. Dynamic biosystems modeling and computer simulation methods for studying biological/biomedical processes and systems at multiple levels of organization. Control system, multicompartmental, predator-prey, pharmacokinetic (PK), pharmacodynamic (PD), and other structural modeling methods applied to life sciences problems at molecular, cellular (biochemical pathways/networks), organ, and organismic levels. Both theory- and data-driven modeling, with focus on translating biomodeling goals and data into mathematics models and implementing them for simulation and analysis. Basics of numerical simulation algorithms, with modeling software exercises in class and PC laboratory assignments. Concurrently scheduled with course CM186B. Letter grading. Mr. DiStefano (F)

CM286L. Biomedical Systems/Biocybernetics Research Laboratory. (2 to 4)

(Formerly numbered CM296L.) (Same as Biomedical Engineering CM286L.) Laboratory, four hours. Requisite: course CM286B. Special laboratory techniques and experience in biocybernetics research. Laboratory instruments, their use, design, and/or modification for research in life sciences. Special research hardware, firmware, software. Use of simulation in experimental laboratory. Laboratory automation and safety. Comprehensive experiment design. Radioactive isotopes and kinetic studies. Experimental animals, controls. Concurrently scheduled with course CM186L. Letter grading. Mr. DiStefano (Sp)

287A. Theory of Program Structure. (4)

Lecture, four hours; outside study, eight hours. Requisite: course 181. Models of computer programs and their syntax and semantics; emphasis on programs and recursion schemes; equivalence, optimization, correctness, and translatability of programs; expressive power of program constructs and data structures; selected current topics. Letter grading. Ms. Greibach

288S. Seminar: Theoretical Computer Science. (2)

Seminar, two hours; outside study, six hours. Requisites: courses 280A, 281A. Intended for students undertaking thesis research. Discussion of advanced topics and current research in such areas as algorithms and complexity models for parallel and concurrent computation, and formal language and automata theory. May be repeated for credit. S/U grading. Ms. Greibach (F,W,Sp)

289A-289ZZ. Current Topics in Computer Theory. (2 to 12 each)

Lecture, four hours; outside study, eight hours. Review of current literature in an area of computer theory in which instructor has developed special proficiency as a consequence of research interests. Students report on selected topics. Letter grading:

289CO. Complexity Theory. (4). Lecture, four hours; outside study, eight hours. Diagonalization, polynomial-time hierarchy, PCP theorem, randomness and de-randomization, circuit complexity, attempts and limitations to proving P does not equal NP, average-case complexity, one-way functions, hardness amplification. Problem sets and presentation of previous and original research related to course topics. Letter grading. Mr. Sahai (Sp)

289OA. Online Algorithms. (4) Lecture, four hours; outside study, eight hours. Requisite: course 180. Introduction to decision making under uncertainty and competitive analysis. Review of current research in online algorithms for problems arising in many areas, such as data and memory management, searching and navigating in unknown terrains, and server systems. Letter grading. Mr. Meyerson (Sp, alternate years)

289RA. Randomized Algorithms. (4) Lecture, four hours; outside study, eight hours. Basic concepts and design techniques for randomized algorithms, such as probability theory, Markov chains, random walks, and probabilistic method. Applications to randomized algorithms in data structures, graph theory, computational geometry, number theory, and parallel and distributed systems. Letter grading. Mr. Meyerson

M296A. Advanced Modeling Methodology for Dynamic Biomedical Systems. (4)

(Same as Biomedical Engineering M296A and Medicine M270C.) Lecture, four hours; outside study, eight hours. Requisite: Electrical Engineering 141 or 142 or Mathematics 115A or Mechanical and Aerospace Engineering 171A. Development of dynamic systems modeling methodology for physiological, biomedical, pharmacological, chemical, and related systems. Control system, multicompartmental, noncompartmental, and input/output models, linear and nonlinear. Emphasis on model applications, limitations, and relevance in biomedical sciences and other limited data environments. Problem solving in PC laboratory. Letter grading. Mr. DiStefano (F)

M296B. Optimal Parameter Estimation and Experiment Design for Biomedical Systems. (4)

(Same as Biomathematics M270, Biomedical Engineering M296B, and Medicine M270D.) Lecture, four hours; outside study, eight hours. Requisite: course M296A or Biomathematics 220. Estimation methodology and model parameter estimation algorithms for fitting dynamic system models to biomedical data. Model discrimination methods. Theory and algorithms for designing optimal experiments for developing and quantifying models, with special focus on optimal sampling schedule design for kinetic models. Exploration of PC software for model building and optimal experiment design via applications in physiology and pharmacology. Letter grading. Mr. DiStefano

M296C. Advanced Topics and Research in Biomedical Systems Modeling and Computing. (4)

(Same as Biomedical Engineering M296C and Medicine M270E.) Lecture, four hours; outside study, eight hours. Requisite: course M296A. Recommended: course M296B. Research techniques and experience on special topics involving models, modeling methods, and model/computing in biological and medical sciences. Review and critique of literature. Research problem searching and formulation. Approaches to solutions. Individual M.S.- and Ph.D.-level project training. Letter grading. Mr. DiStefano

M296D. Introduction to Computational Cardiology. (4)

(Same as Biomedical Engineering M296D.) Lecture, four hours; outside study, eight hours. Requisite: course CM186B. Introduction to mathematical modeling and computer simulation of cardiac electrophysiological process. Ionic models of action potential (AP). Theory of AP propagation in one-dimensional and two-dimensional cardiac tissue. Simulation on sequential and parallel supercomputers, choice of numerical algorithms, to optimize accuracy and to provide computational stability. Letter grading. Mr. DiStefano, Mr. Kogan (Sp)

298. Research Seminar: Computer Science. (2 to 4)

Seminar, two to four hours; outside study, four to eight hours. Designed for graduate computer science students. Discussion of advanced topics and current research in algorithmic processes that describe and transform information: theory, analysis, design, efficiency, implementation, and application. May be repeated for credit. S/U grading. (F,W,Sp)

375. Teaching Apprentice Practicum. (1 to 4)

Seminar, to be arranged. Preparation: apprentice personnel employment as teaching assistant, associate, or fellow. Teaching apprenticeship under active guidance and supervision of regular faculty member responsible for curriculum and instruction at the University. May be repeated for credit. S/U grading. (F,W,Sp)

495. Teaching Assistant Training Seminar. (2)

Seminar, two hours; outside study, six hours. Limited to graduate Computer Science Department students. Seminar on communication of computer science materials in classroom: preparation, organization of material, presentation, use of visual aids, grading, advising, and rapport with students. S/U grading.

495B. Teaching with Technology. (2)

Seminar, two hours; outside study, four hours. Limited to graduate Computer Science Department teaching assistants. Seminar for teaching assistants covering how technology can be used to aid instruction in and out of classroom. S/U grading. Mr. Korf

497D-497E. Field Projects in Computer Science. (4-4)

Fieldwork, to be arranged. Students are divided into teams led by instructor; each team is assigned an external company or organization which they investigate as a candidate for possible computerization, submitting a team report of their findings and recommendations. In Progress (497D) and S/U or letter (497E) grading. Mr. Cardenas

596. Directed Individual or Tutorial Studies. (2 to 8)

Tutorial, to be arranged. Limited to graduate computer science students. Petition forms to request enrollment may be obtained from assistant dean, Graduate Studies. Supervised investigation of advanced technical problems. S/U grading.

597A. Preparation for M.S. Comprehensive Examination. (2 to 12)

Tutorial, to be arranged. Limited to graduate computer science students. Reading and preparation for M.S. comprehensive examination. S/U grading.

597B. Preparation for Ph.D. Preliminary Examinations. (2 to 16)

Tutorial, to be arranged. Limited to graduate computer science students. S/U grading.

597C. Preparation for Ph.D. Oral Qualifying Examination. (2 to 16)

Tutorial, to be arranged. Limited to graduate computer science students. Preparation for oral qualifying examination, including preliminary research on dissertation. S/U grading.

598. Research for and Preparation of M.S. Thesis. (2 to 12)

Tutorial, to be arranged. Limited to graduate computer science students. Supervised independent research for M.S. candidates, including thesis prospectus. S/U grading.

599. Research for and Preparation of Ph.D. Dissertation. (2 to 16)

Tutorial, to be arranged. Limited to graduate computer science students. Petition forms to request enrollment may be obtained from assistant dean, Graduate Studies. S/U grading.