Date: Tue, 05 Nov 1996 00:33:28 GMT Server: NCSA/1.5 Content-type: text/html Last-modified: Thu, 31 Oct 1996 21:11:31 GMT Content-length: 56505 Computer Sciences Courses

Computer Sciences Courses

General Information about Courses

Courses numbered 399 and below may be taken for undergraduate credit only. Courses numbered 400 through 699 may be taken by either undergraduate or graduate students. Courses numbered 700 or above are intended only for graduate students. Undergraduates are allowed to take courses numbered 700 or above, but only if permission is obtained from the dean's office.

Courses offered less than once every two years are marked as ``infrequently offered;'' students should not count on taking these classes when planning their schedules. Tentative timetables for upcoming semesters are available.

World-Wide Web pages for the current semester's offerings of many Computer Sciences courses are available. Additional information about many cross-listed courses can be found via the College of Engineering's and the Department of Mathematics' WWW home pages.

 

110 Introduction to Computer Programming 1 cr.

This course is designed to give engineering students an introduction to a computer programming language, such as Fortran or C. It will cover elementary concepts such as variable type, control structures, loops, and arrays. Prereq: Advanced high school mathematics. Open to Fr.  

132 Using Computers 4 cr.

Introduction to use of computers. Some programs in Basic, but emphasis on productivity tools such as word processing, spreadsheets, graphics, and telecommunications. Consideration of societal impacts of computers. Not intended for Computer Sciences majors. Prereq: Minimum mathematical competency (two years of high school math). Open to Fr.  

302 Algebraic Language Programming 3 cr.

Construction of algorithms; problem solving; instruction and experience in the use of at least one procedure-oriented language (e.g., Pascal or Fortran); survey of other such languages, advanced programming techniques. Prereq: Advanced high school mathematical preparation or some college work in mathematics, statistics or logic; or consent of instructor. Open to Fr.  

310 Problem Solving using Computers 3 cr.

Gives engineering students an introduction to computer and analytical skills to use in their subsequent course work and professional development. Discusses several methods of using computers to solve problems, including elementary Fortran and C programming techniques, the use of spreadsheets, symbolic manipulation languages, and software packages. Techniques will be illustrated using sample problems drawn from elementary engineering. Emphasis on introduction of algorithms with the use of specific tools to illustrate the methods. Prereq: Math 222 and an elementary knowledge of Fortran or C or Pascal.  

352 Digital Systems Fundamentals 4 cr. (also ECE)

Logic components, Boolean algebra, combinational logic analysis and synthesis, synchronous and asynchronous sequential logic analysis and design, digital subsystems, computer organization and design. Prereq: CS 302 or equivalent. Not open to students with EGR classification.  

354 Machine Organization and Basic Systems 4 cr. (also ECE)

An introduction to current system structures of control, communication, memories, processors and I-O devices. Projects involve detailed study and use of a specific small computer hardware and software system. Prereq: CS 302 or consent of instructor. Open to Fr.  

364 Introduction to Database Management Systems 3 cr.

Design, use, and application of database management systems. Role of a database management system as a corporate decision-making tool. The Entity-Relationship and Relational data models for database design. File structures, data independence, integrity, privacy, security, application development, and the role of the database administrator. Students use several database management systems. Students may not receive credit for both CS 364 and 564. Prereq: CS 302 or consent of instructor.  

367 Introduction to Data Structures 3 cr.

Study of data structures - specification, application and implementation. Stacks, queues, trees and other important structures. Application to garbage collection, dynamic storage allocation, sorting and searching, symbol tables, and arithmetic expressions. Emphasis on development and analysis of efficient algorithms, including use of structured programming methodology. Prereq: CS 302; Pascal or equivalent.  

371 Technology of Computer-Based Business Systems 3 cr. (also BUS)

Overview of computers, their attendant technology, and the implications of this technology for large-scale, computer-based information systems. Topics include hardware, system software, program development, files, and data communications. Prereq: Bus 370 and CS 367, or equivalent experience with consent of instructor.  

412 Introduction to Numerical Methods 3 cr.

Interpolation, solution of linear and nonlinear systems of equations, approximate integration and differentiation, numerical solution of ordinary differential equations. Prereq: Math 223, CS 302, or equivalent and knowledge of matrix algebra.  

425 Introduction to Combinatorial Optimization 3 cr. (also Math & IE)

Exact and heuristic methods for key combinatorial optimization problems such as: shortest path, maximum flow problems, and the traveling salesman problem. Techniques include problem-specific methods and general approaches such as branch-and-bound, genetic algorithms, simulated annealing, and neural networks. Prereq: Math 221 or CS 302 or consent of instructor.  

458 Computer Graphics 3 cr. (also ME & ECE)

Principles of computational geometry and computer graphics and their application; homogeneous coordinates, projective geometry, 3-D curve and surface representations; data structures and geometric databases, wire-frame and solid geometric representations; graphic I/O device characteristics and cost considerations. Programming exercises and projects based on applications. Prereq: CS 302 and Math 320 or 340, or consent of instructor.  

460 Artificial Intelligence Programming Languages and Tools 3 cr.

Symbolic computation; Lisp programming; Prolog programming; knowledge representation languages based on logic, objects, frames, rules; symbolic pattern matching; automatic inferencing and reasoning techniques; special-purpose languages and computer architectures for artificial intelligence applications. Prereq: CS 367. (Infrequently offered.)  

475 Introduction to Combinatorics 3 cr. (also Math & Stat)

Problems of enumeration, distribution and arrangement. Inclusion-exclusion principle. Generating functions and linear recurrence relations. Combinatorial identities. Graph coloring problems. Finite designs. Systems of distinct representatives and matching problems in graphs. Potential applications in the social, biological, and physical sciences. Puzzles. Emphasis on problem solving. Prereq: Math 320 or 340 and consent of instructor.  

509 Mathematics for Computer Science 3 cr.

Program correctness and termination, invariants, pre- and post-conditions, axiomatic semantics. Representing time and space requirements of programs by summations, recurrences, and generating functions. Exact and asymptotic solutions. Analysis of algorithms for sorting, searching, and data structure traversal. Prereq: CS 367 and Math 222, or consent of instructor. (Infrequently offered.)  

513 Numerical Linear Algebra 3 cr. (also Math)

Direct and iterative solution of linear and nonlinear systems and of eigenproblems. LU and symmetric LU factorization. Complexity, stability, and conditioning. Nonlinear systems. Iterative methods for linear systems. QR-factorization and least squares. Eigenproblems: local and global methods. Prereq: Math 340 or equivalent; CS 302 or equivalent.  

514 Numerical Analysis 3 cr. (also Math)

Polynomial forms, divided differences. Polynomial interpolation. Polynomial approximation: uniform approximation and Chebyshev polynomials, least-squares approximation and orthogonal polynomials. Splines, B-splines and spline approximation. Numerical differentiation and integration. Numerical methods for solving initial and boundary value problems for ordinary differential equations. Prereq: Math 340 or equivalent; CS 302 or equivalent.  

520 Introduction to Theoretical Computer Science 3 cr.

Survey of the basic concepts of theory, including context-free and context-sensitive languages, regular sets, finite and pushdown automata, Turing machines, undecidable problems, complexity with respect to time and space, NP-completeness, and reducibilities. Prereq: CS 367 and Math 222, or consent of instructor.  

525 Linear Programming Methods 3 cr. (also IE, Math, & Stat)

Real linear algebra over polyhedral cones, theorems of the alternative for matrices. Formulation of linear programs. Duality theory and solvability. The simplex method and related methods for efficient computer solution. Perturbation and sensitivity analysis. Applications and extensions, such as game theory, linear economic models and quadratic programming. Prereq: Math 443 or 320 or 340 or consent of instructor.  

526 Advanced Linear Programming 4 cr. ugrad, 3 cr. grad (also IE)

Review of linear programming. Polynomial time methods for linear programming. Quadratic programs and linear complementarity problems and related solution techniques. Solution sets and their continuity properties. Error bounds for linear inequalities and programs. Parallel algorithms for linear and quadratic programs. Prereq: CS 525 or equivalent, CS 302 or equivalent, or consent of instructor. (Infrequently offered.)  

532 Theory and Applications of Pattern Recognition 3 cr. (also ECE & ME)

Pattern recognition systems and components; decision theories and classification; discriminant functions; supervised and unsupervised training; clustering; feature extraction and dimensional reduction; sequential and hierarchical classification; applications of training, feature extraction, and decision rules to engineering problems. Prereq: ECE 430 or Math 431 or consent of instructor.  

533 Image Processing 3 cr. (also ECE)

Mathematical representation of continuous and digital images; models of image degradation; picture enhancement, restoration, segmentation, and coding; pattern recognition, tomography. Prereq: ECE 330 and 333 or consent of instructor.  

536 Introduction to Programming Languages and Compilers
4 cr. ugrad, 3 cr. grad.

Introduction to the theory and practice of compiler design. Comparison of features of several programming languages and their implications for implementation techniques. Several programming projects required. Prereq: CS 367 and either CS 354 or 552.  

537 Introduction to Operating Systems 4 cr. ugrad, 3 cr. grad.

Input-output hardware, interrupt handling, properties of magnetic tapes, discs and drums, associative memories and virtual address translation techniques. Batch processing, time sharing and real-time systems, scheduling resource allocation, modular software systems, performance measurement and system evaluation. Prereq: CS 367 and 354.  

538 Introduction to the Theory and Design of Programming Languages 3 cr.

Design and theory of programming languages: procedural, object-oriented, functional and logic paradigms. Serial and concurrent programming. Execution models and formal specification techniques. Prereq: CS 354 and 367.  

540 Introduction to Artificial Intelligence 4 cr. ugrad, 3 cr. grad.

Principles of knowledge-based search techniques; automatic deduction; knowledge representation using predicate logic, semantic networks, connectionist networks, frames, rules; Applications in problem solving, expert systems, game playing, vision, natural language understanding, learning, robotics; Lisp programming. Prereq: CS 367.  

545 Natural Language and the Computer 3 cr.

The course covers basic techniques and tools in natural language processing: generative grammars, parsing, dictionary construction, semantic networks, generation of text from a knowledge base, natural language interfaces, and machine translation. Prereq: CS 536 or 537 or 564 or consent of instructor.  

547 Computer Systems Modeling Fundamentals 3 cr.

An introduction to basic tools and applications for modeling and analysis of computer systems. Fundamentals of network flow graphs, graph models of computation and stochastic models of computer system performance. Network delay analysis and capacity planning, reachability analysis for deadlock detection in distributed systems, Markov chains, elementary queueing theory, basic concepts of queueing network models and associated analyses. Prereq: Math 223, CS 367 and 354.  

550 Computers and Society 3 cr. (also Social Studies)

The effect of scientific and technological change on social and economic organization. Historical examples. Comparison, with these examples, of the computer and its effect. Consideration of possible uses of computer systems, social change which they would influence, and the choices they present. Prereq: Junior standing. (Infrequently offered.)  

552 Introduction to Computer Architecture 3 cr.

The design of computer systems and components. Processor design, instruction set design, and addressing; control structures and microprogramming; memory management, caches, and memory hierarchies; interrupts and I/O structures. Prereq: ECE/CS 352 and CS/ECE 354; co-req: CS 367.  

558 Introduction to Computational Geometry 3 cr. (also ME and IE)

Introduction to fundamental geometric computations and algorithms, and their use for solving engineering and scientific problems. Computer representations of simple geometric objects and paradigms for algorithm design. Applications from areas of engineering analysis, design and manufacturing, biology, statistics, and other sciences. Prereq: CS 367 or equivalent, Math 223 or equivalent, or consent of instructor.  

562 Expert Systems: Design and Implementation 3 cr.

Design of expert knowledge bases: choice of appropriate representation, knowledge base structure, connection with databases. Knowledge acquisition: possible knowledge sources, logical analysis and formalization, consistency and adequate checking. Inference engine construction and tailoring: choice and control of inferencing strategies, handling uncertain knowledge, achieving efficiency. Display and dialog design. Implementation of explanation capabilities. Evaluation of knowledge engineering environments and languages. Prereq: CS 460 or 540. (Infrequently offered.)  

564 Database Management Systems: Design and Implementation
4 cr. ugrad, 3 cr. grad.

What a database management system is; different data models currently used to structure the logical view of the database: relational, hierarchical, and network. Hands-on experience with relational and network-based database systems. Implementation techniques for database systems. File organization, query processing, concurrency control, rollback and recovery, integrity and consistency, and view implementation. Prereq: CS 367 and 354.  

577 Introduction to Algorithms 3 cr.

Survey of important and useful algorithms for sorting, searching, pattern-matching, graph manipulation, geometry, and cryptography. Paradigms for algorithm design. Techniques for efficient implementation. Prereq: CS 367 and Math 222, or consent of instructor.  

638 Undergraduate Topics in Computing 3 cr.

Prereq: Consent of instructor.  

640 Introduction to Computer Networks 3 cr.

Architecture and components of computer communications networks; protocol concepts and standards; OSI Reference Model; network/protocol architecture examples: Internet, ISO/CCITT, SNA, DECNET, public data networks; local area networks-gateways, internetworking, transport and application protocols. Prereq: CS 537.   

681-682 Senior Honors Thesis 3 cr. per sem.

Prereq: Honors candidacy and consent of instructor.   

691-692 Senior Thesis 2-3 cr. per sem.

(A year's course must be taken to get credit.) Prereq: Consent of instructor.  

699 Directed Study 1-6 cr.

Prereq: Junior or senior standing and consent of instructor.  

701 Programming Languages and Compilers 3 cr.

Design and implementation of compilers for modern programming languages. Emphasis on tools for compiler construction. Prereq: CS 536.  

702 Compiler Construction 3 cr.

Techniques for the implementation of compilers for sophisticated programming languages. Prereq: CS 536; co-req: CS 701 or consent of instructor. (Infrequently offered.)  

703 Advanced Topics in Programming Languages and Compilers 3 cr.

Advanced topics in compiling and programming languages design. Advanced parsing techniques; automatic syntactic error correction; local and global code optimization; attribute grammars; programming language design issues (data and control abstractions, specification and verification of high level languages). Prereq: CS 701.  

704 Principles of Programming Languages 3 cr.

Introduction to principles of advanced programming languages and programming-language theory. Topics include: lambda-calculus, functional languages, polymorphic functions, type inference, structural induction, lazy evaluation, operational semantics, denotational semantics, and axiomatic semantics. Prereq: CS 536 or consent of instructor.  

709 Mathematical Techniques for Analysis of Algorithms 3 cr.

Techniques for quantitative analysis of algorithms. Charging arguments, amortization, probabilistic methods. Adversary and information lower bounds. Use of methods from combinatorics, complex analysis, and asymptotics in obtaining precise analyses of quicksort, chained hashing, and other algorithms. Prereq: CS 577, knowledge of complex variables at the level of Math 321. (Infrequently offered.)  

712 Finite Difference Methods 3 cr.

Development of finite difference methods for initial and boundary value problems for hyperbolic, parabolic, and elliptic partial differential equations. Analysis of accuracy and stability of difference schemes. Direct and iterative methods for solving elliptic difference schemes. Applications from science and engineering. Prereq: CS 302, 412, Math 419 or equivalent, or consent of instructor.  

713 Numerical Analysis of Differential Equations 3 cr.

Analysis of numerical methods for ordinary differential equations. Single step and multistep methods. Stiff equations. Introduction to Galerkin methods; collocation, least squares, etc. Analysis of methods for the solution of large sparse systems of boundary value problems. Prereq: Graduate standing and consent of instructor.   

717(-718) Numerical Functional Analysis 3 cr. per sem. (also Math)

Fundamentals of normed spaces and linear operators; analysis of nonlinear operators; existence of, and iterative methods for, solutions of linear and nonlinear operator equations, error estimation; variational theory and minimization problems; monotonicity theory. Development of abstract tools and application of them to the general analysis of numerical methods for such problems as differential and integral equations. Prereq: CS 513, 514 and Math 223 or consent of instructor. (CS 718 is infrequently offered.)  

719 Network Flows 3 cr. (also IE)

Optimization problems and techniques for networks, including single and multi-commodity network flow, critical path, and facilities location problems. The theory of totally unimodular matrices and its relationship to network optimization. Prereq: CS 525 or consent of instructor.  

720 Integer Programming 3 cr. (also IE)

Formulation of integer programming problems and the characterization of optimization problems representable as integer and mixed-integer programs. The degree of difficulty of classes of integer programs and its relation to the structure of their feasible sets. Optimality conditions. Branch-and-bound, cutting plane, and decomposition methods for obtaining solutions or approximating solutions. Prereq: CS 525 or consent of instructor.  

723 Dynamic Programming and Associated Topics 3 cr. (also IE)

A generalized optimization model; discrete and continuous state spaces; deterministic and stochastic transition functions. Multistage decision processes. Functional equations and successive approximation in function and policy spaces. Relationship to linear programming and acyclic networks. Markovian decision processes. Solution methods and computational problems. Associated topics and applications such as calculus of variations; feedback control processes; and optimal trajectories, inventory and maintenance policies, and stopping rules. Prereq: CS 525 or IE 623; Math 521 or CS 726; Math 431 and computer programming, or consent of instructor. (Infrequently offered.)  

726 Nonlinear Programming Theory and Applications 3 cr. (also IE & Stat)

Separation theorems and other properties of convex sets in finite-dimensional spaces. Formulation of nonlinear programming problems. Saddle-point (Lagrangian) optimality criteria for convex nonlinear programs. Duality theorems for convex programs. First, and second-order Kuhn-Tucker stationary-point theory for differentiable non-convex programs. Perturbation and sensitivity analysis. Applications and extensions. Prereq: Familiarity with basic mathematical analysis (e.g., Math 521) and either Math. 443 or 320, or consent of instructor.  

727 Advanced Nonlinear Programming 3 cr. (also IE)

Conjugate convex functions and Fenchel-Rockafellar duality. Monotone operators and subdifferentials. Advanced methods for nonconvex problems, such as variational principles, generalized gradients, degree and index arguments, and multivalued ordinary differential equations. Applications to economics and operations research. Prereq: CS 726 or consent of instructor.  

730 Nonlinear Programming Algorithms 3 cr. (also IE)

Rigorous description, and convergence proofs of various nonlinear programming algorithms. Emphasis on algorithms that are important, can be proved to converge and are practical. Unification of classes of algorithms and convergence rates. Each student will code and test one of the algorithms described in the course. Prereq: Consent of instructor.  

731 Advanced Artificial Intelligence 3 cr.

Learning and hypothesis formation; knowledge acquisition; deductive and inductive inference systems; reasoning techniques involving time, nonmonotonic reasoning, spatial reasoning, truth maintenance systems; planning strategies. Prereq: CS 540. (Infrequently offered.)  

732 Topics in Artificial Intelligence 3 cr.

Advanced topics in artificial intelligence. A variable content course which may be repeated any number of times for credit. Prereq: Consent of instructor. (Infrequently offered.)  

733 Computational Methods for Large Sparse Systems
3 cr. (also Math & ECE)

Sparse matrices in engineering and science. Sparsity preservation. Numerical error control. Transversal algorithms, Tarjan's algorithm, Tinney's algorithms, minimum degree, banding, nested dissection, frontal methods. Linear and nonlinear equation solving. Compensation. Sparse vector methods. Iterative methods. ODE and PDE applications. Prereq: CS 367 and 412, or consent of instructor.  

736 Advanced Operating Systems 3 cr.

Advanced topics in operating systems, including process communication, resource allocation, multiprocess and network operating systems, kernel philosophies, fault-tolerant systems, virtual machines, high-level language systems, verifiability and proof techniques. Prereq: CS 537 or consent of instructor.  

737 Computer System Performance Evaluation and Modeling 3 cr.

Statistical techniques of computer system performance evaluation and measurement. System selection and tuning strategies. Deterministic and probabilistic models of process scheduling and resource allocation. Analytic and simulation models of computer systems. Systematic study of system architectures. Prereq: Math 222, CS 537 or 736, or consent of instructor.  

739 Distributed Systems 3 cr.

Basic concepts, distributed programming; distributed file systems; atomic actions; fault tolerance, transactions, program & data replication, recovery; distributed machine architectures; security and authentication; load balancing and process migration; distributed debugging; distributed performance measurement; distributed simulation techniques; distributed applications; correctness considerations and proof systems. Prereq: CS 736 or consent of instructor. (Infrequently offered.)  

740 Advanced Computer Networks 3 cr.

Advanced topics in computer communications networks: Congestion and flow control; Routing; Rate-based protocols; High-speed interfaces and technologies; Metropolitan area networks; Fast packet switching technologies; Advanced applications; Network services: name service, authentication, resource location. Prereq: CS 640.  

747 Advanced Computer Systems Analysis Techniques 3 cr.

Advanced analytical modeling techniques for performance analysis of computer systems, including discrete-parameter (embedded) Markov Chains, M/G/1 queues, stochastic Petri nets, queueing networks, renewal theory, and sample path analysis. Application areas include high performance computer architectures, databases, and operating system resource allocation policies. Prereq: CS 547 or consent of instructor.  

750 Real-Time Computing Systems 3cr. (also ECE)

Introduction to the unique issues in the design and analysis of computer systems for real-time applications. Hardware and software support for guaranteeing timeliness with and without failures. Resource management, time-constrained communication, scheduling and imprecise computations, real-time kernels and case studies. Prereq: CS 552 and 537 or consent of instructor.  

752 Advanced Computer Architecture 3 cr. (also ECE)

Advanced techniques of computer design. Parallel processing and pipelining; multiprocessors, multi-computers and networks; high performance machines and special purpose processors; data flow architecture. Prereq: ECE/CS 552 and CS 537.  

755 VLSI Systems Design 3 cr. (also ECE)

Overview of MOS devices and circuits; introduction to integrated circuit fabrication; topological design of data flow and control; interactive graphics layout; circuit simulation; system timing; organizational and architectural considerations; alternative implementation approaches; design project. Prereq: ECE 340, ECE/CS 352, and CS/ECE 552 or consent of instructor.  

756 Computer-Aided Design for VLSI 3 cr. (also ECE)

Broad introduction to computer-aided design tools for VLSI, emphasizing implementation algorithms and data structures. Topics covered: design styles, layout editors, symbolic compaction, module generators, placement and routing, automatic synthesis, design-rule checking, circuit extraction, simulation and verification. Prereq: CS 367, good programming skills, CS 352; CS 755 strongly recommended. (Infrequently offered.)  

757 Advanced Computer Architecture 3 cr. (also ECE)

Parallel algorithms, principles of parallelism detection and vectorizing compilers, interconnection networks, SIMD/MIMD machines, processor synchronization, data coherence, multis, dataflow machines, special purpose processors. Prereq: CS 752 or consent of instructor.  

760 Machine Learning 3 cr.

Computational approaches to learning: including inductive inference, explanation-based learning, analogical learning, connectionism, and formal models. What it means to learn. Algorithms for learning. Comparison and evaluation of learning algorithms. Cognitive modeling and relevant psychological results. Prereq: CS 540.  

761 Deduction and Problem Solving by Computer 3 cr.

Study and evaluation of programs that use automated deduction to solve problems. Variants of Prolog, such as constraint logic programming, parallel prologs, and deductive database systems. Resolution theorem provers. Verification systems, such as the Boyer-Moore prover. Prereq: CS 540.  

762 Deduction and Problem Solving by Computer 3 cr.

Critical study and evaluation of programs and of man-computer interactive systems that play games such as chess, bridge, and GO; solve problems and puzzles; and prove theorems in various mathematical domains. Different kinds of languages, including natural language, usable for problem formulation and for solution planning and testing. Prereq: CS 540 or consent of instructor. (Infrequently offered.)  

764 Topics in Database Management Systems 3 cr.

Implementation of database management systems, the impact of new technology on database management systems, back-end database computers, distributed database management systems, concurrency control and query execution in both distributed and centralized systems, implementation of multiple user views, roll-back and recovery mechanisms, database translation. Prereq: CS 564, 537, and 536 or consent of instructor.  

765 Perceptual Recognition 3 cr.

High-level perceptual processing by computer; recognition of complex objects and scenes; advanced computer vision systems; relation to the living visual system; algorithm-structured multi-computer architectures for perception; binocular and multi-modal vision; recognition and tracking of moving objects; learning in perceptual systems; perceptual-motor control of robots. Prereq: CS 731 or consent of instructor. (Infrequently offered.)  

766 Computer Vision 3 cr.

Fundamentals of image analysis and computer vision; image acquisition and geometry; image enhancement; recovery of physical scene characteristics; shape-from techniques; segmentation and perceptual organization; representation and description of two-dimensional and three-dimensional objects; shape analysis; texture analysis; goal-directed and model-based systems; parallel algorithms and special-purpose architectures. Prereq: CS 540.  

767 Graph Theory 3 cr.

Theory of graphs, including adjacency and incidence matrices, planarity, hamiltonian circuits, Euler's formula, directed graphs, and trees. The efficiency of the known algorithms for performing various operations on graphs. Prereq: CS 367 and either CS 475 or 577, or consent of instructor. (Infrequently offered.)  

771 Computational Linguistics 3 cr. (also Ling)

Tools, techniques and literature of computational linguistics with applications in artificial intelligence and cognitive science. Topics include syntactic and semantic parsing, natural language understanding, text generation, machine translation, and speech recognition and production. Prereq: CS 540 or 545 or Linguistics 530 or consent of instructor.   

773-774 Problems in Computational Linguistics 3 cr. per sem. (also Ling)

Current research in computational linguistics, coupled with original directed research. Prereq: CS 545 or 771 or consent of instructor. (Infrequently offered.)  

780 Robot Motion Planning 3 cr. (also ECE & ME)

A unified view on geometric, algorithmic, and computational issues of automatic motion planning of motion for mobile robots and arm manipulators in a complex environment. Planning with complete information - configuration space, connectivity graphs, computational complexity; with partial information - algorithm convergence, topological issues. Effect of system kinematics. Relation between sensing media and algorithm efficiency. Prereq: Math 340 or equivalent and consent of instructor.  

784 Data Models and Languages 3 cr.

Study of database programming languages. Topics include: Logic based languages, embedded query languages, object-oriented languages. There will be coverage of types, persistence, inheritance, object identity, data models, implementation issues, and case studies of actual systems and languages. Prereq: CS 564 and 536 or consent of instructor.  

787 Advanced Algorithms and Data Structures 3 cr.

Algorithms for graph manipulation, geometry, matrix multiplication, string processing, information retrieval, etc. Mathematical models and analyses. Lower bounds. Probabilistic, distributed, and parallel algorithms. Advanced data structures. Prereq: CS 577 or 509.  

790 Master's Thesis 1-9 cr.

For students writing a Master's thesis or project. Prereq: Master's candidate.  

799 Master's Research 1-9 cr.

For pre-Master's students doing research projects. Prereq: Master's candidate.  

810 Models and Formalisms for Computation 3 cr.

Models of computation, Turing machines, recursive functions, Church's thesis, undecidable problems, degrees of unsolvability. Denotational semantics, logic of programs. Applications to automata, formal languages, program verification, programming languages, and complexity. Prereq: CS 520.  

812 Arithmetic Algorithms 3 cr.

Design, implementation, and analysis of algorithms for exact arithmetic on arbitrarily large integers, Gaussian integers and rational numbers. Algorithms for modular arithmetic and internal arithmetic. Algorithms for integer greatest common divisor calculation and factorization. Classical and modern algorithms. Prereq: Math 541 and CS 367, or consent of instructor. (Infrequently offered.)   

813-814 Algebraic Algorithms 3 cr. per sem. (also Math)

Algorithms for arithmetic operations on multivariate polynomials with integral, rational and finite field coefficients. Polynomials remainder sequences and subresultants. Algorithms for multivariate polynomial resultant and greatest common divisor calculation. Arithmetic operations on multivariate rational functions. Algorithms for exact linear algebra of systems with polynomial coefficients. Exact calculation of the real and complex zeros of polynomials. Algorithms for factorization of polynomials into irreducibles. Calculations with real algebraic numbers. Quantifier elimination for real closed fields. Operations on formal power series. Prereq: CS 812 and Math 541-542, or consent of instructor. (Infrequently offered.)  

815 Transcendental Function Algorithms 3 cr. (also Math)

Formalism for function class representations; canonical and normal forms; diophantine sets and relation to recursively enumerable sets; Richardson's theorem; Lindemann theorems; canonical and normal form algorithms; fundamental operations on polynomials and rational functions with Gaussian integer coefficients; fundamental operations on various subclasses of the elementary transcendental functions; indefinite integration of rational functions; differential fields; Liouville integration theory; Risch integration algorithm. Prereq: CS 814 or consent of instructor. (Infrequently offered.)  

820 Theory of Automata and Formal Languages 3 cr.

Advanced treatment of results concerning finite automata, regular sets, context-free and context-sensitive languages, Turing machines. Extensions of the models to multi-head, multi-tape, and probabilistic machines. Comparison of models. Applications to programming language design. Prereq: CS 520.  

830 Abstract and Concrete Complexity Theory 3 cr.

Study of computation with limited resources (time, space, etc.). Complexity hierarchies, structure of P, NP, PSPACE, co-NP. Strong NP-completeness, isomorphism completeness, relativized complexity. Abstract complexity, probabilistic complexity. Lower bounds, time-space tradeoffs, pebbling, alternation. Prereq: CS 520. (Infrequently offered.)  

837 Topics in Numerical Analysis 3 cr. (also Math)

Topic selected from advanced areas. A variable content course which may be repeated any number of times for credit. Prereq: Consent of instructor. (Infrequently offered.)  

838 Topics in Computing 3 cr.

Topics selected from advanced areas. A variable content course which may be repeated any number of times for credit. Prereq: Consent of instructor. (Infrequently offered.)  

880 Topics in Theoretical Computer Science 3 cr.

Advanced topics in algorithms, complexity, and models of computation, discussed in a seminar format. The exact topic varies. Prereq: consent of instructor. (Infrequently offered.)   

881-882 Numerical Methods for Ordinary Differential Equations
3 cr. per sem. (also Math)

Initial-value problems and boundary value problems for systems of nonlinear ordinary differential equations; convergence and stability of computational procedures; some topics chosen from the design of general computer programs, variational problems. Prereq: CS 514 and Math 417, or consent of instructor. (Infrequently offered.)   

883-884 Numerical Methods for Partial Differential Equations
3 cr. per sem. (also Math)

Initial-value problems for systems of partial differential equations; boundary value problems, stability and convergence; iterative methods; applications to the classical problems of mathematical physics. Prereq: CS 712 and 717, or consent of instructor. (Infrequently offered.)  

885 Matrix Theory in Numerical Analysis 3 cr. (also Math)

Methods for determining exclusion and inclusion regions for the eigenvalues of an NxN matrix. Variational methods for eigenvalues. The QR and LR algorithms. The Perron-Frobenius theory of positive matrices. Error analysis of numerical methods for computations in linear algebra. Prereq: CS 717 or consent of instructor. (Infrequently offered.)  

887 Approximation Theory 3 cr. (also Math)

Interpolation and approximation by means of interpolation; uniform approximation; best approximation; approximation in normed linear spaces; spline functions; orthogonal polynomials; degree of approximation; computational procedures. Prereq: Consent of instructor.  

899 Pre-Dissertator Research 1-9 cr.

Prereq: Post-Master's, pre-dissertator status.  

990 Dissertation 1-6 cr.

Prereq: Dissertator status.  

999 Independent Study and Research 1-6 cr.

Prereq: Dissertator status.

Non-Credit Seminars

The nine research areas in the Department each run an advanced, non-credit seminar where graduate students, visitors, and faculty members from within and outside the Department present their latest research or discuss recently published papers. These seminars give graduate students the opportunity to learn about current research problems and to get valuable feedback on their own research.

Also, each fall the Department runs a Distinguished Lecturer Series where 6-8 leading researchers in a subfield of computer science visit. The visitors give two lectures - one to a general computer science audience and a second, more specialized, talk targeted toward researchers in the given subfield. Recent topics have been programming languages, computing theory, operating systems, and machine learning.



This page was automatically created. Send comments to ferris@cs.wisc.edu