COMPUTER SCIENCE Emeriti: (Professors) George B. Dantzig, John G. Herriot Chair: Jeffrey D. Ullman Assistant Chair for Education: Eric S. Roberts Assistant Chair for External Relations and Graduate Studies: Carolyn E. Tajnai Professors: Edward A. Feigenbaum, Robert W. Floyd, Hector Garcia-Molina, Gene H. Golub, Leonidas J. Guibas, John Hennessy, Donald E. Knuth, Zohar Manna, John McCarthy, Edward J. McCluskey, William F. Miller, Nils J. Nilsson, Joseph E. Oliger, Vaughan Pratt, Jeffrey D. Ullman, Terry Winograd Associate Professors: David Cheriton, Michael Genesereth, Oussama Khatib, Jean-Claude Latombe, John Mitchell Assistant Professors: David Dill, Andrew Goldberg, Anoop Gupta, Monica Lam, Marc Levoy, Rajeev Motwani, Serge A. Plotkin, Mendel Rosenblum, Yoav Shoham, Andrew M. Stuart Professors (Research): Thomas Binford, Richard Fikes, Gio Wiederhold Associate Professors (Teaching): Charles A. Bigelow, Eric S. Roberts Courtesy Professors: Michael J. Flynn (Electrical Engineering), David E. Rumelhart (Psychology), Edward A. Shortliffe (Medicine), Fouad A. Tobagi (Electrical Engineering) Courtesy Associate Professors: Giovanni De Micheli (Electrical Engineering), John T. Gill, III (Electrical Engineering), Mark A. Horowitz (Electrical Engineering), Grigori Mints (Philosophy), Bernard M. Mont-Reynaud (Music-Research) Courtesy Assistant Professors: David Heeger (Psychology), Teresa Meng (Electrical Engineering), Mark A. Musen (Medicine) Affiliated Professor (Research): David Luckham (Electrical Engineering) Lecturers: James Finn, Allison L. Hansen, Nicholas J. Parlante Consulting Professors: Forest Baskett, Bruce A. Delagi, Richard P. Gabriel, Joseph Y. Halpern, Patrick J. Hayes, Joshua Lederberg, Douglas B. Lenat, Jussi A. Ketonen, Susan Owicki, Victor Pereyra, Stanley J. Rosenschein, Jay M. Tenenbaum, Moshe Vardi, Richard Waldinger Consulting Associate Professors: Robert B. Hagmann, John Koza Consulting Assistant Professor: Robert E. Cypher Five large computer systems at the Department of Computer Science (CS) play a major role in providing the computing environment for research and administration. Most course work and instruction is done on the systems available at L&IR (Libraries and Information Resources). Students in CS also have access to SUNET, the University-wide ethernet system, or to other systems through the nation-wide Internet. The five large systems are: XENON, a SUN 4/670 Muti-processor (4 CPUs) SunOS Release 4.1.2. This system is exclusively for student use as a primary "home base" machine for electronic mail and text processing. SUNBURN, a SUN4/490 running SunOS 4.1.1, is used for departmental administration. HOOKIPA, a Silicon Graphics multi-processor (8 CPUs) compute server, 4D380GTX, supports the Distributed Systems Group and the Numerical Analysis Group. SUMEX-AIM, a SUN 4/490 that supports research on knowledge-based systems and applications of artificial intelligence to biomedicine and engineering. Students doing research in the Knowledge Systems Laboratory may be granted access to the SUMEX system. SAIL, a DECserver 5000, supports research in AI and is used primarily by one of the AI groups. In addition, approximately 12 medium scale Unix operating systems are used by specific research projects at CS. The department also operates approximately 70 SUN workstations, 20 HP workstations, 25 AT&T 386WGS, 40 DEC Microvaxs, 30 DECstation 3100s, 10 NeXT machines, 100 Mac IIs, 5 Symbolics workstations, 35 TI Explorers, and 20 laser printers of various types, all of which are connected by an ethernet network. In addition, the department operates a Graphics Lab that consists of 10 SGI 4D/35TG Color Workstations. At present, students who are supported by research can receive an account on their sponsored machine. All CS students receive an account on XENON. UNDERGRADUATE PROGRAMS The department offers a degree in Computer Science, as outlined in the "School of Engineering" section of this bulletin. In addition, there are several inter-disciplinary degrees with a substantial computer science component. The Computer Systems Engineering major (also in Engineering) allows study of issues of both computer hardware and computer software, bridging the gap between traditional CS and Electrical Engineering majors. The Symbolic Systems major (in the School of Humanities and Sciences) offers a chance to explore computer science and its relation to philosophy, linguistics, and psychology. Finally, the Mathematical and Computational Sciences major (also Humanities and Sciences) allows students to explore computer science along with more mathematics, statistics, and operations research. GRADUATE PROGRAMS MASTER OF SCIENCE The University's basic requirements for the M.S. degree are discussed in the "Degrees" section in this bulletin. COMPUTER SCIENCE The M.S. degree is intended as a terminal professional degree and does not lead to the Ph.D. degree. Students planning to obtain the Ph.D. degree should apply directly for admission to the Ph.D. program. Applications for admission to the M.S. program, and all of the required supporting documents, must be received before December 31, 1992. Exceptions are made for applicants who are either Honors Co-op applicants or who are already students at Stanford (including co-terminal applicants). Information on these deadlines is available from the department. REQUIREMENTS A candidate is required to complete a program of 45 units. At least 36 of these must be graded units, passed with an average 3.0 (B) letter grade indicator (LGI) or better. The 45 units may include no more than 21 units of courses from those listed in Requirements 1 and 2. Thus, students needing to take more than seven of the courses listed in Requirements 1 and 2 actually complete more than 45 units of course work in this program. Only extremely well-prepared students may expect to finish the program in one year; most complete the program in six quarters. It is expected that an adequately prepared student admitted to the M.S. program will have taken a number of the "core" courses as an undergraduate. Students hoping to complete the program with 45 units should already have a good background in computer science, including course work or experience equivalent to all of Requirement 1 and some of the courses in Requirement 2. Requirement 1--The following courses may be needed as prerequisites for other courses in the program: CS 22 (for specialization 5 only), 107, 109A, 109B, 110, 112, 140, 145 (for specialization 6 only), 160; Math. 109 or 120. Requirement 2--The following "core" courses or their equivalent must be completed: CS 137 or 237A, 143, 154 or 254, 157, 161, 212, 221, 240A; Statistics 116. Courses are waived only if evidence is provided that a similar course has been taken elsewhere. Courses that are waived rather than taken may not be counted toward the M.S. degree. Core courses may be taken on a Satisfactory/No Credit basis provided that a minimum of 36 graded units is presented within the 45-unit program. Requirement 3--At least 1, but no more than 3, units of 500-level seminars must be taken. Requirement 4--A program of 21 units in an area of specialization must be completed. All courses in this area must be taken for letter grades. Six approved programs are listed below. Students may propose to the M.S. program committee other coherent programs that meet their goals and satisfy the basic requirements. Students desiring to include a substantial research project as part of their degree program can arrange with their adviser to replace units in their specialization with a CS 393 (Computer Laboratory) project. 1. Numerical Analysis/Scientific Computation a) CS 237A, 237B, 237C. b) At least two of: CS 260; Math. 131, 132, 220A, 220B, 220C; Op. Res. 152, 153; Stat. 116, 200. c) At least three of: CS 223, 326, 327A, 327B, 335, 339; Aero. & Astro. 214A, 214B; Mech. Engr. 235A, 254. 2. Systems a) CS 240B, 242. b) At least three of: CS 211, 243, 244, 245, 248, 312, 348B; Elect. Engr. 271. c) At least 6 more units selected from (2b) and: CS 194A, 194B, 265, 315A, 315B, 317, 318, 340, 341, 342, 343, 344, 345, 348A, 348C; Elect. Engr. 183, 272A, 272B, 281, 374, 482, 487. 3. Software Theory a) CS 242, 243, 258, 260. b) At least one of: CS 244, 245, 342, 343, 345, 441. c) At least one course from the following: CS 254, 363, 367A, 367B. d) At least one additional course from (3b) or (3c). 4. Theoretical Computer Science a) CS 257 or 258, 260, 264. b) At least 12 more units from CS 254, 256, 345, 351, 353, 358, 363, 365, 367A, 367B, 368; Op. Res. 340. 5. Symbolic and Heuristic Computation a) CS 222 or 257; 225A or 227; 226 or 270; 520 or 522 or 524 or 525 or 526 or 527. b) A total of 21 units from the above and: 223, 225B, 228A, 228B, 229, 254, 271, 272, 306, 323, 324, 325, 326, 327A, 327B, 329, 393. 6. Database (23 units) a) CS 245, 346, 347, 395. b) At least two of: CS 225A, 225B, 244, 345. c) At least one of: CS 265; Engr. Eco. Syst. 221, 231, 241; Op. Res. 241, 340; Stat. 376. d) A total of 23 units from the above listings and: CS 228A, 228B, 242, 248, 257, 271, 272, 315A, 315B, 323, 324, 340, 342, 344, 348A, 348B, 348C, 356A, 356B, 363, 365, 367A, 367B, 371, 395. Requirement 5--Additional elective units must be technical courses (numbered 100 or above) related to the degree program and approved by the adviser. Elective courses may be taken on a Satisfactory/No Credit basis provided that a minimum of 36 graded units is presented within the 45-unit program. DOCTOR OF PHILOSOPHY The University's basic requirements for the Ph.D. are discussed in the "Degrees" section in this bulletin. Applications to the Ph.D. program and all the supporting documents must be received before December 31, 1992. The following are departmental requirements (see the Computer Science graduate programs administrator for further details): 1. A student should plan and successfully complete a coherent program of study covering the basic areas of computer science and related disciplines. The student's adviser has primary responsibility for the adequacy of the program which is subject to review by the Ph.D. program committee. 2. Each student, to remain in the Ph.D. program, must satisfy the "breadth" requirement covering introductory level graduate material in major areas of computer science. Once a student fulfills 5 of the 7 "whole" areas of the "breadth" requirement, he or she may apply for admission to candidacy for the Ph.D. This must be done by the end of the second year in the program. The student must completely satisfy the "breadth" requirement by the end of nine quarters (excluding summers), and must pass a qualifying exam in the general area of the expected dissertation. 3. As part of the training for the Ph.D., the student is required to complete the following requirements: a) Two units (a unit is equal to 10 hours per week for one quarter) as a teaching assistant in a Computer Science course numbered above 106 which is organized and taught by a department faculty member. b) Two units as a teaching assistant in a Computer Science course numbered above 106 for which the teaching assistant will prepare and present at least 10 hours of new material in lecture or discussion sections, not including problem set reviews or discussion of material prepared centrally for distribution in the section. 4. The most important requirement is the dissertation. After passing the qualifying examination, each student must secure the agreement of a member of the department faculty to act as the dissertation adviser. (In some cases, the dissertation adviser may be in another department.) 5. The student must pass a University oral examination in the form of a defense of the dissertation. It is usually held after all or a substantial portion of the dissertation research has been completed. 6. The student is expected to demonstrate the ability to present scholarly material orally, both in the dissertation defense and by a lecture in a departmental seminar. 7. The dissertation must be accepted by a reading committee composed of the principal dissertation adviser, a second member from within the department, and a third member chosen from within the University. The principal adviser and at least one of the other committee members must be Academic Council members. Ph.D. MINOR For a minor in Computer Science, a candidate must complete 20 units of computer science course work, including at least three of the master's core courses to provide breadth, and one course numbered 300 to provide depth. The remaining courses must be numbered 200 or above. One of the courses taken must include a significant programming project to demonstrate programming proficiency. A letter grade indicator of 3.0 or better must be maintained. TEACHING AND RESEARCH ASSISTANTSHIPS Graduate student assistantships are available. Half-time assistants receive a tuition scholarship for 9 units per quarter during the academic year, and in addition receive a monthly stipend. Duties for half-time assistants during the academic year involve 20 hours of work per week. Teaching assistants (TAs) help an instructor teach a course by conducting discussion sections, consulting with students, grading examinations, etc. Research assistants (RAs) help faculty and senior staff members with research in computer science. Most teaching and research assistantships are held by Ph.D. students in the Department of Computer Science. If there is an insufficient number of Ph.D. students to staff teaching and research assistantships, then these positions are open to a limited number of master's students in the department. However, master's students should not plan on being appointed to an assistantship. Students with fellowships may have the opportunity to supplement their stipends by serving as graduate student assistants. COURSES GUIDE TO SELECTING INTRODUCTORY COURSES Students arriving at Stanford have widely differing backgrounds and goals, but most find that the ability to use computers effectively is beneficial to their education. The department offers many introductory courses to meet the needs of these students. For students whose principal interest is an exposure to the fundamental ideas behind computer science and programming, 105A is the most appropriate course. It is intended for students in non-technical disciplines who expect to make some use of computers, but who do not expect to go on to more advanced courses. CS 105A meets the Area 6 University distribution requirement and includes an introduction to programming, the discipline of computer science, and the social implications of computing. Students interested in learning to use the computer as a tool should consider 1C (Using the Macintosh) or 1U (Introduction to Unix). Students who intend to pursue a serious course of study in computer science may enter the program at a variety of levels, depending upon their background. Students with little prior experience or who wish to take more time to study the fundamentals of programming should take 106A followed by 106B. Students in 106A need not have prior experience but should be prepared for some mathematical problem solving. Students with prior exposure to programming or who want an intensive introduction to the field should take 106X, which covers most of the material in 106A,B in a single quarter. In some cases, it may be more appropriate for students with a strong background in programming to enroll directly in 106B, so as to concentrate on the material developed in the second half of the sequence. In all cases, students are encouraged to discuss their background with the instructors responsible for these courses. In past years, the medium of instruction for the CS 106 series has been the Pascal programming languages. In 1992-1993, the CS department will complete a transition to an introductory curriculum using C as the instructional language. In Autumn Quarter, 106B and 106X will be taught in Pascal, but no Pascal sections will be offered after that quarter. Both the Pascal and C versions of the course provide an introduction to the essential concepts of programming, but learning C provides a more directly relevant background for more advanced courses in the department. After the introductory sequence, Computer Science majors and those who need a significant background in computer science for related majors in engineering, should take (in any order) 107, 109A, 109B, and 110. CS 107 exposes students to a variety of programming languages which illustrate different programming paradigms. The 109A,B sequence constitutes a broad introduction to the underlying theory and conceptual structures used in computer science. CS 110 extends the computer science fundamental sequence by exposing students to issues in systems programming and computer architecture. In summary: For exposure--1C or 1U. For non-technical use--105A. For scientific use--106A. For a technical introduction--106A For significant use--106A,B or 106X, followed by 107, 109A,B, and 110. NUMBERING SYSTEM The first digit of a C.S. course number indicates its general level of difficulty: 0-99 service courses for non-technical majors 100-199 other service courses, basic undergraduate 200-299 advanced undergraduate/beginning grad-uate 300-399 advanced graduate 400-499 experimental 500-599 graduate seminars The ten's digit indicates the area of Computer Science it addresses: 00-09 Introductory, miscellaneous 10-19 Hardware Systems 20-29 Artificial Language 30-39 Numerical Analysis 40-49 Software Systems 50-59 Mathematical Foundations of Computing 60-69 Analysis of Algorithms 70-79 Typography and Computational Models of Language 90-99 Independent Study and Practicum NONMAJOR 1C. Using the Macintosh--Satisfactory/No Credit introduction to using the Apple Macintosh, including exposure to a word processor, communications facilities, spreadsheets, and other software packages. Weekly one hour lecture/demonstration with demonstrated software package. No exams or problem sets. Not a programming course. I unit, any quarter (Staff) 1U. Introduction to Unix--Tutorial on using the Unix operating system. Topics: the emacs editor, the file system, the Unix shell, and standard Unix tools (make, awk, sed, grep, etc.). Includes simple shell programming, but it is not a programming course and assumes no prior exposure to programming. 2 units, Win (Staff) MW 12 22. Programming in LISP--Introduction to problem solving in the LISP language and the functional and object oriented programming paradigms. Weekly exercises develop skills in recursion, list manipulation, mapping, functional arguments, destructive processing, classes, and methods. Also, macros, environments, packages, I/O, and LISP implementation. Term project. Prerequisite: 106B or 106X, or equivalent. 3 units, Win (Staff) MWF 2:15 50. Problem Solving with Mathematica--For engineers, physicists, mathematicians, and others who frequently need to solve mathematical or quantitative problems. Comprehensive introduction to Mathematica, an interactive mathematical software which incorporates a high-level programming language. Use of Mathematica to manipulate expressions, find roots, solve differential equations, visualize functions and data, import and export data, and to write functions. 2 units, Spr (Blachman) F 12-1 UNDERGRADUATE 105A. Introduction to Computers--For non-technical majors. Develops a working knowledge of computers as utilized in our society. Two major components: programming and issues. Topics: artificial intelligence, graphics, databases, ethical and social implications of computer technology, and computer hardware. Requires considerable interaction between student and computer, but is oriented toward students without a strong math and/or technical background, and assumes no previous computer experience. Students in technical fields and students looking to acquire programming skills are encouraged to take 106A or 106X. DR:6(8) *5 units, Aut (Staff) MWF 10 1 unit>Spr (Staff) MWF 2:15 106A. Programming Methodology--For students in technical disciplines; no prior experience is assumed. Broad introduction to the engineering of computer applications. Software engineering principles are stressed: design, decomposition, information hiding, procedural abstraction, testing, and reusable software components. Uses the programming language C and concentrates on the development of good programming style and on understanding the basic facilities provided by the language. Alternatives: 105A, 106X. DR:6(8) *5 units, Aut, Win (Staff) MWF 1:15 Spr (Staff) MWF 10 106B. Programming Abstractions--Abstraction and its relation to programming. Software engineering principles of data abstraction, modules, certain fundamental data structures (e.g., stacks and queues), and data-directed design. Recursion and recursive data structures (linked lists and binary trees). Analysis of running time and space requirements for arbitrary programs including an introduction to elementary recurrence relations. In Autumn Quarter, 106B is taught using Pascal for those students who have taken 106A in previous years; thereafter, 106B will be taught using C. Prerequisite: 106A or consent of the instructor. *5 units, Aut (Staff) MWF 11 Win, Spr (Staff) MWF 1:15 106X. Programming Methodology and Abstractions (Accelerated)--Covers 70% of the material in 106A,B. Intended as a one-quarter preparation for 109A for students whose previous programming experience is sufficient to help them cover this fundamental material more rapidly. In Autumn Quarter, 106X is taught using Pascal; thereafter, the language for instruction will be C. Prerequisite: Math. 3 or equivalent. DR:6(8) *5 units, Aut (Staff) MWF 3:15 Spr (Staff) MWF 1:15 107. Programming Paradigms--Possible programming languages introduced: Prolog, Lisp, Smalltalk, C, and Ada. Small programming projects are assigned. Prerequisite: 106B or 106X. 5 units, Aut (Staff) MWF 2:15 Spr (Staff) MWF 11 109A,B. Introduction to Computer Science--Two-quarter introduction to the conceptual and mathematical foundations of computer science. 109A: induction and recursion; analysis of the running time of programs; trees, lists, sets, functions, relations; basic data structures. 109B: graph algorithms; finite automata and regular expressions; context-free grammars; propositional and predicate logic; introduction to switching circuit design via propositional logic. Proof techniques, modeling, and abstraction are themes for the sequence. Functional programming exercises explore and exemplify these concepts. Prerequisite for 109A: 106B or 106X. Prerequisite for 109B: 109A. 109A. DR:6(8) 4 units, Aut (Staff) MWF 10 Win (Staff) MWF 2:15 109B. 4 units, Win (Staff) MWF 10 no title (letter)>Spr (Staff) MWF 2:15 110. Introduction to Computer Systems and Assembly Language Programming--Organization of digital computers, buses, registers, processors, I/O, memory systems, and paged memory. Data representation, data structures, and computer arithmetic. Instruction sets and execution; addressing modes. Assembly language programming, including subroutines, co-routines, interrupts, and traps. Operating systems issues and principles of storage management; combines general principles and practice in implementations. Prerequisite: 106B or 106X. 4 units, Aut, Spr (Chou) MW 12:50-2:05 Win (Staff) TTh 11-12:15 112. Computer Organization--(Enroll in Electrical Engineering 182.) Basic computer organization. Computer components: memory systems including caches, computer arithmetic, processors, controllers, input/output, buses, DMA. Data formats, addressing modes, instruction sets, and microcode. Study of the design of a small computer. Prerequisites: 110 and Electrical Engineering 121. 3 units, Aut (Gupta) Win (Hennessy) 137. Fundamentals of Numerical Computation--The fundamental issues of numerical computation for the mathematical, computational, and physical sciences, and engineering. Problems of accurately computing algebraically exact solutions in the presence of rounding errors and of computing discrete approximations of solutions which are defined on the continuum. The taxonomy of problem classes with methods for their solution and principles useful for analysis of performance and algorithmic development. Topics: error analysis, the solution of linear and nonlinear equations, interpolation and numerical differentiation, the approximation of integrals, and the solution of differential equations. Prerequisites: 106A; Math. 103 or 113 or equivalents. *4 units, Aut (Oliger) MWF 11 Win (Staff) TTh 1:15-2:30 Spr (Golub) MW 11-12:15 Sum (Staff) 140. Concurrent Programming--Principles of concurrent programming, including processes, mutual exclusion and synchronization, message-passing and monitors. Emphasis on principles and algorithms, rather than on implementation. Prerequisites: 107 and 110. 3 units, Aut (Staff) MWF 10 Win (Lam) MW 11-12:15 143. Compilers--Principles and practices in the design of programming language compilers. Topics: lexical analysis, parsing theory (LL, LR, and LALR parsing), symbol tables, type checking, common representations for records, arrays, and pointers, runtime conventions for procedure calls, storage allocation for variables, and generation of unoptimized code. Students construct simple compiler as programming project. Prerequisites: 107, 109B, and 110. *4 units, Aut, Spr (Dill) TTh 9:30-10:45 145. Introduction to Databases--Data models, Entity-Relationship model, designing a database for an application, relational database concepts, relational algebra and SQL. Dependencies, contraints, and normal forms. Interactive database interfaces, programmatic interfaces to database systems. Transactions, concurrency control. The role of databases and computers in application environments. Includes a substantial database design project using a database management system. Prerequisites: 109B and 110. *4 units, Aut (Keller) MWF 9 154. Introduction to Automata and Complexity Theory--Regular sets: finite automata, regular expressions, equivalences among notations, methods of proving a language not to be regular; context free languages: grammars, pushdown automata, normal forms for grammars, proving languages non-context free; Turing machines; equivalent forms, undecidability. Nondeterministic Turing machines: properties, the class NP, complete problems for NP. Alternate: 254. Prerequisite: 109B. *4 units, Win (Mitchell) MW 3:15-4:30 1 unit>Spr (Motwani) MWF 3:15 154N. Introduction to NP Completeness--Turing machines. Reducibilities among problems, Cook's theorem, examples of NP-complete problems. Students participate in approximately the last half of 154. Prerequisite: a knowledge of formal languages and automata as in the first part of 154. 2 units, Win (Staff) MW 3:15-4:30 Spr (Motwani) MWF 3:15 157. Logic and Automated Reasoning--Introduction to logic for computer scientists. An elementary exposition, from a computational point of view, of propositional logic, predicate logic, axiomatic theories, and theories with equality and induction. Interpretations, models, validity, proof. Automated deduction: polarity, skolemization, unification, resolution, equality. Strategies. Applications. Prerequisite: 109B. *4 units, Aut (McCarthy) TTh 11-12:15 1 unit>Spr (Genesereth) TTh 1:15-2:30 160. Discrete Mathematics--Introduction to the mathematics used in computer science. Topics: induction, relations, permutations, counting techniques, trees, graphs, groups, boolean algebras, lattices, partial orders. Note: redundant for students enrolled in 109A,B Autumn 1989 or later. 3 units, Aut (Plotkin) MW 11-12:15 161. Data Structures and Algorithms--Efficient algorithms for sorting, searching, and selection. Algorithm analysis: worst case and average case analysis. Efficient data structures: balanced trees, heaps, priority queues. Algorithm design techniques: divide-and-conquer, dynamic programming, greedy algorithm. Algorithms for fundamental graph problems, e.g., depth-first search, connected components, topological sort. Prerequisite: 109B. *4 units, Aut (Goldberg) MWF 3:15 1 unit>Win (Guibas) TTh 9:30-10:45 191. Senior Project--Group projects under faculty direction. Register using the section number associated with the instructor. 3-6 units, any quarter (Staff) by arrangement 192. Programming Service Project--Restricted to Computer Science students. Appropriate academic credit (without financial support) is given for volunteer computer programming work of public benefit and educational value. 1-3 units, any quarter (Staff) by arrangement 193D. C++ and Object-Oriented Programming--C++ programming language and object-oriented programming paradigm. Discussion of several substantial class libraries for data abstraction and graphical user-interface design. Intensive programming assignments. Prerequisites: knowledge of C and basic programming methodology as developed in 106B or 106X. 4 units, Win (Parlante) MW 12:50-2:05 193U. Software Engineering in C--C programming language and UNIX/C programming environment. C programming language issues: data types, control structures, pointers, dynamic memory allocation, libraries, performance, bit operations, and the interface to the UNIX shell. UNIX systems programming issues: file system, processes, signals, interprocess communication, and C interfaces to these capabilities. Includes a significant programming project. Previous experience in a high-level language other than BASIC and experience as a UNIX user required. Prerequisite: 106B, 106X, or equivalent. 3 units, Aut (Staff) MWF 3:15 Spr (Staff) MWF 1:15 194A,B. Software Project Laboratory--Experience in designing and implementing large-scale software systems. Working in teams, students complete modest-sized projects through specification, coding, and testing. 194A: students work on a standard project to develop the relevant software engineering skills. 194B: students work on projects of their own design. Topics: design methodologies, object-oriented design, problems of team programming, examples of good software, debugging techniques, and approaches to testing. 194A and B must be taken in consecutive quarters to qualify for project credit. Prerequisites: 107 and 110. 194A. 3 units, Win (Staff) MW 2:15-4:05 194B. 3 units, Spr (Staff) T 2:15-4:05 196. Microcomputer Consulting--Consulting in a microcomputer environment, focusing on the Apple Macintosh and DOS operating systems. Biweekly lectures outline the microcomputer environment on campus and demonstrate the skills needed to consult in such an environment. Students also work as the on-duty consultant at a campus cluster. 3 units, Aut, Win, Spr (Roberts, Virnau) TTh 7 p.m. 197. Mainframe and Workstation Computer Consulting--Computer consulting in a mainframe and workstation environment, focusing on the UNIX operating system under the SUN and DEC hardware systems. Topics: UNIX fundamentals, systems administration, shell scripting, VI, Emacs, networking, e-mail, and X-windows. Students work as on-duty consultants at the Sweet Hall computer cluster. 3 units, Aut, Win, Spr (Roberts, Kotadia) MW 7-8:30 p.m. 198. Teaching of Computer Science--Teach other students by running a small discussion section for a 106 course, and acting as on-duty help at the computing center. Three weekly meetings to discuss introductory courses in general, the specific course, and techniques of teaching. Application and interview required; see the receptionist in Computer Science/Tressider for information. Prerequisite: 106B or 106X. 4 units, Aut, Spr (Roberts, Nguyen, Wiltamuth) MTW 4:15-5:45 199. Independent Work--Special study under faculty direction, usually leading to a written report. Letter grade given; if this is not appropriate, enroll in 199P. Register using the section number associated with the instructor. any quarter (Staff) by arrangement 199P. Independent Work--Like 199, but graded either Satisfactory or No Credit. any quarter (Staff) by arrangement UNDERGRADUATE AND GRADUATE 200. Undergraduate Colloquium--Strongly recommended for junior-year CS majors as a way to build contacts with faculty. Weekly presentations by faculty and senior people from industry who informally describe their views of computer science as a field and their experience as computer scientists. 1 unit, Aut (Roberts) Th 3:15-5:05 Spr (Staff) Th 3:15-5:05 201. Computers, Ethics, and Social Responsibility--(Same as VTSS 215.) Primarily for majors entering computer-related fields. Analysis of ethical and social issues related to the development and use of computer technology. Introduction to relevant background in ethical theory, and social, political, and legal considerations. Analysis of scenarios in specific problem areas, e.g., privacy, reliability and risks of complex systems, and the responsibility of professionals for the applications and consequences of their work. Small group discussion and critical reading of source materials, emphasizing developing analytical skills for approaching these questions. Prerequisite: 106B or 106X. 3-4 units, Spr (Staff) MWF 11-12:15 203. Self-Directed Research--Students discuss, learn about, and perform self-directed research. Focuses on: defining criteria for success, leveraging off of existing work, finding sponsors, maintaining motivation, obtaining feedback, dealing with procrastination, and individually determining the best strategy for successful research. 3 units, Aut (Ginn) T 2:45-4:30 204. Undergraduate Programming and Problem-Solving Seminar--Students work on several problems for which the "best" solution is not known. Participants, in teams, design and implement their solutions. Class meetings exchange ideas and/or provide necessary background for a given problem. Prerequisites: extremely comfortable with programming, and have taken several upperclass CS courses beyond 109B. 3-6 units, Spr (Ullman) TTh 1:15-2:30 211. Logic Design--(Enroll in Electrical Engineering 381.) Principles and techniques of logic design. Combinatorial circuit analysis (hazard detection); combinatorial circuit design including PLA, VLSI, and MSI techniques and testing techniques; IC logic families, flip-flop properties, sequential circuit analysis and synthesis for fundamental and pulse mode circuits, design for testability techniques. Prerequisite: 112 or equivalent. 3 units, Aut, Win (McCluskey) 212. Computer Architecture and Organization--(Enroll in Electrical Engineering 282.) Structure of systems using processors, memories, input/output (I/O) devices, and I/O interfaces as building blocks. Computer system instruction set design and implementation, including memory hierarchies and pipelining. Issues and tradeoffs involved in the design of computer system architectures with respect to the design of instruction sets. Prerequisite: 112. 3 units, Aut, Win (Olukotun) 221. Introduction to Artificial Intelligence--Broad technical introduction to core concepts. Topics: knowledge representation, search, deduction, planning, constraint propagation, learning, expert systems, natural language understanding, and vision. General problems, critiques, and fundamental assumptions. Prerequisite: working knowledge of Lisp programming language. 3 units, Aut (Nilsson) MF 12:50-2:05 Win (Shoham) TTh 9:30-10:45 Spr (Latombe) TTh 1:15-2:30 221L. Introduction to AI Laboratory 1 unit, Aut (Staff) W 12:50-2:05 222. Agents--Rigorous treatment of the problems involved in building intelligent agents that interact with the physical world. Topics: the representation of knowledge about states, actions, and procedures, simulation and planning, and knowledge level agents. Prerequisites: 157, 221. 3 units, Aut (Genesereth) TTh 1:15-2:30 222L. Agents Laboratory 3 units, Aut (Staff) W 3:15-5:15 223. Introduction to Robotics--(Formerly 327A.) Basics, and a review of current applications. Topics: manipulator kinematics and inverse kinematics; manipulator dynamics, motion control, and force control; motion planning and robot programming. Recommended: knowledge of matrix algebra and some familiarity with basic control theory and rigid body mechanics. 3 units, Win (Khatib) MWF 3:15 225A. Declarative Programming--Construction of programs that use an inference mechanism operating on a declarative knowledge base. Emphasis on declarative representation of domain knowledge, monotonic and non-monotonic inference methods, and on inference control methods. Some knowledge acquisition involved. Substantial Lisp programming required. Course work done in teams. Prerequisites: 157, 221, and Lisp. 3 units, Spr (Staff) TTh 9:30-10:45 225B. Declarative Programming Project--Independent project involving the construction and presentation of a substantial declarative program. Corequisite: 225A. 3 units, Spr (Staff) Th 7-9 p.m. 226. Expert System Applications--Expert Systems are the most important of the applications of Artificial Intelligence in the commercial and defense sectors. Topics: the rapid transition of the Expert System technology from lab to societal use, what is in an Expert System, what is Knowledge Engineering. Case studies of commercial application in: diagnosis and repair, interpretation of data, manufacturing planning and control, financial services, engineering design, etc. The sources of benefit from Expert Systems. The magnitude of these benefits. What an organization needs to do to realize the benefits. A "what" rather than a "how to build systems" orientation aimed for a broad interdisciplinary audience. 3 units, Win (Feigenbaum) TTh 2:45-4 227. AI Algorithmic Techniques--AI algorithmic techniques explained in detail, and implemented in Prolog. Topics: search, backward and forward chaining, production systems, truth maintenance, reasoning with uncertainty, constraint satisfaction. Application areas: temporal reasoning, learning and natural language. Students with no prior Prolog experience may take additional 1-unit tutorial. Prerequisites: programming experience, familiarity with basic notions in data structures and algorithms. Recommended: previous or concurrent course in AI. 3 units, Win (Shoham) TTh 1:15-2:30 228A. Introduction to Knowledge Systems--Foundations for understanding symbols, search, and knowledge-level analysis. Topics: symbol systems, different approaches to semantics, blind, directed, and hierarchical search methods, the verbal data hypothesis for protocol analysis, multi-disciplinary concepts for knowledge acquisition, computational models and reasoning phenomena for classification, configuration and diagnosis, interfaces from embedded systems to data bases, users, and remote knowledge systems. Prerequisites: familiarity with logic and high-level programming languages. 3 units, Spr (Stefik) TTh 4:30-5:45 228B. Introduction to Knowledge Systems--Symbol-level topics in reasoning, representation, and machine learning. Topics: concepts from graph theory for efficient constraint satisfaction, search, and truth maintenance systems. Intensional representations and models for reasoning about space, time, certainty, and qualitative models of mechanism. Introduction to concepts and methods for machine learning. Prerequisite: 228A. 3 units (Stefik) not given 1992-1993 229. Machine Learning--Survey of major research paradigms. Topics: inductive learning, explanation-based learning, genetic algorithms, analogical reasoning, case-based learning, connectionist learning, machine discovery, delayed-reinforcement learning, and probably-approximately-correct learning theory. Focuses on the underlying concepts and on the role of machine learning in artificial intelligence. Representative systems are described. 3 units, Spr (Nilsson) MW 11-12:15 237 Advanced Numerical Analysis--Three-quarter graduate sequence designed to acquaint students in mathematical and physical sciences and engineering with the fundamental theory of numerical analysis. Examples from applications. 237A. Numerical Linear Algebra--Solution of systems of linear equations: direct methods, error analysis, structured matrices; iterative methods and least squares. Parallel techniques. Prerequisites: 106A, 137, Math. 103 or 113. 3 units, Aut (Golub) MW 11-12:15 237B. Numerical Solution of Boundary Value Problems--Two-point boundary value problems: shooting methods, finite difference methods and collocation methods. Defect correction. Higher order methods. Approximation theory and the finite element method for two-point boundary value problems. Elliptic partial differential equations: finite difference, finite element, spectral methods and multigrid methods. Prerequisites: 237A; Math. 130, 131. 3 units, Win (Oliger) MWF 11 237C. Numerical Solution of Initial Value Problems--Linear multistep methods and Runge-Kutta methods for ordinary differential equations: zero-stability, A-stability, and convergence. Differential algebraic equations. Parabolic partial differential equations: stability, convergence and qualitative properties. Hyperbolic partial differential equations: stability convergence and qualitative properties. Prerequisites 237A, Math. 130,131. 3 units, Spr (Stuart) MW 11-12:15 240A,B. Operating Systems--Two-quarter sequence on operating systems design and implementation. 240A: fundamentals of operating system design and implementation--basic structure; synchronization and communication mechanisms; implementation of processes, process management, and scheduling; memory organization and management, including virtual memory; I/O device management, secondary storage, and file systems. 240B: combination of advanced study in standard OS topics and exposure to recent developments in OS research. Deeper coverage of issues that arise in all OS subsystems covered in 240A, plus protection and security, and performance analysis; OS support for special-purpose (e.g., real-time) systems; distributed systems, including OS support for networking, practical distributed environments, distributed kernels, and multiprocessor operating systems. Prerequisites for 240A: 110 and 140 or equivalent. Recommended: 112. Prerequisite for 240B: 240A. 240A. 4 units, Aut (Rosenblum) MWF 1:15 no title (letter)>Win (Staff) MWF 10 240B. 3 units, Win (Rosenblum) MWF 1:15 no title (letter)>Spr (Rosenblum) MWF 10 242. Programming Languages--Basic elements of programming languages and programming paradigms (imperative, functional, logical, object-oriented). Introduction to formal semantic methods. Modern type systems. Runtime support for different language features. Emphasis is on separating the different elements of programming languages and styles; specific languages considered only to show the different incarnations of a given element. Prerequisite: 107, or experience with Lisp, C and Smalltalk (or similar languages). 3 units, Aut (Talcott) MWF 2:15 243. Advanced Compiling Techniques--Theoretical and practical aspects of building modern compilers. Topics: language and machine descriptions, code transformation, intermediate representations, basic block and flow-graphs, function calling mechanisms, dataflow analysis, register allocation, instruction scheduling, type analysis and checking, compiler-compilers. Three hours lecture; one hour discussion led by a TA. Prerequisite: 143 or equivalent. *4 units, Win (Staff) TTh 9:30-10:45 244. Computer Networks: Architectures and Protocols--Objectives of computer networks; network structure and components; switching techniques (circuit switching and packet switching); network functions; layered network architectures (the ISO reference model); data link protocols (character-oriented protocols, bit-oriented protocols, error checking, window flow control, and multi-access protocols); network control (datagrams, virtual circuits, routing, and congestion control); transport and session protocols (end-to-end communication, interconnection of networks); presentation layer protocols are cited for point-to-point, satellite, packet radio, and local area networks. Prerequisite: 240A. 3 units, Aut (Staff) (Enroll in Electrical Engineering 384) Win (Cheriton) TTh 2:45-4 245. Database Implementation--File organization and access, buffer management, performance analysis, and storage management. Database system architecture, query optimization, transaction management, recovery, concurrency control. Reliability, protection, and integrity. Design and management issues. Includes a database implementation project. Prerequisites: 145 and 161. 3 units, Win (Keller) MWF 9 247A,B. Human-Computer Interaction--Issues of human-computer interaction, including: interface styles, work design, communication structure and organizational factors. Students in small groups develop substantial user-interface prototypes of systems for situations of actual use, applying concepts from readings and interacting in project reviews with faculty and experienced system designers. Enrollment limited. Consent of instructor required. Prerequisite for 247A: 109B. Prerequisite for 247B: 247A. 247A. 3 units, Win (Staff) MWF 2:15 plus two-hour lab 247B. 3 units, Spr (Staff) MWF 2:15-3:45 248. Introduction to Computer Graphics--Fundamentals of input, display, and hardcopy devices, scan conversion of geometric primitives, 2D and 3D geometric transformations, clipping and windowing, scene modeling and animation, algorithms for visible surface determination, introduction to local and global shading models, color, and photorealistic image synthesis. Written assignments and programming projects. Prerequisites: 107, Math. 113. 3 units, Spr (Levoy) TTh 9:30-10:45 254. Automata, Languages, and Computability--Enriched version of 154, recommended for graduate students and for undergraduates strong in math. Alternate 154. Prerequisite: 109B. *4 units, Aut (Floyd) MWF 10 256. Concurrent and Reactive Systems--Formal methods for specification, verification, and development of concurrent and reactive programs, based on temporal logic. Basic models: generic transition system, shared variables, synchronization constructs, communication constructs, asynchronous and synchronous message passing. Faithful modeling of concurrency: interleaving, fairness. Specification language of temporal logic: temporal operators, future and past formula, axioms and rules. Hierarchy of program properties: safety, termination, intermittence, response, persistence, and progress. Verification of programs. Invariances, incremental verification, heuristics, assertion diagrams, overtaking analysis, forward and backward analysis, history variables. Chain and well-founded rules. Program development. Parameterized programs. Real-time programs. Automatic verification tools for finite-state programs. Prerequisite: 157 or equivalent. 3 units, Aut (Manna) MW 11-12:15 257. Automated Deduction and Its Applications--Proving theorems and extracting information from proofs. Uses in software engineering (program synthesis, transformation, and verification) and artificial intelligence (commonsense and robotic planning, natural-language understanding). Foundations of logic programming. Deductive tableaux, nonclausal resolution, the truth behind skolemization, building theories into unification and inference rules, term rewriting. The design of theorem provers. Prerequisite: 157. 3 units, Spr (Staff) TTh 2:45-4 258. Introduction to Programming Language Theory--Syntactic, operational, and semantic issues in the mathematical analysis of programming languages. Type systems and non-context-free syntax. Universal algebra and algebraic data types. Operational semantics given by rewrite rules; confluence and termination. Scott-semantics for languages with higher-type functions and recursion. Treatment of side-effects. Prerequisites: 154, and 157 or Philosophy 160A. 3 units, Aut (Mitchell) MW 12:50-2:05 260. Concrete Mathematics--Finite difference calculus; manipulation of sums and products, properties of binomial coefficients, Stirling numbers, harmonic numbers, Fibonacci numbers; use of generating functions to solve recurrence relations; asymptotic expansions; analysis of algorithms. Emphasis is on obtaining simple closed-form answers to problems when it is possible. Prerequisites: 160 and Math. 42, or equivalent. 3 units, Win (Floyd) MWF 10 264. Introduction to Combinatorial Theory--Elementary combinatorics. Topics: permutations, combinations, partitions; the principle of inclusion and exclusion; Ramsey's theorem; Burnside's lemma; Polya's counting theorem; the elementary theory of graphs and trees; flow in networks; matching problems; an introduction to matroids. Prerequisites: 160 and Math. 44 or equivalent. 3 units (Dantzig) alternate years, given 1993-94 265. Basic Tools in Computer Systems Modeling--(Enroll in Electrical Engineering 284.) Basic tools for the analysis and performance evaluation of computer systems. Topics: review of probability theory, Poisson distribution, exponential distribution, transforms, Poisson process, discrete-parameter Markov chains, birth-death processes, queueing theory, networks of markovian queues. Examples from computer systems area. Prerequisite: Statistics 116. 3 units, Win (Staff) 270. Computer Applications in Medicine--(Same as Medical Information Sciences 210.) Survey of use of computers in the medical field. Includes variety of research and applied environments and factors which influence the acceptance of these applications. Topics: integration of computer systems in the medical center, hospital information systems, ambulatory care systems, medical databases and networking, bibliographic search, applications to molecular biology, aids for disabled patients, image processing, computer-aided instruction, decision support systems. 3 units, Aut (Fagan, Shortliffe) TTh 1:30-2:45 271. Computer-Based Medical Decision Making--(Same as Medical Information Sciences 211.) For undergraduates or graduate students. Overview of concepts in medical decision making and survey of methods for the implementation of such concepts in computer-based clinical decision-support tools. Emphasis on Bayesian statistics, decision analysis, artificial intelligence/expert systems, and the synergies among such approaches. No medical background required. Prerequisite: at least one programming course. 3 units, Win (Shortliffe) TTh 1:30-2:45 272. Medical Informatics Project Course--(Same as Medical Information Sciences 212.) Project course for students who have completed 270 or 271 and who wish to implement some of those ideas in a computer program. Software tools provided. Prerequisites: programming experience, 270 or 271. 3 units, Spr (Walker, Fagan) TTh 1:30-2:45 273. Concepts of Text--(Same as Art 281.) What every literate person should know about the basic principles of the visual organization of text. Topics: handwriting, typewriting, typography, and computerized documents, perceptual, linguistic, and semiological issues. Consists primarily of visual exercises. 3 units, Spr (Bigelow) TTh 9:30-10:45 277. Topics in Computational Linguistics--(Enroll in Linguistics 236.) Hands-on practicum aimed at developing tools for an area of application such as machine translation. Prerequisite: background in computational linguistics. 3 units, Win (Kay) PRIMARILY FOR GRADUATE STUDENTS 300. Departmental Lecture Series--Recommended for first-year Computer Science graduate students. Weekly presentations by members of the department faculty, each describing informally his or her current research interests and views of computer science as a whole. 1 unit, Aut (Staff) TTh 4:15-5:30 304. Programming and Problem Solving Seminar--Limited to and recommended for Ph.D. degree candidates in computer science. Solution of various problems, numeric and symbolic, on computers. Emphasis on the research paradigms of computer science and the development of algorithms that are "beautiful" from various points of view. 3 units, Spr (Floyd) TTh 11-12:15 306. Recursive Programming and Proving--Uses LISP language and techniques for providing the correctness of recursive programs. Computing with symbolic expressions rather than numbers, e.g., algebraic expressions, logical expressions, patterns, graphs, and computer programs. Pattern matching and syntax directed computation. Preparation for work in artificial intelligence is emphasized. Prerequisite: 109B. 3 units 309. Industrial Lectureships in Computer Science--The department invites an outstanding computer scientist to give a course in his/her specialty. Lecturers and topics change yearly; courses may be taken repeatedly. See Time Schedule for offerings. 3 units, by arrangement 312. Processor Design--(Enroll in Electrical Engineering 382.) Basic cycle time, processor area tradeoffs, and processor design studies. Vector processors, multiple instruction issue processors and shared memory mutiprocessors. Queuing analysis of memory systems and I/O storage systems. Prerequisite: 212 or equivalent. 3 units, Win (Flynn) 315A. Parallel Computer Architecture and Programming--Principles and major challenges in design of parallel architectures. Study of research and commercial parallel machines designed to support the shared-memory, message-passing, dataflow, systolic, and data-parallel paradigms. Interleaved with architectural studies are lectures on techniques for programming parallel computers. Programming assignments are done on one or more commercial multiprocessors. Prerequisites: 140, 212, and reasonable programming experience. 3 units, Win (Gupta) TTh 11-12:15 315B. Parallel Programming Project--Continuation of 315A. A significant parallel programming project is required. Several different shared-memory multiprocessors, a message-passing machine, and a connection machine are available for use in projects. Lectures on parallel programming languages and their implementation, performance debugging of parallel programs, parallel data structures and algorithms. Prerequisite: 315A or consent of instructor. 3 units (Gupta) not given 1992-93 317. Fault Tolerant Computing Systems--(Enroll in Electrical Engineering 489.) Basic considerations in the design of reliable computing systems. Concurrent checking techniques. Redundancy techniques. Evaluation methods. System considerations. Examples of specific system designs. Prerequisite: 212. 3 units, alternate years, given 1993-94 318. Testing Aspects of Computer Systems--(Enroll in Electrical Engineering 488.) Fundamental principles of testing computer systems and designing for testability. Failure and fault models. Deterministic and probabilistic techniques of test generation and testing. Techniques for testing memories and microprocessors. Design for testability. Prerequisite: 211. 3 units, Spr (McCluskey) alternate years, not given 1993-94 319. Topics in Digital Systems--Advanced material is often taught for the first time as a "topics" course, perhaps by a faculty member visiting from another institution. Students may therefore enroll repeatedly in a course with this number. See Time Schedule for topics currently being offered. by arrangement 323. Nonmonotonic Reasoning--(Same as Philosophy 326.) Formalisms for representing non-monotonic reasoning and their applications to AI. Nonmonotonic aspects of commonsense knowledge and reasoning. Default logic, autoepistemic logic, and circumscription. Computational nonmonotonic reasoning. Applications of nonmonotonic formalisms to inheritance systems, to logic programming, and to reasoning about action using the situation calculus. Prerequisite: a basic knowledge of logic such as 157, or Philosophy 160A. 3 units, Win (McCarthy) TTh 1:15-2:30 324. Semantical Foundations of Knowledge Representation--Formal treatment of reasoning about time, action, knowledge, and uncertainty; emphasis on epistemological questions and their relevance to AI. Topics: logics of time and action, logics of knowledge and belief, nonmonotonic logics, fuzzy logics, and probabilistic logic. Prerequisites: an understanding of logic and basic model theory. 3 units, Spr (Shoham) TTh 11-12:15 325. Planning Methods in Artificial Intelligence--Introduction to AI methods for planning courses of actions to achieve a specified goal from an initial state of the world. Linear planning (means-ends analysis, goal regression), non-linear planning, hierarchical planning, and compromise-based planning. Planning with temporal constraints. Reactive planning architectures. Interaction with execution and learning. Underlying problems--frame, qualification, prediction, and persistence, and notions, such as interdependent subgoals, reviewed and analyzed. Two parts: the basics illustrated with simple examples; and applications in various domains (robotics, process planning, etc.) Prerequisite: 221. 3 units, Win (Latombe) TTh 9:30-10:45 326. Motion Planning--Computing object motions is central to many application domains (e.g., design, manufacturing, robotics, animated graphics, medical surgery) to generate collision-free paths among static obstacles. Extensions include uncertainty, moving among mobile obstacles, manipulating movable objects, and maneuvering with kinematic constraints. Introduction to this domain uses configuration space as a unifying link, describes effective planning methods (roadmap, cell decomposition, potential field, preimage backchaining, centralized/decoupled planning, non-directional planning), illustrated with applications in various domains. Assumes interests in computer graphics, geometrical computing, robotics, and/or artificial intelligence. 3-6 units, Spr (Latombe) MW 12:50-2:05 327A. Advanced Robotic Manipulation--(Formerly 327C.) Topics: redundant manipulators, control architectures, operational space framework, robot motion/force control, control at kinematic singularities, control of multiple manipulators, dextrous dynamic coordination of macro/mini-manipulator systems, effective inertia, sensor-based primitives, artificial potential field and force strategies, robot design. Prerequisites: 223, consent of instructor. 3 units, Spr (Khatib) MW 2:15-3:30 327B. Introduction to Computer Vision--Visual perception by computer with comparisons to psychophysics. Image formation: projection, surface reflectivity models and color, image sensors. Range data analysis: range measurement, representation of surfaces, differential geometry, and local discontinuities. Segmentation and aggregation: local and extended discontinuities, structure and texture. Industrial machine vision. Interpretation of image data: geometric models, generic surface interpretation, graph and network probability methods. 3 units, Win (Binford) TTh 11-12:15 329. Topics in Artificial Intelligence--Advanced material is often taught for the first time as a "topics" course, perhaps by a faculty member visiting from another institution. Students may therefore enroll repeatedly in a course with this number. See Time Schedule for topics currently being offered. 1-3 units 335. Statistical Computing--(Enroll in Statistics 327.) Numerical analysis aspects of least squares, nonlinear and robust regression, random number generation and Monte Carlo, eigenvalue computations in multivariate analysis, numerical integration and computational complexity. Emphasis on computational aspects relevant to practical statistical problems. Prerequisites: Statistics at the level of 219-220, matrix algebra, knowledge of a programming language. 3 units (Staff) not given 1992-93 336. Advanced Methods in Matrix Computation--Eigenvalue problems: perturbation theory, Lanczos method, Jacobi method. Parallel implementation. Singular value problems. Generalized eigenvalue problems. Polynomial equations. Prerequisite: 237A. 3 units (Golub) given 1993-94 337. Numerical Methods for Initial Boundary Value Problems--Initial boundary value problems are solved in different areas of engineering and science modeling phenomena, e.g., wave propagation and vibration, fluid flow, etc. Numerical techniques for such simulations are discussed in the context of applications. Emphasis is on stability and convergence theory for methods for hyperbolic and parabolic initial boundary value problems, and the development of efficient methods for these problems. 3 units (Oliger) given 1993-94 338. Numerical Analysis of Dynamical Systems--Dynamical systems arise in science and engineering, and typical applications involve the prediction or simulation of long-time evolutions, e.g., weather prediction, turbulent fluid simulations, phase separation calculations, and interplanetary motions. Standard analysis of algorithms for approximating initial value problems leads to an error bound of no value over long time intervals. Analysis and construction of algorithms in this case requires an interdisciplinary approach using ideas from numerical analysis and dynamical systems. Topics: introduction to dynamical systems, dissipative dynamical systems and their approximation; conservative and Hamiltonian dynamical systems and their approximation, direct approximation of invariant sets. Theory illustrated with applications. Prerequisite: 237C. 3 units, Aut (Stuart) TTh 9:30-10:45 339. Topics in Numerical Analysis--Advanced material is often taught for the first time as a "topics" course, perhaps by a faculty member visiting from another institution. Students may therefore enroll repeatedly in a course with this number. See Time Schedule for current topics. by arrangement 340. Distributed Systems--Overview of distributed systems, primarily as an extension of uniprocessor operating systems to span networks. Presents the impact of networking on each of the subsystems and issues discussed in 240A,B, including basic architectural models; network-transparent message-passing and remote procedure call; network-wide virtual memory; distributed file systems; encryption, and multi-site concurrency control, replication, and error recovery. Prerequisites: 240B and 244. 3 units, Spr (Cheriton) TTh 2:45-4 341. Distributed Systems Project--Companion project option for students taking 340. Corequisite: 340. 3-6 units, Spr (Cheriton) 342. Programming Language Design--Exposure to problems of programming language design and known solutions. Possible topics: formal semantics, implementation considerations, extensibility, very high level languages, evaluation of language designs, the innovative features of a variety of modern programming languages. Prerequisites: 242, 243. 3 units, Spr (Staff) MWF 3:15 alternate years, not given 1993-94 343. Topics in Compilers--Compilation techniques for parallel machines. Data dependence analysis, loop transformations, parallelization for multiprocessors, optimizations to exploit caches and registers, instruction scheduling for superscalar machines, and other advanced topics, e.g., interprocedural analysis and code generation for distributed memory machines. 3-6 units, Spr (Lam) MW 11-12:15 344. Computer Networks: Modeling and Analysis--(Enroll in Electrical Engineering 484.) Network functions, architectures, and protocols; computer traffic characterization; resource sharing; packet-switched store-and-forward networks (ARPAnet); delay analysis, network design and optimization including capacities assignment, routing and topological design; multi-access/broadcast protocols (used in packet-switched satellite, ground radio, and local networks): fixed assignment, adaptive strategies, stability considerations and dynamic control. Prerequisite: 265. Recommended: knowledge of 244. 3 units, not given 1992-1993 345. Deductive Database Systems--Logic as a query language: relational calculus, datalog, other forms of logic. Techniques for optimizing logical queries. Coping with negated subgoals (nonmono-tonic reasoning): stratified logic, well-founded and other semantics for ascribing meaning to rules with negation. Object-oriented features: Hilog, complex objects, inheritance. Examples of logical query languages and systems. Prerequisite: 145 or equivalent. 3 units, Win (Ullman) MW 2:15-3:30 346. Transaction Processing--Overview of transaction processing systems and their implementation for application, e.g., airline reservations, banking, and inventory control. Evolution and history of transaction processing systems. Review of fault tolerance, process management, and performance. Transaction models, transaction processing monitors and their implementation, lock managers, recovery managers, file management and access paths, and disaster recovery and data replication. Information retrieval systems. Survey of commercial systems and research prototypes. Prerequisites: 145, 245. Recommended: 347. 3 units, Aut (Garcia-Molina) TTh 11-12:15 Sum (Staff) TTh 9:30-10:45 347. Distributed Databases--Principles and system organization of distributed databases. Data fragmentation and distribution, distributed database design, query processing and optimization, distributed concurrency control, reliablility and commit protocols, and replicated data management. Distributed algorithms for data management: clocks, deadlock detection, and mutual exclusion. Heterogeneous and federated distributed database systems. Overview of commercial systems and research prototypes. Prerequisites: 145, 245. 3 units, Spr (Garcia-Molina) TTh 9:30-10:45 348A. Computer Graphics: Mathematical Foundations--Mathematical tools needed for the geometrical aspects of computer graphics. Topics: homogeneous coordinates, transformations and perspective, parametric and implicit curve and surface modeling, representations of solids, geometric algorithms for hidden surface elimination, shadow calculation, ray tracing, etc. Prerequisite: solid foundation in linear algebra and discrete algorithms. 3 units, Aut (Guibas) TTh 9:30-10:45 348B. Computer Graphics: Image Synthesis Techniques--Intermediate level, emphasizing sampling, shading, and display aspects of computer graphics. Topics: local and global illumination methods including radiosity and distributed ray tracing, texture generation and rendering, volume rendering, strategies for anti-aliasing and photorealism, human vision and color science as they relate to computer displays, and high-performance architectures for graphics. Written assignments and programming projects. Prerequisite: 248 or equivalent. Recommended: exposure to Fourier analysis or digital signal processing. 3 units, Win (Levoy) TTh 9:30-10:45 348C. Topics in Computer Graphics--In-depth study of one or more active research areas in computer graphics, depending on student interest. Sample topics: display of multidimensional data, volume visualization, exotic user interface technologies such as eye tracking, head tracking and head-mounted displays, and parallel algorithms for graphics. Includes a significant project. Prerequisites: 248 or 348A, 348B, or consent of instructor. 3 units (Levoy) not given 1992-93 348D. Vision and Image Processing Lab--(Enroll in Psychology 267.) Through lectures and hands-on experience with a computer lab, explores topics in image processing, human and computer vision, and computer graphics. Topics: image representation and image coding, sampling and filtering, motion analysis, binocular stereopsis, color, texture analysis, and synthesis. 3 units, Spr (Heeger) 349. Topics in Programming Systems--Advanced material is often taught for the first time as a "topics" course, perhaps by a faculty member visiting from another institution. Students may therefore enroll repeatedly in a course with this number. See Time Schedule for topics currently being offered. by arrangement 351. Topics in Complexity Theory and Lower Bounds--Possible topics: basic machine models and complexity measures--their properties and relationships. Complexity classes and their properties; reductions and complete problems. Concrete representative problems from important complexity classes and techniques for establishing limits on the possible efficiency of algorithms. Lower bounds based on the following models of computation: decision trees, straight line programs, communication complexity, branching programs, PRAMs, boolean circuits. Spacetime trade-offs and pebbling games. Prerequisites: 154 and 264, or equivalent. 3 units, Win (Motwani) TTh 2:45-4 352. Foundations of Control Structures--Theory of constructs for controlling program execution. Theories of serial control: verification conditions, partial correctness assertions, weakest preconditions, dynamic logic. Models of serial control: state functions and relations, regular expressions, dynamic algebras. Theories of parallel control: temporal logic, CCS, CSP. Models of parallel control: state trajectories, synchronization trees, execution traces, partial orders, metric spaces. Notions of time: ordered, real, probabilistic. Related soundness, completeness, and complexity issues. Prerequisite: 258 or consent of instructor. 3 units, Spr (Staff) TTh 9:30-10:45 353. Algebra for Computer Scientists--Algebraic methods relevant to computer science. Lattice theory: partial orders, monoids, closure systems, topologies, fixpoint theorems. Universal algebra: HSP, free algebras, equational theories, Birkhoff's theorem, completeness of equational logic. Algebras for logic: Boolean, Heyting, cylindric. Categories: limits, adjunctions, algebraic theories, enriched categories. Prerequisites: 157, 161; Philosophy 160A, or equivalent. 3 units (Pratt) not given 1992-93 355. Reasoning About Finite-State Concurrent Systems--Automatic methods for analyzing finite-state systems, emphasizing automatic formal verification. Topics: state graph and automata models of system behavior. Automata on infinite strings. Linear and branching-time temporal logic. Model-checking. Applications to circuits, algorithms, and protocols. Modeling real-time systems. Analysis methods based on Boolean formulas, and other ways of coping with the "state explosion problem." Prerequisite: 154 or 254. Recommended: good understanding of basic automata and complexity theory, and undergraduate-level background in computer science. 3 units (Dill) not given 1992-93 356A. Reasoning about Knowledge--Knowledge plays a crucial role in distributed systems, cryptography, and artificial intelligence. Material examines formalizing reasoning about knowledge and extent to which knowledge is applicable to the areas above. Issues: common knowledge, probabilistic knowledge, applying knowledge to analyzing distributed systems, attainable states of knowledge, and modeling resource-bounded reasoning. Prerequisites: mathematical maturity and an acquaintance with propositional logic. 1-3 units (Halpern) alternate years, given 1993-94 356B. Reasoning about Uncertainty--Uncertainty must be confronted when designing computer systems. Examines formalizing reasoning about uncertainty in particular approaches based on logics involving probablility. Topics: logics of probability, combining knowledge and probablility, probability and adversaries, the Dempster-Shafer approach, going from statistical information to degrees of belief. Prerequisites: mathematical maturity and an acquaintance with propositional logic. Recommended: 356A. 1-3 units, Win (Halpern) F 2:15-4:05 alternate years, not given 1993-94 358. Topics in Programming Language Theory--Possible topics of current research interest in the mathematical analysis of programming languages: structured operational semantics, domain theory, semantics of concurrency, rich type disciplines, problems of representation independence, and full abstraction. May be repeated for credit. Prerequisites: 154, 157, 258, or equivalents. 3 units, Spr (Mitchell) MW 12:50-2:05 359. Topics in Theory of Computation--Advanced material is often taught for the first time as a "topics" course, perhaps by a faculty member visiting from another institution. Students may therefore enroll repeatedly in a course with this number. See Time Schedule for topics currently being offered. 1-3 units, by arrangement 363. Combinatorial Optimization--(Same as Operations Research 349.) Algorithms for optimization of combinatorial structures. Topics: maximum flows, minimum-cost flows, bipartite matching and assignment problem, general matching, stable marriage, polynomial-time algorithms for linear programming, approximation algorithms for NP-hard problems. Emphasis on recent developments in the field. Prerequisite: 161 or 264, or equivalent. 3 units, Win (Goldberg) TTh 11-12:15 365. Probabilistic Algorithms--Construction and analysis of algorithms that solve various problems efficiently in a probabilistic sense. Algorithms that work almost everywhere. Expected performance of heuristic algorithms. Limitation and complexity of probabilistic computations. Prerequisites: 262, Statistics 115 or 116, or equivalents. 3 units, Aut (Motwani) TTh 2:45-4 alternate years, not given 1993-94 367A. Parallel Computation--Introduction to theoretical issues in parallel computation. Topics: Parallel machine models. Design and analysis of algorithms on systolic arrays: arithmetic operations, simple graph algorithms, sorting. Upper and lower bounds for randomized and deterministic routing on Hypercube-related networks. PRAM model of computation. Basic PRAM algorithms: prefix computation, sorting, shortest paths, minimum-weight spanning tree, eulerian walk. Randomized and deterministic techniques for reducing the processor-time product. Simulation of stronger PRAM models by weaker ones. Complexity issues: definition of NC and P-completeness; some simple lower bounds. 3 units (Plotkin) alternate years, given 1993-94 367B. Parallel Computation--Advanced parallel algorithms. Possible topics: efficient randomized parallel algorithms for symmetry-breaking and related problems. Derandomization techniques. Parallel sorting. Evaluation of straight-line code, P-complete problems. Deterministic and randomized parallel algorithms for flows and related problems; assignment problem, matching in general graphs. 3 units, Win (Plotkin) W 2:15-4:05 alternate years, not given 1993-94 368. Geometric Algorithms--Graduate-level introduction to basic techniques used in the design and analysis of efficient geometric alogrithms including: convexity, triangulation, sweeping, partitioning, and point location. Recent developments using random sampling methods. Emphasizes data structures of general usefulness in geometric computing and the conceptual primitives appropriate for manipulating them. Impact of numerical issues in geometric computation. Applications to robotics, vision, and CAGD. No prior knowledge of geometric techniques is assumed. Prerequisite: 161. 3 units, Win (Guibas) TTh 1:15-2:30 369. Topics in Analysis of Algorithms--Advanced material is often taught for the first time as a "topics" course, perhaps by a faculty member visiting from another institution. Students may therefore enroll repeatedly in a course with this number. See Time Schedule for topics currently being offered. 3 units, Win (Goldberg) TTh 2:45-4 Spr (Plotkin) W 2:15-4:05 371. Medical Decision Analysis--(Same as Engineering-Economic Systems 235.) Use of decision analysis in medical practice. Student teams analyze specific clinical decision problems as a term project. Topics: the decision making role of patients and physicians, medical preference models, assessing decision models in a clinical context, medical ethics, and designing and using automated medical decision tools. Prerequisite: Engineering Economics Systems 31 or 231, or equivalent. 4 units, Spr (Holtzman, Matheson) MWF 3:15-4:30 378. Phenomenological Foundations of Cognition, Language, and Computation--(Same as Linguistics 237, VTSS 178.) Critical analysis of theoretical foundations of the cognitive approach to language, thought, and computation. Readings contrast the rationalistic assumptions of current linguistics and artificial intelligence with alternatives drawn from phenomenology, theoretical biology, and socially-oriented speech act theory. Emphasis on the relevance of theoretical orientation to the design, implementation, and impact of computer systems dealing with language. 3-4 units, Aut (Staff) MWF 10 379. Interdisciplinary Topics--Advanced material that relates computer science to other disciplines is often taught for the first time as a "topics" course, perhaps by a faculty member visiting from another institution. Students may therefore enroll repeatedly in a course with this number. See Time Schedule for topics being currently offered. by arrangement 390. Industrial Practical Training--Provides educational opportunities in high-technology research and development labs in the computing industry. Qualified graduate students engage in internship work and integrate that work into their academic program. Students register in the quarter following internship work, and complete a research report outlining their work activity, problems investigated, key results, and any follow-on projects they expect to perform. Meets the requirements for Curricular Practical Training for students on F-1 visas. Sign up for section number corresponding to your academic adviser. 1 unit, Aut (Staff) by arrangement 393. Computer Laboratory--For graduate students of Computer Science. A substantial computer program is designed and implemented, written report required. Recommended as a preparation for dissertation research. Prerequisite: consent of instructor; register using the section number associated with the instructor. any quarter (Staff) by arrangement 395. Database Project--For graduate students of Computer Science. Use of database management or file systems for a substantial application or implementation of components of database management system. Written analysis and evaluation required. Prerequisite: consent of instructor; register using the section number associated with the instructor. any quarter (Staff) by arrangement 399. Independent Project any quarter (Staff) by arrangement 399P. Independent Project--Graded Satisfactory or No Credit. any quarter (Staff) by arrangement EXPERIMENTAL 409. Topics in Knowledge-Based Software Environments--Focuses on how knowledge-based tools can provide automated assistance in developing conventional software. Topics: wide-spectrum and very-high-level languages, domain theories and formal specifications, correctness-preserving transformation rules, representation and use of programming knowledge (algorithm and data structure design, program optimization, refinement of data and control structure), performance estimation, knowledge-based support for project management, synthesis of parallel programs and architectures. Individual projects. Prerequisites: 22, 243, 257. 3 units, Spr (Smith, Green) TTh 9:30-10:45 425. Artificial Life--Existing carbon-based lifeforms exploit available energy (primarily solar) to organize available matter to survive, reproduce, and evolve, whereas computational forms of artificial life exploit computer time to organize computer memory to the same effect. Extrapolates the computational characteristics of existing lifeforms to life as it might be by presenting artificial life from the perspective of the major tools and the issues of the field. Tools include self-reproducing cellular automata, dynamical systems, genetic algorithms, genetic programming, neural nets, genomic processes, and nanotechnology. Issues: spontaneous emergence of self-replicating and self-improving computer programs, self-replicating matter, programmable matter, algorithmic chemistry, evolution, learning, and emergent computation. 3 units, Win (Koza) MW 1-2:15 426. Genetic Algorithms and Their Applications--Genetic algorithms are mathematical algorithms for search, optimization, and machine learning patterned after the evolutionary processes of reproduction and survival of the fittest. Topics: mathematical justification for genetic algorithms; applications to function optimization, design, games, economics, neural network design, pattern recognition; genetic classifier systems; genetic programming; implementation on parallel computer architectures. 3 units, Spr (Koza) MW 1-2:15 441. Topics in ADA Programming--The ADA language is used as an example for discussing current research in high-level languages for programming large systems and distributed systems. Related developments in specification languages are discussed. Part 1 (the ADA language design and programming techniques): multi-task programming, compilation algorithms for tasking, runtime supervisors for distributed systems in ADA, detection of concurrency error: comparison of ADA with other high level concurrent languages. Part 2: design of specification languages related to ADA, specification, validation, and verification methods for multi-task programs; environments for programming with specifications. Prerequisite: 107. 3 or 4 units, Win (Luckham) TTh 1:15-2:30 alternate years, not given 1993-94 443. Design and Prototyping Languages--Introduction to advanced computer-aided design and prototyping language, tools, and methods aimed at the field of distributed and realtime systems. Hardware and software systems modeling. Students gain a working knowledge of some of the languages and support tools currently used in industry, e.g., VHDL and Verilog, and emerging advanced languages and methodologies presently in the research and experimentation phase. Case studies of specific Languages/Toolsets in the "emerging" category, e.g., LOTOS, Esterel, and Rapide. Case study languages vary each year. Emphasis on foundational principles and theories of concurrent language design, models of distributed and realtime systems behavior, and methods of formal specification, verification, and synthesis. Prerequisites: 112, 106B or 242 or consent of instructors. 3-4 units (De Micheli, Luckham) alternate years, given 1993-94 499. Advanced Reading and Research--For graduate students in Computer Science; consent of instructor required. Register using the section number associated with the instructor. any quarter (Staff) by arrangement GRADUATE SEMINARS 510. Digital Systems Reliability Seminar--(Enroll in Electrical Engineering 385A.) Student/faculty discussions of research problems in the design of reliable digital systems. Areas: fault-tolerant systems, design for testability and system reliability. Emphasis on student presentations and Ph.D. thesis research. 1-4 units, Aut, Win, Spr (McCluskey) 520. Survey of Research Topics in Artificial Intelligence--(Same as Psychology 224.) Topics vary yearly. Some current topics: machine learning and discovery, speech or image or language understanding, automatic programming, formal reasoning, nonmonotonic logic, game playing, intelligent computer assisted instruction, knowledge representation and expert systems. Often involves distinguished outside lecturers who are specialists in these research topics. Prerequisite: 121 or 221, or equivalent. 1 units, Spr (Staff) T 11 522. Knowledge Systems Seminar--Weekly series of informal talks on a variety of AI-related topics: new ideas, research in progress, project overviews, technology transfer, business implication, social issues. 1 unit, Aut, Win, Spr (Staff) F 12:05-1:15 523. Readings in Artificial Intelligence--Primarily intended for students planning to take the AI qualifying exam. A series of lectures and discussions on readings in all areas of artificial intelligence research. Prerequisite: 221. 3 units, Win (Staff) 524. Seminar on Expert Systems Research--(Same as Medical Information Sciences 229.) For graduate students. Historical perspective and technical understanding of research in knowledge-based systems. Classic work from the 1970s and 80s compared with current investigation in the areas of knowledge representation, user interfaces, knowledge acquisition, and control of inference. Enrollment limited to 20. Prerequisite: 221 or 228A, or equivalent. 2 units Spr (Musen, Shortliffe) W 3:30-5 alternate years, not given 1993-94 525. Seminar on Knowledge Acquisition for Expert Systems--(Same as Medical Information Sciences 230.) For graduate students. Discussion of experimental approaches to the construction of expert-system knowledge bases. Topics: interviewing techniques, formal and informal approaches to modeling expert knowledge, automated tools which facilitate knowledge acquisition. Enrollment limited to 20. Prerequisite: 228A or equivalent. 2 units (Musen) alternate years, given 1993-94 526. Topics in Perception Seminar--(Enroll in Psychology 266.) Current research in perceptual psychology, neurophysiology of perception, computational models, and computer vision. Topics: color vision, visual motion perception, binocular vision, shape perception, visual search, psycho-acoustics, auditory localization, music perception, attention. 1-3 units, Win (Heeger) 527. Robotics Seminar--Recent research in motion planning, computer vision, manipulation, and mobile robot navigation. Invited speakers present recent results and summaries of articles from the current literature. 1 unit, Aut, Spr (Khatib) M 4:15 530. Applied Mathematics/Scientific Computing Seminar 1-3 units, any quarter (Staff) by arrangement 531. Numerical Analysis/Scientific Computing Seminar 1 unit, any quarter (Golub) M 4:15-5:30 540. Seminar on Computer Systems--(Enroll in Electrical Engineering 380.) Discussion of current research in the design, implementation, analysis, and use of computer systems ranging from integrated circuits to operating systems and programming languages. 1 unit, Aut, Win, Spr (Staff) 545. Database Research Seminar--Presentations of current research and industrial innovation. Emphasis on discussion and evaluation. Topics: database models, knowledge bases, high performance algorithms, large and distributed databases, application of artificial intelligence techniques to databases, and architecture of future information systems. 1 unit, any quarter (Milton) F 3:15 547. Human-Computer Interaction Seminar--Weekly speakers on topics related to human-computer interaction design. 1 unit, Aut, Win, Spr (Winograd) W 12-1:05 548. Distributed Systems Research Seminar--Primarily for Ph.D. students and other researchers in these areas. Recent research in distributed operating systems, computer communications, parallel machines, parallel programming, and distributed applications. Invited speakers from Stanford and elsewhere present topics and results of current interest. 1 unit, Spr (Cheriton) Th 4:15