Graduate Bulletin
|
|
1996-1997
|
Computer Science
In the College of Sciences
Office: Business Administration and Math. 203
Telephone: (619) 594-6191
John D. Elwin, Ph.D., Professor of Mathematical Sciences, Chair of Department
Kasi Anantha, Ph.D., Professor of Mathematical Sciences
Sara Baase, Ph.D., Professor of Mathematical Sciences
Leland L. Beck, Ph.D., Professor of Mathematical Sciences
John L. Carroll, Ph.D., Professor of Mathematical Sciences
John D. Donald, Ph.D., Professor of Mathematical Sciences
Nenad Marovac, Ph.D., Professor of Mathematical Sciences
Roman W. Swiniarski, Ph.D., Professor of Mathematical Sciences
Mahmoud Tarokh, Ph.D., Professor of Mathematical Sciences
Marko I. Vuskovic, Ph.D., Professor of Mathematical Sciences
Carl F. Eckberg, Ph.D., Associate Professor of Mathematical Sciences (M.S. Computer Science Graduate Adviser)
Kris Stewart, Ph.D., Associate Professor of Mathematical Sciences
Vernor S. Vinge, Ph.D., Associate Professor of Mathematical Sciences
Roger E. Whitney, Ph.D., Associate Professor of Mathematical Sciences
Graduate teaching associateships in computer science are available to a limited number of qualified students. Application blanks and additional information may be secured from the chair of the Department of Mathematical Sciences.
The Department of Mathematical Sciences, in the College of Sciences, offers graduate study leading to the Master of Science degree in computer science. The areas in which courses are offered include software, systems, architecture, artificial intelligence, and computer science theory.
Master's level research projects are available in the following areas of computer science: distributed systems, multiprocessing, operating systems, graphics, neural networks, formal languages, numerical methods, robotics, signal processing, and computational complexity. Specialized laboratories exist for microprocessor architecture, graphics, and robotics and intelligent machines.
All students must satisfy the general requirements for admission to the University with classified graduate standing, as described in Part Two of this bulletin.
All students must satisfy the general requirements for advancement to candidacy as described in Part Two of this bulletin. In addition, the student must have passed a qualifying examination in their area.
In addition to meeting the requirements for classified graduate standing and the basic requirements for the master's degree as described in Part Two of this bulletin, the student must meet the following departmental requirements:
- 1. Complete a minimum of 30 units of 500-, 600-, and 700-level courses selected with the approval of the adviser. All programs must include at least 24 units chosen from computer science and mathematics. Programs must also satisfy the following requirements:
- a. At least 15 units of graduate (600-700) courses (excluding
797, 798, 799A).
- b. At least one course from each of the following:
Programming and Formal Languages: Computer Science
520, 524, 532, 535, 620A, 620B, 624, 632.
Operating Systems and Architecture: Computer Science
572, 574, 576, 670, 672, 674.
Algorithms and Complexity: Computer Science 562, 564,
660, 662, 664.
Applications and Other Topics: Computer Science 514,
550, 551, 552, 553, 555, 556, 557, 558, 559, 561, 566,
650, 651, 656, 700; Mathematics 542, 693A, 693B.
- 2. With departmental approval, students may select Plan A (thesis), and must complete 799A in accordance with departmental and University regulations. An oral examination on the subject of the thesis is required. Students selecting Plan B must pass written comprehensive examinations as determined by the department.
514. Database Theory and Implementation (3)
Prerequisites: Computer Science 310 and Mathematics 245.
Database systems architecture. Storage structures and access techniques. Relational model, relational algebra and calculus, normalization of relations, hierarchical and network models. Current database systems.
520. Advanced Programming Languages (3)
Prerequisites: Computer Science 237, 310, and 320.
Object oriented programming, concurrent programming, logic programming. Implementation issues.
524. Compiler Construction (3)
Prerequisites: Computer Science 237, 310, and 320.
Syntactical specification of languages. Scanners and parsers. Precedence grammars. Run-time storage organization. Code generation and optimization.
530. Systems Programming (3) I, II
Prerequisites: Computer Science 237 and 310.
Design and implementation of systems software. Relationship between software design and machine architecture. Topics from assemblers, loaders and linkers, macro processors, compilers, debuggers, editors. Introduction to software engineering. Large project required. Not acceptable for the M.S. degree in computer science.
532. Software Engineering (3)
Prerequisites: Computer Science 310 and 320.
Theory and methodology of programming complex computer software. Analysis, design, and implementation of programs. Team projects required.
535. Object-Oriented Programming and Design (3)
Prerequisites: Computer Science 310 and 320.
Basic concepts of object-oriented programming; classes, objects, messages, data abstraction, inheritance, encapsulation. Object-oriented design methodology.
550. Artificial Intelligence (3)
Prerequisites: Computer Science 108 and either Mathematics 245
or 523.
Heuristic approaches to problem solving. Systematic methods of search of the problem state space. Theorem proving by machine. Resolution principle and its applications.
551. User Interface Environments (3)
Prerequisites: Computer Science 310 and 320.
Design of user-machine interfaces in interactive systems. Problems faced by user of an interactive system; basic issues and principles involved in design and implementation of good and friendly user-machine graphical interfaces.
552. Advanced Artificial Intelligence (3)
Prerequisites: Computer Science 310, 320, and 550.
Presentation of logic based programming languages and their usefulness in artificial intelligence, including areas such as expert systems and natural language translation. Implementation and use of chaining, recursion, lists. Substantial programming practice.
553. Neural Networks (3)
Prerequisites: Computer Science 320 and Mathematics 254.
Principles of neural networks, their theory and applications.
555. Raster Computer Graphics (3)
Prerequisite: Computer Science 551.
Bit map graphics, algorithms to connect between different formats and enhancement of pictures.
556. Robotics: Mathematics, Programming, and Control (3)
Prerequisites: Computer Science 320, Mathematics 254, knowledge of the C programming language.
Robotic systems including manipulators, actuators, sensors, and controllers. Algebraic methods for spatial description of solid objects, manipulator kinematics and control. Robot programming languages and robot programming systems.
557. Computer Control Systems (3)
Prerequisites: Computer Science 310 and Mathematics 254.
Analysis and programming of real-time computer control systems, implementation of digital controllers including programming, intelligent control systems and fuzzy control.
558. Computer Simulation (3)
Prerequisites: Computer Science 310 and Mathematics 550.
Methodology of simulation for discrete and continuous dynamic systems. State-of-the-art programming techniques and languages. Statistical aspects of simulation. Students will design, program, execute, and document a simulation of their choice.
559. Computer Vision (3)
Prerequisites: Computer Science 310 and Mathematics 254.
Algorithms and computer methods for processing of images. Visual perception as a computational problem, image formation, characterization of images, feature extraction, regional and edge detection, computer architectures for machine vision.
560. Algorithms and Their Analysis (3) I, II
Prerequisites: Computer Science 310 and Mathematics 245.
Algorithms for solving frequently occurring problems. Analysis techniques, lower bounds. Sorting, merging, graph problems (shortest paths, depth-first and breadth-first search), and others. NP-complete problems. Not acceptable for the M.S. degree in Computer Science.
561. Multimedia Systems (3)
Prerequisite: Computer Science 551.
System aspects of multimedia authoring, browsing, and database subsystem; digital representation for different media; audio and video; operating system support for continuous media applications; architectures; design and implementation of multimedia support systems; use of multimedia technology in software engineering.
562. Automata Theory (3)
Prerequisite: Mathematics 245 or 521A.
Definition of finite automata. Classification of finite automaton definable languages. Minimization of finite automata. Nondeterministic finite automata. Sequential machines with output. Regular sets and expressions. Introduction to grammars.
564. Introduction to Computability (3)
Prerequisite: Mathematics 245 or 523.
Definition of algorithm by abstract (Turing) machines. Universal Turing machines. Primitive recursive and recursive functions. The equivalence of the computational power of Turing machines and recursive functions. Limitations and capabilities of computing machines; the halting problem.
566. Queuing Theory (3)
Prerequisites: Computer Science 108 and Mathematics 550.
Performance prediction of computer networks and other systems (e.g., inventory control, customer service lines) via queuing theory techniques. Operational analysis.
570. Operating Systems (3) I, II
Prerequisites: Computer Science 310, 370, and knowledge of the
C programming language.
File systems, processes, CPU scheduling, concurrent programming, memory management, protection. Relationship between the operating system and underlying architecture.
572. Microprocessor Architecture (3)
Prerequisites: Computer Science 370 and knowledge of the C programming language.
Architecture of state-of-the-art microprocessor. Internal pipeline, internal cache, external cache, and memory management. Programming a uniprocessor. Communication among computers in a distributed environment. Architecture and programming of a multiprocessor system.
574. Computer Security (3)
Prerequisites: Computer Science 310; Mathematics 245, 550; and
credit or concurrent registration in Computer Science 570.
Principles of computer security and application of principles to operating systems, database systems, and computer networks. Topics include encryption techniques, access controls, and information flow controls.
575. Supercomputing for the Sciences (3)
Prerequisite: Extensive programming background in Fortran or C.
Interdisciplinary course, intended for all science and engineering majors. Advanced computing techniques developed for supercomputers. Overview of architecture, software tools, scientific computing and communications. Hands-on experience with CRAY.
576. Computer Networks and Distributed Systems (3)
Prerequisite: Credit or concurrent registration in Computer Science 570.
Local area networks and wide area networks; mechanisms for interprocess communication; rules for distribution of data and program functions.
596. Advanced Topics in Computer Science (1-4) I, II
Prerequisite: Consent of instructor.
Selected topics in computer science. May be repeated with the approval of the instructor. See Class Schedule for specific content. Limit of nine units of any combination of 296, 496, 596 courses applicable to a bachelor's degree. Maximum credit of six units of 596 applicable to a bachelor's degree. Maximum combined credit of six units of 596 and 696 applicable to a 30-unit master's degree.
For additional courses useful to computer scientists, see:
Mathematics 541. Introduction to Numerical Analysis
and Computing
Mathematics 542. Introduction to Numerical Solutions of
Differential Equations
Mathematics 561. Applied Graph Theory
Mathematics 579. Combinatorics
620A. Formal Languages and Syntactic Analysis I (3)
Prerequisites: Computer Science 310, 320 or 520, and 562.
Regular, context-free, context-sensitive, and general grammars. Corresponding machine model recognizers. Chomsky and Greibach normal forms. Closure, decidability and undecidability properties.
620B. Formal Languages and Syntactic Analysis II (3)
Prerequisite: Computer Science 620A.
Properties of deterministic context-free languages. Backtrack and matrix based general parsing techniques. LL(k) and LR(k) based parser generators. Precedence grammars.
624. Advanced Compiler Construction (3)
Prerequisite: Computer Science 524.
LR parsing. Attribute grammars and multipass translation. Intermediate representations. Global optimization. Global data flow analysis. Table compaction techniques. Syntactic error recovery and repair.
632. Advanced Software Engineering (3)
Prerequisite: Computer Science 532.
Theoretical and practical concepts associated with the specification, design, testing, and maintenance of large software systems. Use of automated tools in engineering such systems.
650. Seminar in Artificial Intelligence (3)
Prerequisite: Computer Science 550.
General problem-solving programs, expert problem solving, game-playing programs, pattern recognition and natural language processing. Understanding vision, manipulation, computer decision. May be repeated with new content with approval of graduate adviser. Maximum credit six units applicable to a master's degree.
651. Advanced Multimedia Systems (3)
Prerequisite: Computer Science 561.
System aspects of multimedia authoring, browsing, and database subsystems. Formal models for hypermedia documents. Conversion of flat text into hypertext. Artificial intelligence in hypermedia systems. Architectures, design, and implementation of multimedia support systems. Use of multimedia technology in software engineering.
656. Advanced Robotics (3)
Prerequisite: Computer Science 556.
Computer-based techniques for low-, medium-, and high-level robot control including sequential and parallel schemes for robot dynamics, robot programming and robot task planning.
660. Combinatorial Algorithms and Data Structures (3)
Prerequisite: Computer Science 560.
Algorithm design techniques. Network flow and matching. Complexity analysis. NP-completeness, reductions among NP-complete problems. Approximation algorithms for NP-complete problems such as the traveling salesman problem.
662. Theory of Parallel Algorithms (3)
Prerequisites: Computer Science 560 and Mathematics 254.
Models for parallel computation. Parallel algorithms for several common problems including sorting, searching, graph problems, and matrix problems. Complexity of parallel algorithms. Lower bounds on parallel complexity.
664. Theory of Computability (3)
Prerequisite: Computer Science 562 or 564.
Turing machines and other formal models of computation. Recursive function theory. The Ackermann function. Solvable and unsolvable problems.
670. Advanced Operating Systems (3)
Prerequisite: Computer Science 570.
Survey of advanced operating systems including distributed systems. Associated design issues. Case studies.
672. Microcomputer Software (3)
Prerequisite: Computer Science 572.
Design and implementation of a real time operating system for a state-of-the-art microprocessor. Applications of the operating system.
674. Advanced Computer Architecture (3)
Prerequisite: Computer Science 572.
Advanced computer architecture, including parallel and distributed architecture, and accompanying software and algorithmic issues.
696. Selected Topics in Computer Science (3)
Prerequisite: Consent of instructor.
Intensive study in specific areas of computer science. May be repeated with new content. See Class Schedule for specific content. Maximum combined credit of six units of 596 and 696 applicable to a 30-unit master's degree.
700. Applications of Computer Science (3)
Prerequisite: Classified graduate standing in mathematics or computer science.
Topic to be chosen from such applications as theorem proving, simulation, learning theory, graphics definition languages. May be repeated with new content. See Class Schedule for specific content. Maximum credit six units applicable to a master's degree.
797. Research (1-3) Cr/NC/SP
Prerequisite: Six units of graduate level computer science courses.
Research in computer science. Maximum credit six units applicable to a master's degree.
798. Special Study (1-3) Cr/NC/SP
Prerequisite: Consent of staff; to be arranged with department
chair and instructor.
Individual study. Maximum credit six units applicable to a master's degree.
799A. Thesis or Project (3) Cr/NC/SP
Prerequisites: An officially appointed thesis committee and
advancement to candidacy.
Preparation of a project or thesis for the master's degree.
799B. Thesis or Project Extension (0) Cr/NC
Prerequisite: Prior registration in Thesis or Project 799A with an
assigned grade symbol of SP.
Registration required in any semester or term following assignment of SP in Course 799A in which the student expects to use the facilities and resources of the university; also student must be registered in the course when the completed thesis or project is granted final approval.
For additional courses useful to computer scientists, see:
Mathematics 693A-693B, Advanced Numerical Analysis
