Computer Sciences
continued
Graduate Courses
The faculty has approval to offer the following courses in the academic years 20032004 and 20042005; 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.
380K. Statistical Applications of Electronic Computers.
Development and application of statistical and mathematical algorithms, computational techniques, and simulation methods to problems in management science and business administration. Prerequisite: Graduate standing and consent of instructor.
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: birthdeath models, queueing models, and networks of queues. Numerical methods: computational algorithms, approximation techniques, discreteevent simulation. Performance of scheduling disciplines: priority, timesharing, multiple access. Prerequisite: Graduate standing and an undergraduate course in probability theory.
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: floatingpoint computation, solution of linear equations, least squares problems, algebraic eigenvalue problems. Prerequisite: Graduate standing, either consent of instructor or Mathematics 341 (or 311) 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 indepth treatments of techniques for realistic image synthesis, advanced geometric modeling methods, animation and dynamic simulation, scientific visualization, and highperformance 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; either Computer Sciences 356 and 372 or 380D and 380L.
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.
386. Database Management.
Advanced course in database management concepts and techniques. Topics: schema, logical, physical structures; hierarchical, network, relational, and setoriented data models; operations on data models; language interfaces; review of operational database management systems; current issues in database management systems development. Prerequisite: Graduate standing and Computer Sciences 347.
386K. Numerical Treatment of Differential Equations.
Same as Computational and Applied Mathematics 386K and Mathematics 383G. The analysis of numerical methods for solving ordinary and partial differential equations. 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 objectoriented 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.
387H. Database System Implementation.
Principles of centralized and distributed database system implementation, parallelism in database machines, rulebased and nonrulebased query optimization, concurrency control (serializability, multigranularity locking, concurrent operations on file structures), performance modeling, objectoriented databases (inheritance, persistence, userdefined types, data languages, data models), extensible database systems, heterogeneous database systems. Prerequisite: Graduate standing, and Computer Sciences 347 or consent of instructor.
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, NPcompleteness. Prerequisite: Graduate standing, and Computer Sciences 357 or the equivalent 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; firstorder theories; formalizing mathematical reasoning; firstorder arithmetic; recursive functions; Gödel's incompleteness theorems; axiomatic set theory. Prerequisite: Graduate standing and experience in abstract mathematical thinking.
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.
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; NPcomplete 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 ObjectOriented Software Technology.
Fundamental principles of objectoriented software engineering, including design and implementation of objectoriented analysis methods, software architectures, translators of highlevel programming language representations, translations to multiplesoftware 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, modelbased 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, rulebased, neural network, Bayesian, and instancebased methods; as well as computational learning theory, explanationbased 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.
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.
394F. Knowledge Representation and Reasoning.
Case studies of existing expert systems; choosing appropriate application domains; knowledge acquisition; knowledge representation; reasoning under uncertainty; expert system software tools. Each student constructs an expert system. Prerequisite: Graduate standing, Computer Sciences 351 and 381K or their equivalents, and consent of instructor.
394N. Neural Networks.
Biological information processing; architectures and algorithms for supervised learning, selforganization, reinforcement learning, and neuroevolution; 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 highlevel specifications. Program analysis, optimization, and transformation; partial evaluation; objectoriented programming; transformation of formal specifications; specialization of generic procedures; views. Prerequisite: Graduate standing. Computer Sciences 375 and 381K are recommended.
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.
