6.16	Computer Science

Head: John Bate
General Office: E2-445 EITC
Telephone: (204) 474 8313
Fax: (204) 474 7609
Graduate Program Assistant: Lynne Romuld
Email: romuld@cs.umanitoba.ca
Website: www.cs.umanitoba.ca

Academic Staff

Program Information
The department offers Master's and Ph.D. programs at the graduate level, which cover many areas of computer science. The department also participates in the new Master's in Mathematical, Computational and Statistical Sciences program offered through the Institute of Industrial Mathematical Sciences. Graduates find employment in industry and academia.

Fields of Research
The department has people working in the areas of algorithms and complexity, computer graphics, artificial intelligence and expert systems, robotics, computer communications and networking, parallel computing, databases, distributed computing, graph theory, number theory and cryptography, simulation, software engineering, text processing, hypertext and videotex and the theory of languages and environments. More information about specific individuals and their current graduate students can be found on the department web pages.

Research Facilities
The department provides each graduate student with a study space and access to computers, laser printers, mail, photocopier, fax machine, a reading room and a lounge.

Computing facilities for research include a large number of UNIX workstations, PC's, and some Macintosh computers as well as equipment in individual's research labs. Operating systems used include Solaris, Linux, AIX, Windows XP and 2000, and MacOS.

M.Sc. in Computer Science

Admission
Admission requirements are those of the Faculty of Graduate Studies found in the Graduate Studies Regulations Section of this Calendar. Students may be admitted to the Master's program if they hold an Honours Bachelor's degree in Computer Science and if they present a suitable selection of courses. However, space is limited and only the best qualified students will be admitted.

Students can also be admitted to the Master's program upon successful completion of their pre-Master's program. In special cases, where a student holds a first or upper second class Honours bachelor's degree and has previous experience or academic qualifications in Computer Science equivalent to the pre-Master's program, consideration will be given to his/her admission directly into the Master's program. Please contact the Department for details.

Application Deadlines
The Department of Computer Science allows students to begin their program in September or January. For admission for each of these start dates, Canadian/U.S. students should send their applications with complete supporting documentation to the Department of Computer Science no less than three (3) months before the intended start date. All other students should have their applications with complete supporting documentation received by the Department of Computer Science no later than eight months (8) before the intended start date.

Program Requirements
Minimum program requirements of the Faculty of Graduate Studies are found in the Graduate Studies Regulations Section of this Calendar. Students must complete 12 credit hours of coursework and a thesis. All credit hours must be at the 700/7000 level and must include the 0-credit-hour Research Methodologies course. See the departmental supplemental regulations and Student Handbook for information. Students must consult with their departmental advisor prior to deciding on courses. The courses listed below may not all be offered in any one particular year.

Second language reading requirement: none

Expected time to graduate: two years

Ph.D. in Computer Science

Admission
Admission requirements are those of the Faculty of Graduate Studies found in the Graduate Studies Regulations Section of this Calendar. A candidate must normally complete an M.Sc. degree before entering the Ph.D. program. Individual qualifications other than these will be considered.

Application Deadlines
The Department of Computer Science allows students to begin their program in September or January. For admission for each of these start dates, Canadian/U.S. students should send their applications with complete supporting documentation to the Department of Computer Science no less than three (3) months before the intended start date. All other students should have their applications with complete supporting documentation received by the Department of Computer Science no later than eight months (8) before the intended start date.

Program Requirements
Program requirements are those of the Faculty of Graduate Studies found in the Graduate Studies Regulations Section of this Calendar.

Second language reading requirement: none

Expected time to graduate: four years

Course Descriptions

COMP 7220 Research Methodologies Cr.Hrs.0 (Formerly 074.722) This course explores the research process in general and the resources for research in computer science. Traditional research approaches and use of emerging technology will be discussed. Attendance at department seminars and classes is required. The course is evaluated on a pass/fail basis.

COMP 7570 Advanced Topics in Computer Science 1 Cr.Hrs.3 (Formerly 074.757) Topics of current research interest in areas of computer science, available on an occasional basis, subject to the interests and availability of faculty. Prerequisite: written consent of instructor.

COMP 7580 Advanced Topics in Computer Science 2 Cr.Hrs.6 (Formerly 074.758) Topics of current research interest in areas of computer science, available on an occasional basis, subject to the interests and availability of faculty. Prerequisite: written consent of instructor.

COMP 7700 Advanced Design and Analysis of Algorithms Cr.Hrs.3 (Formerly 074.770) An advanced course covering models of computation, advanced analysis techniques, lower bounds, NP-completeness (from an algorithmic viewpoint), with applications of these techniques to various areas. Prerequisites: COMP 3170 (or 074.317) or equivalent or written consent of instructor.

COMP 7710 Group Algorithms and Graph Isomorphisms Cr.Hrs.3 (Formerly 074.771) Techniques for representing and manipulating permutation groups by computer; Schreier s algorithm, stabiliser towers, orbits, block systems, graph isomorphism, coset enumeration in permutation groups, the Butler-Sims base change algorithm. Not to be held with the former 074.727 or COMP 7280 (or 074.728). Prerequisites: COMP 4340 (or 074.434) or equivalent or written consent of instructor.

COMP 7720 Advanced Topics in Algorithms Cr.Hrs.3 (Formerly 074.772) Topics of current research interest in advanced algorithms. Possible topics include string matching, data compression, computational geometry, probabilistic algorithms; subject to the interests and availability of faculty. Prerequisites: COMP 3170 (or 074.317) or equivalent or written consent of instructor.

COMP 7730 Theory of Computation and Complexity Cr.Hrs.3 (Formerly 074.773) Study of the nature and complexity of computations. Formal theory of computability and decidability. Complexity on Turing machines, RAM s and circuits. Non-deterministic computation and NP-completeness. New developments on topics including randomized algorithms, parallel computation, counting problems, and approximation. Prerequisites: COMP 3170 (or 074.317) and COMP 3030 (or 074.303) or equivalents or written consent of instructor.

COMP 7740 Symbolic and Algebraic Computation Cr.Hrs.3 (Formerly 074.774) Problems in both the theory and practice of symbolic and computational algebra. Possible topics include implementation issues in Computer Algebra Systems, polynomial factoring, symbolic solution of systems of equations, Grobner bases, probabilistic techniques, algebraic complexity theory. Applications to cryptography, error correcting codes, robot motion planning, and others. Prerequisite: written consent of instructor.

COMP 7750 Advanced Topics in Computation Theory Cr.Hrs.3 (Formerly 074.775) Topics of current research interest in computation and complexity theory. Possible topics include decidability and complexity theoretic issues in parallel computation, cryptography, graph theory, or number theory, subject to the interests and availability of faculty. Prerequisite: written consent of instructor.

COMP 7760 Algorithmic Methods in Number Theory and Combinatorics Cr.Hrs.3 (Formerly 074.776) Large scale problems arising in combinatorics and number theory; practicable algorithms for solution of such problems. Computer implementation of these algorithms. Prerequisite: written consent of instructor.

COMP 7770 Coding Theory Cr.Hrs.3 (Formerly 074.777) Algebraic background of coding theory. Theory of linear codes. Hamming, Golay, Reed-Mller, Macdonald, and Hadamard codes. Structure of finite fields. Application to cyclic and Bose Chaudhuri codes. Decoding algorithms and error-correcting bounds. Specialized topics. Prerequisite: written consent of instructor.

COMP 7780 Queuing Theory and Performance Evaluation Cr.Hrs.3 (Formerly 074.778) Theory and application of queuing systems applied to problems of computer systems performance. Investigation of deterministic and stochastic models of single and multiple queuing systems using analytical, numerical, and simulation techniques. Performance evaluation methods for computer systems and communications networks. Prerequisites: STAT 1000 (or 005.100) or equivalent or written consent of instructor.

COMP 7790 Advanced Topics in Mathematical Foundations Computer Science Cr.Hrs.3 (Formerly 074.779) Topics of current research interest in the area of mathematical foundations of computer science. Possible topics include cryptography, computational number theory, combinatorics, queuing theory, statistical computing and performance evaluation; subject to the interests and availability of faculty. Prerequisite: written consent of instructor.

COMP 7810 Computer Networks Cr.Hrs.3 (Formerly 074.781) A selection of current research topics from such areas as network modeling and analysis, packet switching, circuit switching, non-switched nets, frame relay, cell relay, ATM, integrated voice/ video/data networks, B-ISDN, and emerging technologies. Prerequisites: STAT 1000 (or 005.100) and COMP 4300 (or 074.430) or equivalents or written consent of instructor.

COMP 7820 Advanced Topics in Computer Architecture Cr.Hrs.3 (Formerly 074.782) Topics of current research interest from such areas as computer design and architecture, distributed systems, multiprocessor and parallel systems, computer networks, specialized architectures, and VLSI; subject to the interests and availability of faculty. Prerequisites: written consent of instructor.

COMP 7830 Distributed Database Systems Cr.Hrs.3 (Formerly 074.783) Architecture and management of distributed database systems; distributed design, query processing, transaction management; traditional and object-oriented database systems; overview of existing systems. Prerequisites: COMP 4380 (or 074.438) or equivalent or written consent of instructor.

COMP 7840 Operating Systems Design and Implementation Cr.Hrs.3 (Formerly 074.784) A discussion of the current research issues in operating systems including, but not limited to: distributed operating systems, multiprocessor operating systems, and other application-specific operating systems such as those for mobile computing. Prerequisites: COMP 3430 (or 074.343) or equivalent or written consent of instructor.

COMP 7850 Advances in Parallel Computing Cr.Hrs.3 (Formerly 074.785) This course introduces advanced research topics in parallel architectures, parallel programming, parallelizing compilers, runtime systems, and parallel I/O. Prerequisite: written consent of instructor.
COMP 7860 Advanced Topics in Computer Systems Cr.Hrs.3 (Formerly 074.786) Topics of current research interest in database and operating systems. Possible topics include: operating systems, parallel systems, real-time systems, networks, and database systems; subject to the interests and availability of faculty. Prerequisite: written consent of instructor.

COMP 7870 Advanced Programming Language Design, Translation, and Implementation Cr.Hrs.3 (Formerly 074.787) A selection of topics taken from the following: formal methods for the description and translation of programming languages, parsing theory and methods, automatic translator writing systems, recent developments in programming language design and implementation. Prerequisites: COMP 4290 (or 074.429) or equivalent or written consent of instructor.

COMP 7880 Object-Oriented Software Development Cr.Hrs.3 (Formerly 074.788) Object-oriented principles; OO life cycle models; OO analysis and design; OO programming and testing; discussion on research topics in OO techniques. Prerequisites: COMP 3350 (or 074.335) or equivalent or written consent of instructor.

COMP 7890 Advanced Topics in Languages and Software Cr.Hrs.3 (Formerly 074.789) Topics of current research interest in the areas of programming languages or software engineering. Possible topics include program language design and implementation, visual programming languages, formal specification techniques, and software verification and validation; subject to the interests and availability of faculty. Prerequisite: written consent of instructor.

COMP 7910 Advanced Graphics Cr.Hrs.3 (Formerly 074.791) This course will focus on two major advanced topics in computer graphics: the principles and properties of lighting models such as Phong shading, ray tracing and radiosity; and a selection of visualization and modelling techniques. Prerequisites: COMP 4490 (or 074.449) or equivalent or written consent of instructor.

COMP 7920 Advanced Topics in Graphics and Human Interfaces Cr.Hrs.3 (Formerly 074.792) Topics of current research interest in advanced graphics and human interfaces, chosen from such areas as intelligent user interfaces, user modelling, user interface design, visualization, computer animation, advanced multimedia, and computer-based training; subject to the interests and availability of faculty. Prerequisite: written consent of instructor.

COMP 7930 Natural Language and Speech Processing Cr.Hrs.3 (Formerly 074.793) Analysis and evaluation of computational models of language and speech understanding and generation including: syntactic analysis, semantic interpretation, statistical methods in speech and language understanding, applications of NLP such as machine translation, information extraction, and human-computer interfaces. Prerequisites: COMP 3190 (or 074.319) or equivalent or written consent of instructor.

COMP 7940 Machine Learning Cr.Hrs.3 (Formerly 074.794) This course examines topics in machine learning. Topics will be chosen from: statistical learning, symbolic learning, neural networks, and genetic algorithms. Prerequisites: COMP 3190 (or 074.319) or equivalent or written consent of instructor.

COMP 7950 Advanced Topics in Artificial Intelligence Cr.Hrs.3 (Formerly 074.795) Topics of current research interest in artificial intelligence chosen from such areas as: expert systems, knowledge representation, intelligent systems, planning systems, multi-agent systems, symbolic logic, knowledge engineering, and automated reasoning; subject to the interests and availability of faculty. Prerequisites: COMP 3190 (or 074.319) or equivalent or written consent of instructor.

COMP 7960 Image Processing Cr.Hrs.3 (Formerly 074.796) A detailed study of the methods used for image processing including: image quantization, transformations, enhancement, and analysis. Prerequisites: COMP 4490 (or 074.449) or equivalent or written consent of instructor.

COMP 7970 Curves and Surfaces in Computer Graphics Cr.Hrs.3 (Formerly 074.797) Algorithms and techniques for curve and surface generation, representation, and display in an interactive computer graphics environment. Discussion of applications to computer-aided design and computer-aided geometric design. Prerequisites: COMP 4490 (or 074.449) or equivalent or written consent of instructor.

COMP 7980 Advanced Topics in Scientific and Numerical Computing Cr.Hrs.3 (Formerly 074.798) Topics of current research interest in scientific and numerical computing chosen from areas such as geometric modelling, special splines, problems related to medical imaging, or other topics subject to the interests and availability of faculty. Prerequisites: COMP 7910 (or 074.791) or COMP 7920 (or 074.792) or written consent of instructor.