Infgr08z doc (rev) 23 Oct 1992 erik jonsson school of engineering and computer science graduate program in computer science (M. S., Ph. D.) Faculty professors: Dung T. Huynh, William J. Pervin, Ivan H



Download 25.09 Kb.
Date28.05.2018
Size25.09 Kb.
#51385
infgr08z.doc (rev) 23 Oct 1992 ERIK JONSSON SCHOOL OF ENGINEERING AND COMPUTER SCIENCE GRADUATE PROGRAM IN COMPUTER SCIENCE (M.S., Ph.D.) FACULTY PROFESSORS: Dung T. Huynh, William J. Pervin, Ivan H. Sudborough, Klaus Truemper ASSOCIATE PROFESSORS: Galigekere R. Dattatreya, Eliezer Dekel, Simeon C. Ntafos, Ivor P. Page, Ioannis G. Tollis ASSISTANT PROFESSORS: R. Ramesh, Haim Schweitzer, Subbarayan Venkatesan OBJECTIVE The objective of the Graduate Program in Computer Science is to offer intensive preparation in the design, programming, theory, and applications of computers. Training is provided for both academically oriented students and students with professional goals in the many business, industrial or governmental occupations requiring advanced knowledge of computer theory and technology. Courses and research are offered in a variety of subfields of computer science, including operating systems, computer architecture, computer graphics, pattern recognition, automata theory, combinatorics, artificial intelligence, database design, computer networks, programming languages, software systems, analysis of algorithms, computational complexity, parallel processing, VLSI, computational geometry, and design automation. A comprehensive program of evening courses is offered which enables part-time students to earn the Master's degree or to select individual courses of interest. FACILITIES The university maintains a modern, large computer facility (IBM 4381), a Convex C-3 Vector Computer with a wide range of peripheral equipment. All these computers are connected by a local area network. A direct high throughput link to the University of Texas Center for High Performance Computing is also available. In addition, the Computer Science program has an N-Cube parallel processing machine with 64 processors for its own research use. The Computer Science Program is connected to the CSNet. All major computers on campus are linked by an Ethernet network. In addition to the faculty of the program, there are individuals who are involved in computer related work in many other areas of the university, including the several physical and social sciences and in various areas of business and management. Students majoring in computer science with interest in these important application areas have the opportunity to consult and work with talented faculty from a wide range of disciplines. SPECIFIC DEGREE REQUIREMENTS For general degree requirements, see the section on General Academic Regulations. Students lacking undergraduate prerequisites for graduate courses in their chosen area must complete these prerequisites or receive approval from their graduate adviser and the course instructor. At the discretion of the graduate adviser a diagnostic exam may be required. Specific degree requirements follow. MASTER OF SCIENCE The student entering the M.S. program should have an undergraduate preparation equivalent to a baccalaureate in a quantitative science, including calculus and linear algebra. However, special arrangements (requiring more than the minimal number of hours) can be made for students with good undergraduate preparation in other fields. The student may choose a thesis plan or a non-thesis plan. The thesis plan requires 27 hours of courses, plus completion of an approved thesis (six thesis hours). This thesis is directed by a supervising professor and must be approved by the head of the Computer Science program. The non-thesis plan requires 36 hours of courses. However, for students with good undergraduate preparation in Computer Science, three of these hours may be waived by the head of the program with the written concurrence of the Dean of Graduate Studies and Research. Two tracks of studies are available. TRACK A ENTRANCE REQUIREMENTS Bachelor's degree which includes calculus through multivariable calculus and linear algebra. GPA of at least 3.0 (last 60 hours). GPA in quantitative courses of at least 3.3. GRE of at least 1100 (verbal + quantitative). GRADUATION REQUIREMENTS Prerequisites: (taken if necessary) CS 5303 Computer Science I CS 5330 Computer Science II CS 5333 Discrete Structures CS 5334 Introduction to Systems Programming CS 5341 Survey of Computer Architecture (plus 5142 Lab) CS 5343 Data Structures & Algorithms CS 5349 Automata Theory CORE REQUIREMENTS Benchmark Courses CS 6349 Digital Logic Design CS 6353 Compiler Construction CS 6363 Design & Analysis of Computer Algorithms CS 6371 Structure & Design of Programming Languages CS 6378 Operating Systems Students must satisfy the benchmark requirements by either earning a 3.2 minimum grade point average in the courses listed OR by earning a 3.0 minimum grade point average in the courses listed plus a 6000/7000/8000 level approved elective taken beyond the graduation requirements. Five 6000/7000/8000 level elective CS courses with approval of a Graduate Adviser. A minimum grade point average of 3.0 is required. Approved electives to make a total of 36 credits. TRACK B ENTRANCE REQUIREMENTS B.S. Degree with calculus through multivariate calculus, differential equations and a GPA of 3.0 on a scale of 4.0, with 3.3 in quantitative subjects. GRE of 1100. Two course college physics sequence. College statistics. Linear Algebra. GRADUATION REQUIREMENTS Prerequisites: (taken if necessary) CS 5303 Computer Science I CS 5330 Computer Science II CS 5333 Discrete Structures CS 5334 Systems Programming CS 5341 Survey of Computer Architecture, plus 5142 Lab CS 5343 Data Structures & Algorithms EE 5301 Circuit Analysis EE 5302 Systems Theory EE 5311 Active Circuits CORE REQUIREMENTS Benchmark Courses CS 6349 Digital Logic Design CS 6354 Software Engineering CS 6352 Performance of Computer Systems CS 6351 Computer Systems Design EE 6325 VLSI Design or CS6358 Students must satisfy the benchmark requirements by either earning a 3.2 minimum grade point average in the courses listed OR by earning a 3.0 minimum grade point average in the courses listed plus a 6000/7000/8000 approved elective taken beyond the graduation requirements. Three of the following courses with a grade point average of 3.0 or better. CS 6360 Database Design CS 6366 Computer Graphics CS 6390 Computer Networks CS 7374 Advanced Computer Architecture CS 7368 VLSI Algorithms CS 6367 Software Validation Approved electives to make a total of 36 credits including at least two additional 6000/7000/8000 level courses. All electives must be approved by a graduate adviser. Substitutions for required courses may sometimes be made if approved by a graduate adviser and program head. Instructors may waive stated prerequisites for students with equivalent experience. DOCTOR OF PHILOSOPHY Each degree program is tailored to the student. The student must arrange a course program with the guidance and approval of a faculty member chosen as his/her graduate adviser. Adjustments can be made as the student's interests develop and a specific dissertation topic is chosen. ENTRANCE REQUIREMENTS A student may be admitted under 2 possible options. The student must have: A Master's degree in computer science or its equivalent, and A GPA of at least 3.5 and GRE of at least 1100; or A B.S. in related area with GPA of at least 3.5 in the last 60 hours, and A GRE of at least 1300. GRADUATION REQUIREMENTS Benchmark courses: same as Master's Pass a qualifying examination on the benchmark courses and their prerequisites. Pass, with a grade of B or better, courses chosen as follows: 1) Either CS 6369 Complexity of Combinatorial Algorithms; or CS 6381 Combinatorics and Graph Algorithms 2) CS 6382 Theory of Computation 3) Four 6000/7000 level courses 4) Two 8000 level courses Sufficient CS electives for a total of 90 credits. Dissertation. A dissertation is required and must be approved by the graduate program. A student must arrange for a dissertation adviser willing to guide this dissertation. The student must have a dissertation supervising committee that consists of no less than four members of which at least three must be from the Computer Science faculty. The dissertation may be in computer science exclusively or it may involve considerable work in an area of application. COMPUTER SCIENCE COURSE DESCRIPTIONS CS 5107 PROGRAMMING: FORTRAN (1 semester hour) Programming in FORTRAN. Based primarily on self-study materials. No credit allowed to Computer Science majors. Prerequisite: higher level computer programming language.(1-0) CS 5108 PROGRAMMING: APL (1 semester hour) Programming in APL. Based primarily on self-study materials. No credit allowed to Computer Science majors. Prerequisite: higher level computer programming language. (1-0) CS 5109-5609 SPECIAL TOPICS/TAGER (1-6 semester hours) Prerequisite: higher level computer programming language. ([1-6]-0) CS 5111 PROGRAMMING: PASCAL (1 semester hour) Theory and application programming in Pascal. Based primarily on self-study materials. No degree credit allowed for Computer Science majors. Prerequisite: higher level computer programming language. (1-0) CS 5112 PROGRAMMING: C (1 semester hour) Theory and application programming in C. Based primarily on self-study materials. No degree credit allowed for Computer Science majors. Prerequisite: higher level computer programming language. (1-0) CS 5118 PROGRAMMING: PL/I (1 semester hour) Programming in PL/I. Based primarily on self-study materials. No degree credit allowed to Computer Science majors. Prerequisite: higher level computer programming language. (1-0) CS 5122 PROGRAMMING: LISP (1 semester hour) Programming in LISP. Based primarily on self-study materials. No degree credit allowed for Computer Science majors. Prerequisite: higher level computer programming language. (1-0) CS 5123 PROGRAMMING: ADA (1 semester hour) Programming in Ada. Based primarily on self-study materials. Prerequisite: higher level computer programming language. No credit degree allowed for Computer Science majors. (1-0) CS 5124 PROGRAMMING: PROLOG (1 semester hour) Programming in PROLOG. Based primarily on self-study materials. Prerequisite: higher level computer programming. No degree credit allowed for Computer Science majors. (1-0) CS 5303 COMPUTER SCIENCE I (3 semester hours) Computer science problem-solving. The structure and nature of algorithms and their corresponding computer program implementation. Programming in a high level block-structured language (e.g., PASCAL, Ada, C++, or MODULA-2). Elementary data structures: arrays, records, linked lists, trees, stacks and queues. (3-0) CS 5330 COMPUTER SCIENCE II (3 semester hours) Logical basis of computer organization: machine representation of numbers and characters, flow of control, instruction codes, arithmetic and logical operations, indexing and indirect addressing, input/output interrupts, subprograms, linkages, macros, assembly systems, and machine language implementation of data structures. Corequisite: CS 5303. (3-0) CS 5333 DISCRETE STRUCTURES (3 semester hours) Mathematical foundations of computer science. Logic, sets, relations, graphs and algebraic structures. Combinatorics and metrics for performance evaluation of algorithms. (3-0) CS 5334 INTRODUCTION TO SYSTEMS PROGRAMMING (3 semester hours) Basic computer programming systems: loaders, assemblers, interpreters, compilers and simple monitors. File organization: peripheral device characteristics, input/output structures, sequential and random access files, physical and logical file organization. Prerequisite: CS 5330. (3-0) CS 5341 SURVEY OF COMPUTER ARCHITECTURE (3 semester hours) Basic digital circuits. Machine arithmetic. Register transfer level computer architecture. Hardware stack organization. Interrupt handling hardware. Design of control unit and input/output interface. Corequisite: CS 5142 or equivalent. Prerequisite: CS 5330 or knowledge of an assembly language. (3-0) CS 5142 COMPUTER ARCHITECTURE LABORATORY (1 semester hour) Laboratory for projects and experiments in CS 5341. May be repeated for credit with permission of graduate adviser. (0-3) CS 5343 DATA STRUCTURES & ALGORITHMS (3 semester hours) Formal specifications and representation of lists, arrays, trees, graphs, multilinked structures, strings and recursive pattern structures. Analysis of associated algorithms. Sorting and searching, file structures. Relational data models. Prerequisites: CS 5303, CS 5333. (3-0) CS 5349 AUTOMATA THEORY (3 semester hours) Deterministic and nondeterministic finite automata; regular expressions, regular sets, context-free grammars, pushdown automata, context free languages. Turing machines as acceptor, computer, and enumerator. Church's hypothesis, Universal Turing machines and the halting problem. Undecidability of Post's correspondence problem. Prerequisite: CS 5333. (3-0) CS 5181-5981 SPECIAL TOPICS IN COMPUTER SCIENCE (1-9 semester hours) Selected topics in Computer Science. (May be repeated to a maximum of 9 credit hours.) ([1-9]-0) CS 6349 DIGITAL LOGIC DESIGN (3 semester hours) Advanced mathematical concepts useful in digital logic design. Algorithmic minimization of switching functions. Hazards in combinational networks. Synthesis of switching functions from IC building blocks. Disjoint decomposition and multiple level synthesis. Analysis and design of synchronous and asynchronous sequential machines. Design of components of high speed arithmeticlogic units. Prerequisite: CS 5341. (3-0) CS 6351 COMPUTER SYSTEMS DESIGN (3 semester hours) Design of instruction sets, memory addressing modes, interleaved memory, cache memory design. Instruction pipelines, techniques for removing dependency delays. Computer bus systems and interfaces for various input/output device types. Pipelined and parallel functional units and their associated code generation algorithms. RISC architectures, support of high level languages, data flow machines, functional languages, lazy evaluation and graph reduction machines. Prerequisite: CS 6349.(3-0) CS 6352 PERFORMANCE OF COMPUTER SYSTEMS (3 semester hours) Theory of random variables and their functions. Classification of stochastic processes. Discrete parameter Markov chains and M/G/1 and M/M/m queues. Networks of queues. Statistical inference and simulation. Prerequisite: a first course on probability theory. (3-0) CS 6353 COMPILER CONSTRUCTION (3 semester hours) Lexical analyzers, context-free grammars. Top-down and bottom-up parsing; shift reduce and LR parsing. Operator- precedence, recursive-descent, predictive, and LL parsing. LR(k), LL(k) and precedence grammars will be covered. Prerequisites: CS 5343 and CS 5349. (3-0) CS 6354 SOFTWARE ENGINEERING (3 semester hours) The software life cycle. Requirement specification, program design methodologies, structured programming, software validation methods, quality assurance, software project management and control. Prerequisites: CS 5330 and CS 5333. (3-0) CS 6358 DESIGN OF INTEGRATED CIRCUITS (3 semester hours) Fabrication and cost analysis. Design of logic masks. Comparison of logic families. Computation using integrated circuits: addition, multiplication, square root, etc. Memories, PLAs and gate arrays. Computer-Aided Design: placement, routing, layer assignment. Full-custom and semi-custom design approaches. Comparison of different implementation approaches from the viewpoints of economy, performance and design time. Prerequisites: CS 5341, CS 5343. (3-0) CS 6360 DATABASE DESIGN (3 semester hours) Methods, principles and concepts that are relevant to the practice of database software design. Topics such as file-system organization, database structure, schemas, database implementation, information retrieval and protection. Prerequisite: CS 5343. (3-0) CS 6363 DESIGN AND ANALYSIS OF COMPUTER ALGORITHMS (3 semester hours) The study of efficient algorithms for various computational problems. Sorting, manipulation of data structures, graphs, matrix multiplication, the Fast Fourier Transform, arithmetical operations and pattern matching. Complexity of algorithms, lower bounds, NP completeness. Prerequisites: CS 5343, CS 5349. (3-0) CS 6364 ARTIFICIAL INTELLIGENCE (3 semester hours) Design of machines that exhibit intelligence. Particular topics include: representation of knowledge, vision, natural language processing, search, logic and deduction, expert systems, planning, language comprehension, machine learning. Prerequisite: CS 5343. (3-0) CS 6365 EXPERT SYSTEMS (3 semester hours) Fundamentals of expert systems. Topics include knowledge acquisition and representation, metaknowledge, control of problemsolving systems, process explanation, plausible reasoning. Prerequisite: CS 6364. (3-0) CS 6366 COMPUTER GRAPHICS (3 semester hours) Geometric models of two- and three-dimensional objects and curved surfaces. Transformations in two and three dimensions. Clipping algorithms. Homogeneous coordinates. Hidden line and surface elimination algorithms: depth buffer, priority, polygon and others. Raster graphics systems. Scan line conversion algorithms, color and grey scale resolution and aliasing problems. Shading, rendering and special effects. Curved surface modeling. Bezier and B-spline functions. Review of current developments. Prerequisites: CS 5330, CS 5343, and linear algebra. (3-0) CS 6367 SOFTWARE VALIDATION, VERIFICATION, AND PERFORMANCE MEASUREMENT (3 semester hours) Program testing techniques. Formal and informal proofs of correctness. Reliability models and performance measurement techniques. Prerequisite: CS 6354 or consent of instructor. (3-0) CS 6369 COMPLEXITY OF COMBINATORIAL ALGORITHMS (3 semester hours) Topics include bounded reducibilities and completeness, approximation algorithms and heuristics for NP--hard problems, randomized algorithms, additional complexity classes. Prerequisite: CS 6363. (3-0) CS 6371 STRUCTURE AND DESIGN OF PROGRAMMING LANGUAGES (3 semester hours) Evolution of concepts in programming languages. Data and control abstraction. Run-time effects of binding, scope and extent; structure of ALGOL-like and interpretive languages. Data types, problem areas and implementation models. Control structures, exception handling, concurrency. Functional programming. Examples from representative languages. Prerequisite: CS 5343. (3-0) CS 6374 COMPUTATIONAL LOGIC (3 semester hours) Methods and algorithms for the solution of logic problems. Topics include problem formulation in first order logic and extensions, theorem proving algorithms, polynomially solvable cases, logic programming, applications. Prerequisites: CS 5343, and knowledge of "C". (3-0) CS 6375 ARTIFICIAL NEURAL NETS AND MACHINE LEARNING (3 semester hours) Algorithms for training perceptions and multi-layer neural nets: back propagation, Boltzman machines, selforganizing nets. The ID3 and the Nearest Neighbor algorithms. Formal models for analyzing learnability: exact identification in the limit and probably approximately correct (PAC) identification. Computational limitations of learning machines. Prerequisite: CS 5343. (3-0) CS 6376 PARALLEL PROCESSING (3 semester hours) Topics include parallel machine models, parallel algorithms for sorting, searching and matrix operations. Parallel graph algorithms. Selected topics in parallel processing. Prerequisite: CS 6363. (3-0) CS 6378 OPERATING SYSTEMS (3 semester hours) Multiprogramming, processes, concurrent operation. Synchronization and interprocess communication. Semaphores, monitors, messages. Processor scheduling. Memory protection, segmentation, virtual memory, paging, page replacement algo-rithms. Resource allocation, deadlock avoidance, detection, and recovery algorithms. Prerequisites: CS 5334, CS 5343. (3-0) CS 6381 COMBINATORICS AND GRAPH ALGORITHMS (3 semester hours) Fundamentals of combinatorics and graph theory. Combinatorial optimization, optimization algorithms for graphs (max flow, shortest routes, Euler tour, Hamiltonian tour). Prerequisites: CS 5343, CS 6363. (3-0) CS 6382 THEORY OF COMPUTATION (3 semester hours) Formal models of computation. Recursive function theory. Undecidability and incompleteness. Selected topics in theory of computation. Prerequisite: CS 5349. (3-0) CS 6384 IMAGE UNDERSTANDING IN COMPUTER VISION (3 semester hours) Algorithms for extracting information from digital pictures. Particular topics include: analysis of motion in time varying image sequences, recovering depth from a pair of stereo images, image separation, recovering shape from textured images and shadows, object matching techniques, model based recognition, the Hough transform. Prerequisite: CS 5343. (3-0) CS 6390 COMPUTER NETWORKS (3 semester hours) The design and analysis of computer networks. Topics include network architectures, the OSI reference model, theoretical basis for data communications, network protocols, local area networks, ISDN. Prerequisites: CS 5341, CS 6378. (3-0) CS 7350 SCHEDULING THEORY (3 semester hours) Deterministic scheduling theory, mainly in relation to computer operation. Topics include minimization of makespan and mean flow time, feasibility tests, and scheduling real-time tasks. Emphasis will be on complexity issues of various scheduling problems. Approximation algorithms with worstcase performance bounds. Prerequisite: CS 6363. (3-0) CS 7364 RECENT ADVANCES IN FOUNDATIONS OF COMPUTING (3 semester hours) Study of recent results in foundations of computing, mainly in theory of computation and computational complexity. (May be repeated for credit with the approval of a graduate adviser.) Prerequisite: consent of instructor. (3-0) CS 7368 RECENT ADVANCES IN VLSI (3 semester hours) Issues relating to the design, implementation and organization of VLSI systems. Properties of MOS devices and circuits. Implementation of basic functions, typical computer systems and highly concurrent machines. Languages for circuit specification. Automatic placement and routing algorithms. Area-time complexity bounds. (May be repeated for credit with the approval of a graduate adviser.) Prerequisite: CS 6363. (3-0) CS 7370 RECENT ADVANCES IN DISTRIBUTED COMPUTING (3 semester hours) Topics include distributed graph algorithms, election algorithms, synchronizers, mutual exclusion, resource allocation, deadlocks, Byzantine agreement and clock synchronization, knowledge and common knowledge, reliability in distributed networks, proving distributed programs correct. (May be repeated for credit with the approval of a graduate adviser.) Prerequisite: CS 6363. (3-0) CS 7374 COMPUTER ARITHMETIC (3 semester hours) Carry look ahead systems and carry save adders. Multipliers, multi-bit recording schemes, array multipliers, redundant binary schemes, residue numbers, slash numbers. High speed division and square root circuits. Multiprecision algorithms. The IEEE floating point standard, rounding processes, guard bits, error accumulation in arithmetic processes. Cordic algorithms. Prerequisite: CS 6349. (3-0) CS 7376 RECENT ADVANCES IN PARALLEL PROCESSING (3 semester hours) Topics include parallel computation models, interconnection networks, principles for the design of parallel algorithms, parallel complexity classes and inherently sequential problems. Selected topics in parallel computation. (May be repeated for credit with the approval of a graduate adviser.) Prerequisites: CS 6369, CS 6376. (3-0) CS 7378 RECENT ADVANCES IN OPERATING SYSTEMS (3 semester hours) Topics include security and protection, computer networks, modularization of systems, language design for asynchronous systems parallel programs, and proof correctness of asynchronous systems. May be repeated for credit with approval of a graduate adviser. Prerequisite: CS 6378. (3-0) CS 7380 COMPUTATIONAL GEOMETRY (3 semester hours) Survey of recent results in the application of computational techniques to geometric problems. Convex hulls, searching, proximity problems, Voronoi diagrams, intersections, rectilinear geometry, polygon decomposition, motion planning, applications. Prerequisite: CS 6363. (3-0) CS 8102-8602 TOPICS IN COMPUTER SCIENCE (1-6 semester hours) (May be repeated to a maximum of 9 hours.) ([1-6]-0) CS 8107-8907 RESEARCH (1-9 semester hours) Open to students with advanced standing subject to approval of the graduate adviser. ([1-9]-0) CS 8333 ADVANCED PROJECT (3 semester hours) A project related to recent advances in computer science research. Available to Master and Ph.D. students. (May be repeated to maximum of 6 hours) Prerequisites: consent of a faculty member who will supervise the project. (3-0) CS 8398-8998 THESIS (3-9 semester hours) (May be repeated for credit.) ([3-9]-0) CS 8399-8999 DISSERTATION (3-9 semester hours) (May be repeated for credit.) ([3-9]-0)

Download 25.09 Kb.

Share with your friends:



The database is protected by copyright ©ininet.org 2024
send message
    Main page
graduate program
computer science program