COURSES REQUIRING GRADUATE STUDENT INSTRUCTORS DEPARTMENT OF ELECTRICAL ENGINEERING AND COMPUTER SCIENCES 2000-2001 ACADEMIC YEAR CS 3 INTRODUCTION TO SYMBOLIC PROGRAMMING Introduction to computer programming, emphasizing symbolic computation and functional programming style. Students will write a project of at least 200 lines of code, in a dialect of the LISP programming language. (Lab and Discussion Sessions. GSI must know some dialect of Lisp and UNIX.) CS 3S, CS 9A, CS 9B, CS 9C, CS 9D, CS 9E, CS 9F SELF-PACED PROGRAMMING COURSES The first two of these are self-paced versions of the corresponding introductory lecture courses; the others are 1-unit courses for students who already know how to program in some other language. Languages used include Lisp, C, Fortran, and Pascal. (GSI positions are 10 hrs/wk and involve face-to-face grading and consulting in the CS Self-Paced Center. Activities range from correcting short-answer questions to explaining high-level constructs like recursion. GSI must know at least three of Lisp, C, Fortran, and Pascal, and be familiar with the UNIX operating system. GSI should also enjoy the challenge of saying something intelligent about a program or quiz he or she has not previously encountered.) CS 61A INTRODUCTION TO COMPUTER SCIENCE Introduction to programming and computer science. This course exposes students to techniques of abstraction at several levels: (a) within a programming language, using higher-order functions, manifest types, data-directed programming, and message-passing; (b) between programming languages, using functional and rule-based languages as examples. It also relates these techniques to the practical problems of implementation of languages and algorithms on a von Neumann machine. There are several significant programming projects, programmed in dialect of the LISP language. (Lab and Discussion Sessions. GSI must know Lisp, preferably the Scheme dialect. CS 61B DATA STRUCTURES Fundamental dynamic data structures, including linear lists, queues, trees, and other linked structures; arrays strings, and hash tables. Storage management. Elementary principles of software engineering. Abstract data types. Algorithms for sorting and searching. (Lab and Discussion Sessions. GSI should be familiar with the language C and a reduced- instruction set architecture.) CS 61C MACHINE STRUCTURES The internal organization and operation of digital computers. Machine architecture support for high-level languages, logic, arithmetic, instruction sequencing and operating systems (I/O, interrupts, memory management, process switching). Elements of computer logic design. Trade-offs involved in fundamental architectural design decisions. (Lab and Discussion Sessions. GSI should be familiar with C and the UNIX operating system, and have substantial programming experience.) CS 70 Discrete Mathematics and Probability Logic, infinity, and induction; applications include undecidability and stable marriage problem. Modular arithmetic and GCDs; applications include primality testing and cryptography. Polynomials; examples include error correcting codes and interpolation. Probability including sample spaces, independence, random variables, law of large numbers; examples include load balancing, existence arguments, Bayesian inference. CS 150 COMPONENTS AND DESIGN TECHNIQUES FOR DIGITAL SYSTEMS Design of boolean logic and finite state machines. Standard SSI, MSI and LSI parts. Drawing standards, dependency notation. Implementation with different logic families, mainly TTL and MOSsticks. Synchronous systems design, ALU, memory, tristate andopen-collector busses. Functional blocks in microprocessors. Discussion of a typical example of a microprocessor. Simple I/O switches, LED displays, A/D, D/A. (Lab and Discussion Sessions) CS 152 COMPUTER ARCHITECTURE AND ENGINEERING Instruction set design; register transfer; computer design project requiring about 150 hours; data-path design; controller design; memory system; addressing; microprogramming; Busses, I-O processing; computer arithmetic; survey of real computers and microprocessors. (Discussion Sessions) CS 160 USER INTERFACE DESIGN AND DEVELOPMENT The design, implementation, and evaluation of human computer interfaces. Interface devices (keyboard, pointing, display, audio, etc.), metaphors (desktop, notecards, rooms, ledger sheets, tables, etc.), interaction styles and dialog models, design examples, and user-centered design and task analysis. Interface-development methodologies, implementation tools, testing, and quality assessment. Students will develop a direct-manipulation interface. CS 162 OPERATING SYSTEMS AND SYSTEM PROGRAMMING Basic concepts of operating systems and system programming. Utility programs, subsystems, multiple-program systems. Processes, interprocess communication and synchronization. Memory allocation, segmentation, paging. Loading and linking, libraries. Resource allocation, scheduling, performance evaluation. File systems, storage devices, I/O systems. Protection, security and privacy. (Lab and Discussion Sessions) CS 164 PROGRAMMING LANGUAGES AND COMPILERS Survey of programming languages. The design of modern programming languages. Principles and techniques of scanning, parsing, semantic analysis, and code generation. Implementation of compilers, interpreters, and assemblers. Overview of run-time organization and error handling. (Lab and Discussion Sessions) CS 167 INTRODUCTION TO DISTRIBUTED SYSTEMS Basic concepts on distributed systems. Network architecture and internet routing. Message passing layers and remote procedure call. Process migration. Distributed file systems and cache coherence. Server design for reliability, availability, and scalability. Internet security and electronic commerce. Example applications, from the WWW to email to parallel processing. Distributed system implementation to be done as course project CS 169 SOFTWARE ENGINEERING Ideas and techniques for designing, developing, and modifying large software systems. Function-oriented and object-oriented modular design techniques, designing for re-use and maintainability. Specification and documentation. Verification and validation. Cost and quality metrics and estimation. Project team organization and management. Students will work in teams on a substantial programming project. (Discussion Sessions) CS 170 EFFICIENT ALGORITHMS AND INTRACTABLE PROBLEMS Concept and basic techniques in the design and analysis of algorithms; models of computation; lower bounds; algorithms for optimum search trees, balanced trees and UNION-FIND algorithms; numerical and algebraical algorithms; combinational algorithms. Turing machines, how to count steps, deterministic and nondeterministic Turing machines, NP-completeness. Unsolvable and intractable problems. (Discussion Sessions) CS 172 FORMAL LANGUAGES AND AUTOMATA THEORY Variations on the theme of finite automata. Nondeterminism and regularity. Properties of languages accepted by finite automata; context-free grammars and push-down automata. Turing machines and computability. Time and space bounded computation. Special classes of grammars and languages. (Discussion Sessions) CS 174 COMBINATORICS AND GRAPH THEORY Permutations, combinations, generating functions, recurrence relations, inclusion-exclusion principle, Polya's theorem, Hall's theorem; planar graphs, Euler graphs, Hamiltonian graphs, coloring problems; independence numbers, covering numbers. (Discussion Sessions) CS 182 NEURAL BASIS OF COGNITION AND LANGUAGE The course studies how the computational properties of neural systems and the specific neural structures of the human brain shape the nature of thought and language. The evercise include working with on-line simulation systems as well analysis of neural, cognitive, and linguistic findings. CS 184 FOUNDATIONS OF COMPUTER GRAPHICS An introduction to the principles of computer graphics. A comparison of various display devices. Two-dimensional and three-dimensional transformations such as rotation, scaling, and translation, and their matrix representations. Homogeneous coordinates and projective transformations including several formulations for perspective projection. Algorithms for clipping, hidden surface removal, and antialiasing. Lighting models for reflection, refraction, and transparency. Mathematical techniques for curve and surface representation. (Lab and Discussion Sessions) CS 186 INTRODUCTION TO DATABASE SYSTEMS Introduction to data base systems. Access methods and file systems to facilitate date access. Hierarchical, network, relational and object-oriented data models. Query languages for models. Embedding query languages in programming languages. Database services including protection, integrity control and alternative views of data. High level interfaces including application generators, browsers and report writers. Introduction to transaction processing. Database system implementation to be done as term project. (Discussion Sessions) CS 188 INTRODUCTION TO ARTIFICIAL INTELLIGENCEAND NATURAL LANGUAGE PROCESSING Basic ideas and techniques underlying the design of intelligent computer systems. Topics include heuristic search, problem solving, game playing, knowledge representation, logical inference, planning, reasoning under uncertainty, expert systems, learning, perception, language understanding. (Discussion Sessions) CS 250 VLSI SYSTEMS DESIGN Unified top-down and bottom-up design of integrated circuits and systems concentrating on architectural and topological issues. VLSI architectures, systolic arrays, self-time systems. Trends in VLSI development. Physical limits. Tradeoffs in custom-design, standard cells, gate arrays. VLSI design tools. CS 252 GRADUATE COMPUTER ARCHITECTURE Graduate survey of contemporary computer organizations covering: early systems, CPU design, instruction sets, control, processors, busses, ALU, memory, I/O interfaces, connection networks, virtual memory, pipelined computers, multiprocessors, and case studies. CS 264 IMPLEMENTATION OF PROGRAMMING LANGUAGES Compiler construction. Lexical analysis, syntax analysis. Semantic analysis, code generation and optimization. Storage management. Run-time organization. CS 267 APPLICATIONS OF PARALLEL COMPUTERS Models for parallel programming. Fundamental algorithms for linear algebra, sorting, FFT, etc. Survey of parallel machines and machine structures. Exiting parallel programming languages, vectorizing compilers, environments, libraries and toolboxes. Data partitioning techniques. Techniques for synchronization and load balancing. Detailed study and algorithm/program development of medium sized applications. Possible candidate applications include finite element methods, solution of differential equations, circuit simulation, n-body simulation, database searching, applications in computer vision, graphics and other. (Lab sessions) CS 270 COMBINATORIAL ALGORITHMS AND DATA STRUCTURES Design and analysis of efficient algorithms for combinatorial problems. Network flow theory, matching theory, matroid theory; augmenting-path algorithms; branch-and-bound algorithms; data structure techniques for efficient implementation of combinatorial algorithms; analysis of data structures; applications of data structure techniques to sorting, searching and geometric problems. CS 284 COMPUTER AIDED GEOMETRIC DESIGN AND MODELING Mathematical techniques for curve and surface representation including: Hermite interpolation, interpolatory splines, tensed splines, Bezier curves and surfaces, B-splines, Beta-splines, Coons patches, tensor product forms, lofted patches, blending function methods, Boolean sum schemes. CS 285 SOLID FREE-FORM MODELING AND FABRICATION >From shape design to computer-based descriptions suitable for manufacturing or rapid prototyping. Solid modeling techniques and procedural shape generation. Effective data structures and unambiguous part description formats. Algorithms for dealing with Boolean operations and for machine tool path planning. Problems of finite-precision geometry and machinging tolerances. Introduction to some rapid prototyping techniques based on Solid Free-Form Fabrication and NC machining. Other advanced topics and recent developments in the field.