## Graduate Courses

The faculty has approval to offer the following courses in the academic years 2007–2008 and 2008–2009; however, not all courses are taught each semester or summer session. Students should consult the *Course Schedule* to determine which courses and topics will be offered during a particular semester or summer session. The *Course Schedule* may also reflect changes made to the course inventory after the publication of this catalog.

Unless otherwise stated below, each course meets for three lecture hours a week for one semester.

### Computer Sciences: C S

**380C. Compilers.** Basics of static analysis and transformation techniques; exploration in depth of one aspect of compilation and optimization. Computer Sciences 380C and 395T (Topic: *Compilers*) may not both be counted. Prerequisite: Graduate standing; Computer Sciences 357 and 375 are recommended.

**380D. Distributed Computing I.** Models of distributed systems; language issues, proving properties of distributed systems; time, clocks, partial ordering of events; deadlock and termination detection; diffusing computations; computing in hostile environments; distributed resource management. Prerequisite: Graduate standing and Computer Sciences 372.

**380L. Advanced Operating Systems.** Study of the formal structure, design principles, organization, implementation, and performance analysis of multiprogramming and/or multiprocessor computer systems. Prerequisite: Graduate standing, and Computer Sciences 372 or consent of instructor.

**380N. Systems Modeling.** Theory and applications of Markovian models: birth-death models, queueing models, and networks of queues. Numerical methods: computational algorithms, approximation techniques, discrete-event simulation. Performance of scheduling disciplines: priority, time-sharing, multiple access. Prerequisite: Graduate standing and an undergraduate course in probability theory.

**380P. Parallel Systems.** Explores parallel systems, from languages to hardware, from large-scale parallel computers to multicore chips, and from traditional parallel scientific computing to modern uses of parallelism. Includes discussion of and research methods in graphics, languages, compilers, architecture, and scientific computing. Computer Sciences 380P and 395T (Topic: *Parallel Systems*) may not both be counted. Prerequisite: Graduate standing.

**380S. Theory and Practice of Secure Systems.** Survey of modern security, designed to introduce the basic techniques used in the design and analysis of secure systems. Prerequisite: Graduate standing, and Computer Sciences 353 and 372 or consent of instructor.

**381K. Artificial Intelligence.** Use of computers in problem solving, game playing, theorem proving, natural language understanding, and related tasks; methods of search, knowledge representation, learning, and other topics. Prerequisite: Graduate standing, and Computer Sciences 351 or consent of instructor.

**382M. Advanced Computer Architecture.** Algorithms and their realizations, special techniques for coding, addressing, and control; integration of computer units; relations between programming and design considerations. Prerequisite: Graduate standing.

**383C. Numerical Analysis: Linear Algebra.** Same as Computational and Applied Mathematics 383C and Mathematics 383E. Survey of numerical methods in linear algebra: floating-point computation, solution of linear equations, least squares problems, algebraic eigenvalue problems. Prerequisite: Graduate standing, either consent of instructor or Mathematics 341 or 340L, and either Mathematics 368K or Computer Sciences 367.

**383D. Numerical Analysis: Interpolation, Approximation, Quadrature, and Differential Equations.** Same as Computational and Applied Mathematics 383D and Mathematics 383F. Survey of numerical methods for interpolation, functional approximation, integration, and solution of differential equations. Prerequisite: Graduate standing; either consent of instructor or Mathematics 427K and 365C; and Computational and Applied Mathematics 383C, Computer Sciences 383C, or Mathematics 383E.

**384G. Computer Graphics.** Same as Computational and Applied Mathematics 384G. Advanced material in computer graphics, including in-depth treatments of techniques for realistic image synthesis, advanced geometric modeling methods, animation and dynamic simulation, scientific visualization, and high-performance graphics architectures. Prerequisite: Graduate standing; and Computer Sciences 354 or another introductory course in computer graphics, or equivalent background and consent of instructor.

**384M. Multimedia Systems.** Theoretical and practical issues in advanced systems, including multimedia systems, digital audio and video compression techniques, operating system and network support for digital audio and video, and multimedia conferencing systems. Prerequisite: Graduate standing; and either Computer Sciences 356 and 372 or 380D and 380L.

**384R. Geometric Modeling and Visualization.** Computational image processing, computational geometry and geometric modeling algorithms with an emphasis on spatial realism, and the programmatic use of physiological simulation and visualization to quantitatively depict how things work at the molecular, cellular, tissue, organ, and system levels. Computer Sciences 384R and 395T (Topic: *Graphics, Modeling, and Visualization*) may not both be counted; Computer Sciences 384R and 395T (Topic: *Multiscale Bio-Modeling and Visualization*) may not both be counted; Computer Sciences 384R and 395T (Topic: *Physically Based Geometric Modeling*) may not both be counted. Prerequisite: Graduate standing, and Computer Sciences 354 or consent of instructor.

**384V. Introduction to VLSI Design.** Basic techniques required to design custom negative metal oxide semiconductor digital integrated circuits. Prerequisite: Graduate standing, and Computer Sciences 352 or consent of instructor.

**386C. Dependable Computing Systems.** System models from synchronous to asynchronous, with emphasis on in-between models such as the timed asynchronous model. Control structures such as timed state-transition systems, and constraints in temporal and real-time logics. Analysis techniques such as model checking of timed systems, and extended Presburger arithmetic. Basic building blocks such as clock synchronization, synchronous atomic broadcast, time-bounded membership protocols, real-time scheduling theory, and state recovery methods. Practical implementation issues such as special operating system data structures and algorithms, open system design, and security concerns. Computer Sciences 386C and 395T (Topic: *Dependable Computing Systems*) may not both be counted. Prerequisite: Graduate standing, and an undergraduate course in operating systems or consent of instructor.

**386D. Database Systems.** Introduction to the principles of database systems, including fundamental ideas and algorithms used in the construction of centralized database management systems, distributed database management systems, and database machines and their roles in Internet infrastructure. Topics include data storage and indexing algorithms, query processing and optimization, concurrency control, recovery, XML and object-oriented databases, database evaluation and tuning, and recent directions in database research. Computer Sciences 386 and 386D may not both be counted; Computer Sciences 386D and 387H may not both be counted. Prerequisite: Graduate standing and Computer Sciences 347 and 375.

**386K. Numerical Treatment of Differential Equations.** The analysis of numerical methods for solving ordinary and partial differential equations. Only one of the following may be counted: Computational and Applied Mathematics 386K, Computer Sciences 386K, Mathematics 383G. Prerequisite: Graduate standing; and Computational and Applied Mathematics 383D, Computer Sciences 383D, Mathematics 368K, 383F, or consent of instructor.

**386L. Programming Languages.** Topics include formal syntax representations, program correctness, typing, and data abstraction. Features and problems in languages that allow parallelism. Exploration of different programming styles, such as imperative, functional, logic, data flow, and object-oriented programming. Prerequisite: Graduate standing, and Computer Sciences 345 or consent of instructor.

**386M. Communication Networks.** Switching techniques, network and protocol architectures, communication protocols, resource allocation problems, internetworking, design and analysis methods. Prerequisite: Graduate standing.

**386S. Network Protocol Security.** Techniques and research in Internet and network security. Computer Sciences 386S and 395T (Topic: *Secure Network Protocols*) may not both be counted. Prerequisite: Graduate standing.

**386W. Wireless Networking.** Fundamental concepts and principles of wireless network technologies and protocol design, ranging from physical layer to application layer, and in-depth studies of current wireless research. Computer Sciences 386W and 395T (Topic: *Wireless Networking*) may not both be counted. Prerequisite: Graduate standing.

**388. Natural Language Processing.** Computational methods for syntactic and semantic analysis of structures representing meanings of natural language; study of current natural language processing systems; methods for computing outlines and discourse structures of descriptive text. Prerequisite: Graduate standing, and a course in artificial intelligence or consent of instructor.

**388C. Combinatorics and Graph Theory.** Counting, matching theory, extremal set theory, Ramsey theory, probabilistic method, linear algebra method, coding theory. Applications to computer science, including randomized algorithms. Prerequisite: Graduate standing, and Computer Sciences 336 or the equivalent or consent of instructor. An understanding of elementary proof and counting techniques is assumed.

**388F. Automata and Formal Languages.** Formal grammars, languages and related classes of automata, language hierarchies, operations on languages, decidability, related complexity issues, closure properties, other classes of automata. Prerequisite: Graduate standing, and Linguistics 340 or consent of instructor.

**388G. Algorithms: Techniques and Theory.** Sorting and searching algorithms, graph algorithms, algorithm design techniques, lower bound theory, fast Fourier transforms, NP-completeness. Prerequisite: Graduate standing, and Computer Sciences 357 or the equivalent or consent of instructor.

**388H. Cryptography.** Surveys the foundations of cryptography from formal notions of security to fundamental protocols, including one-way functions, encryption, pseudorandom generators, signature schemes, and zero-knowledge. Prerequisite: Graduate standing, and Computer Sciences 353 or consent of instructor.

**388L. Introduction to Mathematical Logic.** Introduction to some of the principal topics of mathematical logic: propositional and predicate calculus; Gödel's completeness theorem; first-order theories; formalizing mathematical reasoning; first-order arithmetic; recursive functions; Gödel's incompleteness theorems; axiomatic set theory. Prerequisite: Graduate standing and experience in abstract mathematical thinking.

**388M. Communication Complexity.** Covers the most important models of communication complexity and their applications, including recent research results and various open problems. Computer Sciences 388M and 395T (Topic: *Communication Complexity*) may not both be counted. Prerequisite: Graduate standing.

**388P. Parallel Algorithms.** Parallel algorithm design on shared memory machines (PRAMs); parallel complexity results; lower bounds; relationship of PRAM model to other models of parallel computation. Prerequisite: Graduate standing; and Computer Sciences 357 or the equivalent, or Computer Sciences 388G, or consent of instructor.

**388R. Randomized Algorithms.** The design and analysis of efficient randomized algorithms. Computer Sciences 388R and 395T (Topic: *Randomized Algorithms*) may not both be counted. Prerequisite: Graduate standing, and Computer Sciences 357 or consent of instructor.

**388S. Formal Semantics and Verification.** Sequential execution: partial and total correctness; deductive, operational, and denotational semantics; formal derivation of programs; parallel execution: partial correctness, deadlock, and starvation; methodology, parallel versus distributed execution. Prerequisite: Graduate standing and consent of instructor.

**388T. Theory of Computation.** Models of computation, decidability, complexity theory, relations between complexity classes, reductions, and completeness; NP-complete problems, randomized computation; approximability; circuit complexity; parallel computation. Prerequisite: Graduate standing, and Computer Sciences 353 or the equivalent or consent of instructor.

**389M. Principles of Object-Oriented Software Technology.** Fundamental principles of object- oriented software engineering, including design and implementation of object-oriented analysis methods, software architectures, translators of high-level programming language representations, translations to multiple-software architectures. Prerequisite: Graduate standing, Computer Sciences 371S or the equivalent, and consent of instructor.

**389R. Recursion and Induction I.** The development of a formal theory for reasoning about computer programs, with emphasis on recursively defined functions in the LISP style and proof by mathematical induction. Heavy emphasis on student discovery and presentation of proofs. Prerequisite: Graduate standing.

**390D. Distributed Computing II.** Synchronous and asynchronous algorithms, with particular emphasis on notations for expressing the algorithms and logics for reasoning about them. Algorithms from a variety of application areas and for a variety of architectures. Prerequisite: Graduate standing and Computer Sciences 380D.

**391K. Artificial Intelligence II.** Advanced course in artificial intelligence. Topics include planning, probabilistic reasoning, truth maintenance, abduction, model-based diagnosis, and speech recognition. Prerequisite: Graduate standing, and Computer Sciences 381K or equivalent knowledge of artificial intelligence and LISP.

**391L. Machine Learning.** Computing systems that automatically improve their performance with experience, including various approaches to inductive classification such as version space, decision tree, rule-based, neural network, Bayesian, and instance-based methods; as well as computational learning theory, explanation-based learning, and knowledge refinement. Prerequisite: Graduate standing, and Computer Sciences 381K or equivalent knowledge of artificial intelligence and LISP.

**392C. Methods and Techniques for Parallel Programming.** Models of parallel fundamental concepts for representation of parallel computation structures, study of representative parallel programming languages, formulation of languages and translation methods, translation of parallel programs to multiple targets, laboratory exercises in parallel programming. Prerequisite: Graduate standing and consent of instructor.

**392F. Feature-Oriented Programming.** Software design and program synthesis, including automatic programming, transformation systems, generative programming (metaprogramming), software product lines, feature models, compositional verification, metaobject protocols and aspect-oriented programming, feature interactions, multidimensional separation of concerns, modularly extensible programming languages, program algebras and category theory, and model-driven engineering. Computer Sciences 392F and 395T (Topic: *Feature-Oriented Programming*) may not both be counted. Prerequisite: Graduate standing, and a basic knowledge of Java, compilers and grammars, and object-oriented design methods.

**393C. Agent-Based Electronic Commerce.** Focuses on the intersection of computer sciences (including multiagent systems and machine learning), economics, and game theory. Explores economic mechanisms of exchange suitable for use by automated intelligent agents, including auctions and auction theory, game theory and mechanism design, and autonomous bidding agents. Students demonstrate programming proficiency in a trading agent competition. Computer Sciences 393C and 395T (Topic: *Agent-Based Electronic Commerce*) may not both be counted. Prerequisite: Graduate standing.

**393D. Topics in Numerical Analysis.** Recent topics have included numerical methods in ordinary differential equations, numerical methods in partial differential equations, computational problems in linear algebra, numerical solution of systems of equations, numerical methods in functional approximation, numerical integration. May be repeated for credit when the topics vary. Some sections are offered on the credit/no credit basis only; these are identified in the *Course Schedule*. Prerequisite: Graduate standing and consent of instructor.

**393N. Numerical Solution of Elliptic Partial Differential Equations.** Same as Computational and Applied Mathematics 393M and Mathematics 393N. The numerical solution of large systems of linear algebraic equations arising in the solution of elliptic partial differential equations by discretization methods. Prerequisite: Graduate standing; and Computational and Applied Mathematics 386K, Computer Sciences 386K, Mathematics 383G, or consent of instructor.

**393R. Autonomous Robots.** Covers the steps necessary to create and program fully functional teams of autonomous robots, including locomotion, object manipulation, vision (segmentation and object detection), localization, inter-robot communication, Kalman filters and control theory, individual behavior creation, and multiagent coordination and strategic reasoning. Computer Sciences 393R and 395T (Topic: *Autonomous Robots*) may not both be counted. Prerequisite: Graduate standing.

**394F. Knowledge Representation and Reasoning.** Surveys the research and practice of building knowledge systems, including knowledge representation, automated reasoning, knowledge acquisition, and explanation generation. Prerequisite: Graduate standing; and Computer Sciences 381K or the equivalent or consent of instructor.

**394N. Neural Networks.** Biological information processing; architectures and algorithms for supervised learning, self-organization, reinforcement learning, and neuro-evolution; theoretical analysis; hardware implementations and simulators; applications in engineering, artificial intelligence, and cognitive science. Prerequisite: Graduate standing and consent of instructor.

**394P. Automatic Programming.** Automatic generation of computer programs from high-level specifications. Program analysis, optimization, and transformation; partial evaluation; object-oriented programming; transformation of formal specifications; specialization of generic procedures; views. Prerequisite: Graduate standing. Computer Sciences 375 and 381K are recommended.

**394R. Reinforcement Learning: Theory and Practice.** Introduces the theory and practice of modern reinforcement learning, with emphasis on temporal difference learning algorithms. Computer Sciences 394R and 395T (Topic: *Reinforcement Learning: Theory and Practice*) may not both be counted. Prerequisite: Graduate standing.

**195, 295, 395. Conference Course.** May be repeated for credit when the topics vary. Prerequisite: Graduate standing and consent of instructor.

**195T, 395T. Topics in Computer Sciences.** From eight to fifteen topics are offered each semester; topics are announced in the *Course Schedule*. One or three lecture hours a week for one semester. May be repeated for credit when the topics vary. Computer Sciences 195T is offered on the credit/no credit basis only. Prerequisite: Graduate standing; complete prerequisite varies with the topic and is given in the *Course Schedule*.

**Topic 1: Parallel Computations.**Computer Sciences 395T (Topic 1) is same as Computational and Applied Mathematics 395T (Topic 1:*Parallel Computations*).

**396. Research Practice and Experience.** Open only to those in their first two years as graduate students in computer sciences. Designed to provide an early research experience for new doctoral students in computer sciences. Students conduct an independent research project and present the results. Individual instruction. Offered on the credit/no credit basis only. May not be counted toward a master's degree in computer sciences. Prerequisite: Graduate standing.

**396M. Advanced Networking Protocols.** Topics include routing, multiple access, internetworking, security, performance models, and verification methods. Prerequisite: Graduate standing.

**698. Thesis.** The equivalent of three lecture hours a week for two semesters. Offered on the credit/no credit basis only. Prerequisite: For 698A, graduate standing in computer sciences and consent of the graduate adviser; for 698B, Computer Sciences 698A.

**398T. Supervised Teaching in Computer Sciences.** Supervised teaching experience, and seminar focused on curriculum construction and teaching methods. Offered on the credit/no credit basis only. Prerequisite: Graduate standing and appointment as a teaching assistant.

**399R, 699R, 999R. Dissertation.** Offered on the credit/no credit basis only. Prerequisite: Admission to candidacy for the doctoral degree.

**399W, 699W, 999W. Dissertation.** Offered on the credit/no credit basis only. Prerequisite: Computer Sciences 399R, 699R, or 999R.