31. Introduction to Computer Science I. Lecture, four hours; discussion, two hours; outside study, six hours. Limited to majors in computer science and engineering and computer science majors. Introduction to computer science via theory, applications, and programming. Operators and control structures. Functions, parameters, scope rules. Recursion. Arrays, strings, pointers. Object-oriented programming, classes, data abstraction. Input/output. Examples and exercises from computer science theory and applications. 32. Introduction to Computer Science II. Lecture, four hours; discussion, two hours; outside study, six hours. Prerequisite: course 31. Limited to majors in computer science and engineering and computer science majors. Not open to students with credit for course 23. Object-oriented programming, overloading, inheritance, polymorphism. Object-oriented view of data structures: lists, stacks, queues. Memory management. Sorting and searching algorithms and their performance. Trees, graphs, and associated algorithms. Case studies and exercises from computer science applications. 33. Systems Programming (5 units). (Formerly numbered 24.) Lecture, four hours; discussion, two hours; outside study, nine hours. Prerequisite: course 32. Limited to majors in computer science and engineering and computer science majors. Not open to students with credit for former course 24. Introductory course on 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, I/O programming, memory management, file systems. 111. Operating Systems Principles. Lecture, four hours; laboratory, two hours; outside study, six hours. Prerequisites: courses 32 or equivalent, 33. Introduction to design and performance evaluations of modern operating systems. Mapping and binding of addresses. Organization of multiprogramming and multiprocessing systems; interrupts, process model, and interlocks. Resource allocation models and problem of deadlocks. Scheduling, synchronization. Memory management, virtual memory. I/O control, file systems. 130. Software Engineering. Lecture, four hours; laboratory, two hours; outside study, six hours. Prerequisite: course 32. Structured programming, program specification, program proving, modularity, abstract data types, composite design, software tools, software control systems, program testing, team programming. 131. Programming Languages. Lecture, four hours; laboratory, two hours; outside study, six hours. Prerequisites: courses 32, 33. Study, comparison, and evaluation of alternative strategies for language specification, data description, data control, program modularity, instruction sequencing, and language implementations. Use of a few languages selected from FORTRAN 77, ADA, SNOBOL 14, LISP, MODULA 2, and PROLOG to illustrate particular implementations of some of above features. 132. Compiler Construction. Lecture, four hours; discussion, two hours; outside study, six hours. Prerequisites: courses 32, 131, 181. Compiler structure; lexical and syntactic analysis; semantic analysis and code generation; theory of parsing. 133. Parallel and Distributed Computing. 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. 141. Basic Methods of Data Organization. Lecture, four hours; laboratory, two hours; outside study, six hours. Prerequisite: course 32 or consent of instructor. Fundamental techniques for organizing and manipulating data, stressing relationships to performance, time/storage trade-offs. Sequential and linked storage allocation for linear lists, multilinked structures. Trees: implementation, traversals, mathematical properties. Graphs and networks: memory representation, algorithms. Dynamic storage allocation. External storage devices. Database concepts and architectures. Topics include sorting-searching, algorithmic analysis, graph theory, concepts underlying file management. 143. Introduction to Database Systems. Lecture, four hours; discussion, two hours; laboratory, two hours; outside study, four hours. Prerequisite: course 32 or consent of instructor. Information systems and database systems in enterprises. File organization and secondary storage structures. Relational model and relational database systems. CODASYL and other data management approaches. Database design principles. Transactions, concurrency, and recovery. Integrity and authorization. 170A. Introduction to Scientific Computing. Lecture, four hours; laboratory, two hours; outside study, six hours. Prerequisite: senior standing in computer science or consent of instructor. Introduction to scientific modeling and simulation, using the very high-level computer languages MATHEMATICA and MAPLE. Extensive coverage of programming in MATHEMATICA, with applications involving engineering modeling; simulation term project required. 174. Elements of Computer Graphics. Lecture, two hours; laboratory, two hours; outside study, eight hours. Requisite: course 32. Hardware and software elements of computer graphics systems. Graphics languages. Graphic workstations and specialized I/O devices. Design and development of interactive graphics programs. 181. Introduction to Formal Languages and Automata Theory. Lecture, four hours; discussion, two hours; outside study, six hours. Prerequisites: Mathematics 61 and junior standing in computer science, or consent of instructor. 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. 190. Computer Science Design Project. Lecture, four hours; outside study, eight hours. Prerequisite: senior standing with adequate background in hardware, software, and computer applications. Limited to majors in computer science and engineering and computer science majors. Basic concepts of design of projects in computer science, including interpretation of specifications, subtasking, design of experiments, data analysis and performance evaluation, cost engineering, reliability, and societal and safety considerations. 231A. Advanced Topics in Programming Languages. Prerequisite: course 131. Presentation, analysis, and discussion of specialized programming languages, new higher-level languages, and new and/or advanced features of programming languages. 232A. Operational Semantics of Programming Languages. Lecture, four hours; outside study, eight hours. Prerequisites: courses 131, 181, or equivalent. Introduction to formal semantics. Interpreter-based operational definitions. Induction and structural operational semantics. Proving equivalence between structural and interpreter-based operational definitions. Static and dynamic semantics. Example operational definitions of functional, imperative, concurrent, logic, and object-oriented programming languages. 232B. Semantics of Programming Languages. Prerequisites: courses 131 and 181, or consent of instructor. Denotational semantics of programming languages. Notation and foundations. Expressions, commands, declarations, and other constructs. Environments, stores, and continuations. Examples. Relations between semantic definitions of programming languages. Applications of current research interest. 233A. Parallel Programming. Lecture, four hours; other, eight hours. Prerequisites: 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. 233B. Verification of Concurrent Programs. Lecture, four hours; other, eight hours. Prerequisite: 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. 234A. Correctness Proofs. Prerequisite: consent of instructor. Theoretical and practical aspects of correctness proofs. Partial correctness, total correctness, and termination. Axiomatic semantics and proof systems. Abstraction and correctness of implementations. Formulation, execution, and assessment of correctness proofs. Topics of current research interest. 235A. Logic Programming and PROLOG. Lecture, four hours; outside study, eight hours. Prerequisite: graduate standing in computer science. Logic programming; PROLOG as an approximation thereof; PROLOG programming techniques; translation and definite clause grammars; rewriting and interpreters; implementation of PROLOG; constraint logic programming and other proposed extensions to PROLOG; parallel logic programming systems. 239. Current Topics in Computer Science: Programming Languages and Systems (2 to 12 units). Lecture, four hours. Prerequisite: consent of instructor. 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. 240A. Databases and Knowledge Bases. Lecture, four hours; outside study, eight hours. Prerequisite: 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. 241A. Object-Oriented and Semantic Database Systems. Lecture, three and one-half hours; recitation, 30 minutes; laboratory, one hour; outside study, eight hours. Prerequisite: course 143 or equivalent. Object and database principles. Data models and accessing. Database systems architecture and functional components. Extended relational systems. Object and semantic systems. Systems comparison. Database design, organization, indexing, and performance. Other topics at discretion of instructor. 241B. Pictorial and Multimedia Database Systems. Lecture, three and one-half hours; recitation, 30 minutes; outside study, nine hours. Prerequisites: courses 143, 241A. Pictorial and multimedia information system requirements. Data models and accessing; alternatives. Database systems. Visual languages and communication. Hypertext. Database design and organization, logical and physical. Database heterogeneity and distribution. Other topics at discretion of instructor. 243B. Abstract Data Types and Program Specification. Lecture, four hours; outside study, eight hours. Prerequisites: courses 32 or equivalent, 181. Notions of abstract data type and abstract program specification permit one to understand how programs manipulate data, independently of their implementations. These notions also give powerful techniques for program structuring and verification. Programming exercises. 244A. Distributed Database Systems. Lecture, four hours; outside study, eight hours. Prerequisites: 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. 245A. Intelligent Information Systems. Lecture, four hours; outside study, eight hours. Prerequisites: courses 241A and 255A, or consent of instructor. 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. 249. Current Topics in Data Structures (2 to 12 units). Prerequisite: consent of instructor. 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. 255A. Distributed Processing Systems. Lecture, four hours; outside study, eight hours. Prerequisites: 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. 259. Current Topics in Computer Science: System Design/Architecture (2 to 12 units). Lecture, four hours. Prerequisite: consent of instructor. 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. 262A. Reasoning with Partial Beliefs. Prerequisite: course 112 or Electrical Engineering 131A or equivalent. Review of several formalisms for representing and managing uncertainty in reasoning systems; presentation of comprehensive description of Bayesian inference using belief networks representation. 262B. Knowledge-Based Systems. Prerequisite: 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. 262C. Computer Methods of Data Analysis and Model Formation. Prerequisite: course 112 or equivalent or consent of instructor. 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. 265A. Machine Learning. Prerequisites: courses 263A, 264A, consent of instructor. 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. 267A. Neural Models. Prerequisites: graduate standing, consent of instructor. 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. 267B. Artificial Neural Systems and Connectionist Computing. Prerequisites: graduate standing, consent of instructor. 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. 268. Machine Perception. Prerequisites: graduate standing, consent of instructor. Course 168 may be taken concurrently. 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. 268CN. Computational Neuroscience. Lecture, four hours; discussion, two hours; outside study, eight hours. Prerequisite: consent of instructor. Computational neuroscience as a paradigm of formal analysis and demonstrations of how to correctly interpret sensory data by discovering constraints from the natural world. Neural networks and connectionist models as a paradigm for parallel and concurrent computation and application to problem of vision, multimodel sensory interpretation, and learning. 268S. Seminar: Computational Neuroscience (2 units). Prerequisite: consent of instructor. Intended 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 units). Prerequisite: consent of instructor. 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. 270A. Computer Methodology: Advanced Numerical Methods. Prerequisites: graduate standing in computer science or engineering, Electrical Engineering 103 or Mathematics 141B or comparable experience with numerical computing. 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. 271A. Modeling and Simulation of Lumped Parameter Systems. Lecture, eight hours. Recommended (but not prerequisite): course 270A or equivalent. 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. 271B. Modeling and Simulation of Distributed Parameter Systems. Lecture, eight hours. Recommended (but not prerequisite): course 270A or equivalent. 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. 271C. Seminar: Advanced Simulation Methods (2 units). Prerequisite: course 271A or equivalent. 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. Lecture, four hours; outside study, eight hours. Prerequisite: course 172 or consent of instructor. 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. 273A. Digital Processing of Engineering and Statistical Data. Prerequisite: course 173. Computer methods for processing engineering and statistical data. Algorithms to evaluate recursive filter functions, Fourier series, power spectral, analysis correlation computations, and statistical testing. 276A. Pattern Analysis and Machine Intelligence. Prerequisites: graduate standing, consent of instructor. Fundamentals of pattern recognition, feature extraction and selection, autonomous learning, clustering, and machine intelligence.