Undergraduate Calendar 2000-2001

Undergraduate Advisors
B.W. Becker, DC 3105, ext. 4661
L. Case, DC 3112, ext. 4452
A. Pidduck, DC 3106, ext. 4662
J.P. Pretti, DC 3107, ext. 6477
S. Safayeni, DC 3107, ext. 6598
T. Vasiga, DC 3103, ext. 6937

Notes

1. The Department of Computer Science has two distinct streams of courses, one for students registered in a Computer Science Major program, and another designed for non-specialists who wish to become sophisticated computer users.
   CS courses numbered with middle digits 4 through 9 are considered CS Major courses and are not normally open to non-CS Major students. All other CS courses numbered with a middle digit of 0 through 3 are non-specialist courses. As such, they will not normally be open to Computer Science Major students, but they are available to all other students in the University, subject to resource limitations.
   CS 120, 130 and 134 are normally restricted to students in the Faculty of Mathematics.
   Any student registered in an Honours BMath program may apply to take CS 240, 241, 246 or 251 (courses that are normally restricted to CS majors) provided the student has a 65% CS major average (see items 2 and 4 in the Faculty Policies section of the Mathematics chapter) and have met the stated prerequisites. Any student registered in an Honours BMath program may apply to take CS 341, 342, 354, 360 or 370 provided they would be admitted to an Honours Computer Science program if they chose to apply (see page 13:11 for details) and have met the stated prerequisites. Students must bring their most recent mark report to a Computer Science Undergraduate Advisor for validation of the above requirements during the normally scheduled preregistration period.
2. Students entering the Faculty of Mathematics have a choice of three entry points in their Computer Science courses. Students with little or no experience programming repetition and selection structures (ifs and loops) should begin with CS 120, followed by CS 130 and CS 134. Students who have substantial experience with repetition and selection should begin with CS 130, followed by CS 134. Students who are familiar with Java or C++, including strong experience in object-oriented programming, are encouraged to begin with CS 134. Students in the CS Major programs are reminded that a minimum of 15 CS courses are required even for those beginning with CS 134.
3. The Computer Science Department is experiencing demand for its courses beyond available resources. Thus, access to Computer Science courses cannot be guaranteed to all students. Every effort will be made to accommodate the students who preregister during published University preregistration periods, during which time, priority will be given to students who are at the appropriate year level. However, admission to specific courses cannot be guaranteed and course substitutions may be required to satisfy degree requirements.
4. All part-time students, as well as full-time non-degree and post-degree students, will normally be limited to at most one Computer Science course per term from the non-specialist offerings. (Post-degree students on academic leave from their home institution should consult a Computer Science Advisor.) Priority for registration will normally be given to students registered full-time in a degree program.
5. Students in first year are limited to one Computer Science course per term. Students in second year are limited to two Computer Science courses per term.
6. The terms in which courses are offered may deviate from those indicated below. Students are advised to consult the University Course Offerings List published at preregistration time.
7. Where there is significant overlap between major and non-specialist courses, the major course can be used to satisfy the prerequisite for non-specialist courses, unless otherwise specified.
8. A CS course may not be taken for credit if it is the prerequisite of another CS credit that has already been granted.
9. Students who have demonstrated exceptionally strong academic performance will be permitted to enrol in 600-level CS courses at the discretion of the instructor, if there is available capacity.
10. The prerequisite phrase "n-year standing" means that a student must have credit for at least three courses at the n-1 level.
11. The standard penalty for cheating will be the assignment of a grade of -100% for the assignment, test or exam in question, with a minimum deduction of 5% from the final course grade. All such incidents will also be reported to the Associate Dean (Undergraduate Studies) of the student's faculty.

CS100s

CS 100 F,W,S 1C,3L 0.5
Introduction to Computer Usage
Introduction to using personal computer hardware and software. Using personal computers as effective problem solving tools for the present and the future. Experience with common application software including word processing, spreadsheets, database management, and electronic communications. Exposure to the Internet and World Wide Web. Programming principles to support the understanding of application software.
Antireq: OAC Computer Science or equivalent
Not open to students who already have credit for any other computing course.
CS 100 cannot be taken for credit toward a BMath Honours degree.
Also available by Distance Education in certain terms.

CS 110 F,W 2C,1T,3L 0.5
Computers as Problem Solving Tools
Effective use of personal computers in solving problems, both through programming and through the use of application software. Overview of computer hardware and software. Use of a high-level programming language. Spreadsheets, word processors, database systems, electronic mail, World-Wide Web. Social implications of computing.
Antireq: OAC Computer Science, CS 100, 120
Not open to students who already have credit for any other computing course.
CS 110 cannot be taken for credit toward a BMath Honours degree.


CS 113 F,W,S 3C,2L 0.5
Developing Programming Principles
Review of fundamental programming concepts and their application in Java. Objects: encapsulation, instantiation, declaration and use, exceptions. Arrays of objects. Using libraries to solve problems.
Prereq: high-school programming course or CS 110
Antireq: CS 102, 112, 130
CS 113 cannot be taken for credit toward a BMath Honours degree.
Also available by Distance Education in certain terms.

CS 114 F,W 3C,1T 0.5
Introduction to Software Development
An introduction to the concepts of software development, some basic programming tools and the ability to evaluate them. Major topics include: abstraction and encapsulation, specification, testing, debugging, dynamic memory management, abstract data types, recursion, and regular expressions.
Prereq: CS 113
Antireq: CS 134, 212
CS 114 cannot be taken for credit toward a BMath Honours degree.
Also available by Distance Education in certain terms.

CS 120 F 2C,2T,2L 0.5
Computers as Problem Solving Tools
Effective problem solving using current computer environments and ones in years to come. A broad understanding of how to use personal computers. Problem solving through computer programming and application software. Strategies for learning about computer technology.
Prereq: Full-time degree registration in the Faculty of Mathematics
Antireq: OAC Computer Science or equivalent.
Not open to students who already have credit for any other computing course.
See Note 2 above.


CS 130 F,W,S 3C,2L 0.5
Developing Programming Principles
Review of fundamental programming concepts and their application in Java. Arrays of simple types. Objects: encapsulation, instantiation, declaration and use, exceptions. Practical programming: design and life-cycle issues. Arrays of objects. Libraries and interactive programming.
Prereq: Exposure to programming, such as Grade 11 Computer Science or CS 120, and full-time degree registration in the Faculty of Mathematics
Antireq: CS 102, 112, 113
See Note 2 above.
Also offered at St. Jerome's University in the Fall term


CS 134 F,W,S 3C,1T 0.5
Principles of Computer Science
An introduction to basic concepts of computer science, including the paradigms of theory, abstraction, and design. Broad themes include the design and analysis of algorithms, the management of information, and the programming mechanisms and methodologies required in implementations. Topics discussed include iterative and recursive sorting algorithms; lists, stacks, queues, trees, and their application; and the history and philosophy of computer science.
Prereq: Full-time degree registration in the Faculty of Mathematics and CS 130 or an equivalent level of knowledge and experience.
Antireq: CS 114, 212
See Note 2 above.
Also offered at St. Jerome's College in the Winter term


CS200s

CS 200 F,W,S 3C,2L 0.5
Concepts for Advanced Computer Usage
Important concepts underlying major personal computer application categories; methodologies for learning and evaluating software; operating system and hardware design from the user's point of view, with implications for maintaining a personal computer. Students are encouraged to use their own personal computer for assignments. A substantial project is required involving the integrated use of several applications.
Prereq: CS 100 or equivalent computing experience.
Not open to students who already have credit for CS 230 or CS 246.


CS 230 W 3C 0.5
Introduction to Computers and Computer Systems
Basic computer architecture, operating system services, and programming languages in support of development of software systems.
Prereq: One of CS 134, 234
Antireq: CS 241
CS 230 cannot be counted for credit in a Computer Science Major program.


CS 234 F,S 3C 0.5
Data Types and Structures
Top-down design of data structures. Using representation- independent data types. Introduction to commonly used data types, including lists, sets, mappings, and trees. Selection of data representation.
Prereq: One of CS 114, 134
Antireq: CS 240, 334
CS 234 cannot be counted for credit in a Computer Science Major program


CS 240 F,W,S 3C 0.5
Data Structures and Data Management
Introduction to widely used and effective methods of data organization, focusing on data structures, their algorithms, and the performance of these algorithms. Specific topics include trees, operations on sets, sorting, priority queues, memory management. A brief introduction to database systems and the analysis of data structure performance and use in these systems.
Prereq: CS 246
Coreq: C&O 230
Antireq: CS 234, 334, 340, E&CE 250
Enrolment is restricted; see Note 1 above.


CS 241 F,W,S 3C 0.5
Foundations of Sequential Programs
The relationship between high-level languages and the computer architecture that underlies their implementation, including basic machine architecture, assemblers, specification and translation of programming languages, linkers and loaders, block-structured languages, parameter passing mechanisms, and comparison of programming languages.
Prereq: CS 246, 251
Antireq: CS 230
Enrolment is restricted; see Note 1 above.


CS 246 F,W,S 3C 0.5
Software Abstraction and Specification
Systematic methods for designing, coding, testing, and documenting medium-sized programs. Major topics include formal specification, abstraction, modularity and reusability. Students will become strong apprentice programmers able to write a clear specification for a problem, read a specification and design the software to implement it, use appropriate data structures in a program, write reusable code and reuse existing code when possible, debug a program, and adequately test a program.
Prereq: CS 134
Antireq: CS 212
Enrolment is restricted; see Note 1 above.


CS 251 F,W,S 3C 0.5
Digital Design and Architecture
Boolean algebra. Design and analysis of both combinational and sequential circuits. Registers, counters, memory, programmable logic. CPU control logic, the arithmetic-logic unit. Input/output and interrupts. Assembly language programming.
Prereq: CS 134 and full-time registration in the Faculty of Mathematics
Antireq: E&CE 223
Enrolment is restricted; see Note 1 above.
Students enrolled in CS/EEE should take E&CE 223


CS300s

CS 316 W 3C,1L 0.5
Introduction to Statistical Problem Solving by Computer
This is an applications oriented course which prepares the nonmathematical student to use the computer as a research tool. Topics include aids for statistical analysis and the preparation of documents such as reports and theses. The course provides sufficient background for application to other problems specific to the individual's field.
Prereq: One statistics course and computer literacy (e.g. CS 100 or high school computing), or consent of instructor
CS 316 cannot be counted for credit toward a BMath degree.


CS 330 F,W,S 3C 0.5
Management Information Systems
An introduction to information systems and their strategic role in business. Topics include types of information systems, organizational requirements, systems development strategies, decision support systems, data and information management, and information systems management, control and implementation.
Prereq: One of CS 134, 114, and registration in 2B or later.
Antireq: CS 480, M SCI 441, ACC 442
CS 330 cannot be counted for credit in a Computer Science Major program.


CS 337 W 3C 0.5
Introduction to Numerical Analysis
Pitfalls in computation; solution of linear algebraic equations; polynomial interpolation; least squares; numerical integration and differentiation. The intent is to expose students to the theory behind modern algorithms for solving mathematical problems.
Prereq: CS 134 or 114, MATH 125 or 136, 128 or 138. CS 234, MATH 126 or 235 and MATH 227 or 237 are recommended.
Antireq: CS 370
CS 337 cannot be counted for credit in a Computer Science Major program.


CS 338 F,W,S 3C 0.5
Computer Applications in Business: Databases
A user-oriented approach to the management of large collections of data. Methods used for the storage, selection and presentation of data. Common database management systems.
Prereq: One of CS 234, 246, 330
Antireq: CS 448
CS 338 cannot be counted for credit in a Computer Science Major program.


CS 341 F,W 3C 0.5
Algorithms
The study of efficient algorithms and effective algorithm design techniques. Program design with emphasis on pragmatic and mathematical aspects of program efficiency. Topics include compression and text searching methods, NP-completeness and approximation algorithms for NP-complete problems; number theoretic algorithms and their implications.
Coreq: CS 360
Enrolment is restricted; see Note 1 above.


CS 342 F,W,S 3C 0.5
Control Structures
An introduction to understanding concurrency and writing concurrent programs, with an emphasis on language constructs used to express and control concurrency, and different concurrent programming techniques and styles. Major topics include: coroutines, mutual exclusion, semaphores, high-level concurrency, deadlock, interprocess communication and process structuring. Students will learn how to structure, implement and debug basic concurrent programs.
Prereq: CS 240, 241
Enrolment is restricted; see Note 1 above.


CS 354 F,W 3C 0.5
Operating Systems
An introduction to the basic components of a modern operating system. Major topics include: concurrency in the large, memory management, device management, file systems, security, networks and distributed systems. Students will learn how to write complex programs that accomplish part of their operation through interaction with the operating system.
Prereq: CS 342
Enrolment is restricted; see Note 1 above.


CS 360 F,W,S 3C 0.5
Introduction to the Theory of Computing
Models of computers including finite automata and Turing machines. Basics of formal languages with applications to syntax of programming languages. Unsolvable problems and their relevance to the semantics of programming.
Prereq: CS 240, 241, Math 239
Enrolment is restricted; see Note 1 above.


CS 370 F,W,S 3C 0.5
Numerical Computation
Principles and practices of basic numerical computation as a key aspect of scientific computation. Visualization of results. Approximation by splines, fast Fourier transforms, solution of linear and nonlinear equations, differential equations, floating point number systems, error, stability. Presented in the context of specific applications to image processing, analysis of data, scientific modeling.
Prereq: MATH 138, 235 and one of CS 234, 246
Antireq: CS 337
Enrolment is restricted; see Note 1 above.


CS400s

CS 430 F 3C 0.5
Applications Software Engineering
An investigation into the role and function of software engineering practice in the construction of computer based systems. Topics include: requirements and specification; documentation techniques; analysis and design; implementation; testing and maintenance; management issues.
Prereq: CS 330 or permission of instructor and registration in third year or later.
Antireq: CS 446
CS 430 cannot be counted for credit in a Computer Science Major program.


CS 432 F,W,S 3C 0.5
Business Systems Analysis
Survey of organization and management theory. Systems theory and the systems approach. Systems design. Database concepts. Implementation and evaluation of computer based information systems.
Prereq: CS 330 and registration in third year or later.
Antireq: CS 445, 482
CS 432 cannot be counted for credit in a Computer Science Major program.


CS 436 W 3C 0.5
Distributed Computer Systems
An introduction to networks and computer systems, reliable communication, layered models, distributed file systems, cryptography, concurrency issues.
Prereq: One of CS 230, 246
Antireq: CS 454, E&CE 428
CS 436 cannot be counted for credit in a Computer Science Major program.


CS 437 W 3C 0.5
Computer Simulation of Complex Systems
Building and validation of stochastic simulation models useful in computing, operations research, engineering and science. Related design and estimation problems. Variance reduction. The implementation and analysis of simulation results.
Prereq: STAT 231
Antireq: CS 457, STAT 371
Cross-listed as STAT 340


CS 442 W 3C 0.5
Principles of Programming Languages
An exposure to important concepts and issues in contemporary programming languages. Data types, abstraction, and polymorphism. Program structure. Lambda calculus and functional programming, logic programming, object-oriented programming. Semantics of programming languages. Critical comparison of language features and programming methodologies using examples drawn from a variety of programming languages including Lisp, Prolog, ML, Ada, Smalltalk, Icon, APL, and Lucid. Programming assignments involve the use of some of these languages.
Prereq: Fourth-year standing in a Computer Science Major program


CS 444 W 3C 0.5
Compiler Construction
Phases of compilation. Lexical analysis and a review of parsing. Compiler-compilers and translator writing systems. LEX and YACC. Scope rules, block structure, and symbol tables. Runtime stack management. Parameter passage mechanisms. Stack storage organization and templates. Heap storage management. Intermediate code. Code generation. Macros.
Prereq: Fourth-year standing in a Computer Science Major program


CS 445 F,W 3C,1T,1D 0.5
Software Requirements Specification and Analysis
Introduction to the requirements definition phase of software development. Models, notations, and processes for software requirements identification, representation, validation, and analysis. An important component of the course is a group project: the software requirements specification of a large software system.
Prereq: CS 342 and registration in a Computer Science Major program.
Coreq: CS 360
Antireq: CS 432
Cross-listed as E&CE 451
Meet times and exact meet types may vary depending on instructor.


CS 446 F,S 3C,1T,1D 0.5
Software Design and Architectures
Software design process and its models, representations of design/architecture, software architectures and design plans, design methods, design state assessment, design quality assurance, design verification. Implementation of a group project specified in CS 445.
Prereq: CS 445 and registration in a Computer Science Major program.
Antireq: CS 430
Cross-listed as E&CE 452
Meet times and exact meet types may vary depending on instructor.


CS 447 W 3C,1T,1D 0.5
Software Testing, Quality Assurance and Maintenance
Systematic testing of software systems, software verification, symbolic execution, software debugging, quality assurance, measurement and prediction of software reliability, project management, software maintenance, software reuse, reverse engineering. Application to the group project from CS 445 and CS 446.
Prereq: CS 446 and registration in a Computer Science Major program.
Cross-listed as E&CE 453
Meet times and exact meet types may vary depending on instructor.


CS 448 F,W,S 3C 0.5
Introduction to Database Management
The course introduces the student to the techniques that have been developed for processing very large collections of data. The requirement that data be held on secondary storage (disks and tapes) has an enormous impact on the design of algorithms to access that data.
Prereq: CS 354 and fourth-year standing in a Computer Science Major program
Antireq: CS 338


CS 450 W 3C 0.5
Computer Architecture
The course is intended to provide the student with an appreciation of modern computer design and its relation to system architecture, compiler technology and operating system functionality. The course places an emphasis on design based on the measurement of performance and its dependency on parallelism, efficiency, latency and resource utilization.
Prereq: CS 251 or 351 or (CS 342 and E&CE 223), and fourth-year standing in a Computer Science Major program
Antireq: E&CE 427, 429


CS 452 F,S 3C 0.5
Real-time Programming
Intended to give students experience with tools and techniques of real-time programming, this course includes not only issues of microcomputer architecture and a real-time programming language and operating system, but also hands-on experience programming a microcomputer for applications such as process control, data acquisition and communication.
Prereq: CS 354 and fourth-year standing in a Computer Science Major program.
Antireq: E&CE 354


CS 454 F,W,S 3C 0.5
Distributed Systems
An introduction to distributed systems, emphasizing the multiple levels of software in such systems. Specific topics include fundamentals of data communications, network architecture and protocols, local-area networks, concurrency control in distributed systems, recovery in distributed systems, and clock synchronization.
Prereq: CS 354 and fourth-year standing in a Computer Science Major program.
Antireq: CS 436, E&CE 428, 454


CS 457 W 3C 0.5
System Performance Evaluation
Basic techniques of system performance evaluation. Specific topics include: performance modeling, discrete event simulation, verification and validation of simulation models, analysis of simulation output, analysis of single server queue and queueing networks, modeling of computer systems, networks, and other queueing or non-queueing systems.
Prereq: CS 246
Antireq: CS 437


CS 462 F 3C 0.5
Formal Languages and Parsing
Languages and their representations. Grammars -- Chomsky hierarchy. Regular sets and sequential machines. Context-free grammars -- normal forms, basic properties. Pushdown automata and transducers. Operations on languages. Undecidable problems in language theory. Applications to the design of programming languages and compiler construction.
Prereq: CS 360 and fourth-year standing in a Computer Science Major program


CS 464 W 3C 0.5
Computational Complexity Theory
The classification of problems according to the computational resources required for their solution, with emphasis on properties of feasible computations rather than on specific algorithms. Topics include: time and space complexity, tractable and intractable problems, computation using randomness, parallel computation.
Prereq: CS 360 and fourth-year standing in a Computer Science Major program. CS 466 is recommended


CS 466 F,S 3C 0.5
Algorithm Design and Analysis
Design of good algorithms and analysis of the resources they consume. Lower bounds on the resource requirements of algorithms to compute certain functions. Problems from the following areas are discussed in this light: sorting and order statistics, data structures, arithmetic computations, the NP-complete problems.
Prereq: CS 341 and fourth-year standing in a Computer Science Major program


CS 472 W 3C 0.5
Numerical Linear Algebra
Direct methods for the numerical solution of linear systems of equations and linear least squares problems. Numerical methods for solving the algebraic eigenvalue problem.
Prereq: CS 370 or 337 and consent of instructor


CS 476 F 3C 0.5
Numeric Computation for Dynamic Simulation
The interaction of continuous dynamic simulation models, numerical methods, and computing environments. Constant coefficient models for restricted operating ranges, linearization. Time stepping techniques for models based on general systems of ordinary differential equations. Stiffness and nonlinearity. Simulation of computer memory circuits. Wave type linear partial differential equations.
Prereq: CS 370 or 337 and consent of instructor
Cross-listed as AM 441


CS 480 W 3C 0.5
Information Systems Management
The integration of business and technical considerations in the design, implementation and management of information systems. Topics include: IS planning and development; business, management, executive, and strategic information systems, including case studies of selected large- scale systems; decision support systems; end-user training and development; systems security, disaster planning and recovery. Practical examples of information systems in industry.
Prereq: Fourth-year standing in a Computer Science Major program
Antireq: CS 330, MSCI 441, (ACC 442)


CS 482 F 3C 0.5
Computational Techniques for Genome Analysis
An introduction to the computer-science principles underlying current techniques in genome analysis, focusing on the design, development, and implementation of these techniques. Specific topics include algorithms for sequence alignment, database searching, sequencing, and structure analysis.
Prereq: BIOL 365, CS 341


CS 483 W 3C 0.5
Computational Techniques in Molecular Evolution
An introduction to the types of computational questions posed in the study of evolution, including models of evolution, inference algorithms, and genome events. Techniques will be examined from both a theoretical and a practical perspective.
Prereq: BIOL 365, CS 341, STAT 231


CS 486 F,W,S 3C 0.5
Introduction to Artificial Intelligence
Goals and methods of artificial intelligence. Methods of general problem solving. Introduction to mathematical logic Mechanical theorem proving. Game playing. Natural language processing.
Prereq: CS 341 and fourth-year standing in a Computer Science Major program
Antireq: E&CE 475, 457


CS 487 W 3C 0.5
Introduction to Symbolic Computation
An introduction to the use of computers for symbolic mathematical computation, involving traditional mathematical computations such as solving linear equations (exactly), analytic differentiation and integration of functions, and analytic solution of differential equations.
Prereq: CS 241, PMATH 334 or consent of instructor


CS 488 F,W,S 3C 0.5
Introduction to Computer Graphics
Software and hardware for interactive computer graphics. Implementation of device drivers, 3-D transformations, clipping, perspective, and input routines. Data structures, hidden surface removal, colour shading techniques, and some additional topics will be covered.
Prereq: CS 342, MATH 235, and fourth-year standing in a Computer Science Major program


CS 492 W 3C 0.5
The Social Implications of Computing
This course is designed to consider the problems encountered by individuals, organizations and society as computer technology is adopted, with a view towards assessing possible courses of action.
Prereq: Fourth-year standing in a Computer Science Major program, or consent of instructor.


CS 494 F,W 3C 0.5
Computers and the Law of Information Technology
An introduction to the subject of computer law, examining current legal issues and problems relating to the use of computer-based information systems, the protection of computer software and data bases, and the acquisition and sale of computer systems.
Prereq: Third-year standing in a Computer Science Major program


CS 498 0.5
Advanced Topics in Computer Science
See the Course Offerings List for topics available.
Prereq: Fourth-year standing in a Computer Science Major program


CS 499 0.5
Readings in Computer Science
Prereq: Fourth-year standing in a Computer Science Major program

The Undergraduate Calendar is published by the
Office of the Registrar, University of Waterloo, Waterloo, ON N2L 3G1 Canada
Inquiries: infoucal@www.adm.uwaterloo.ca
Revised February 2000