Curriculum Proposal to SCS Faculty May 2011

Overview

This document contains course changes proposed by the SCS Curriculum committee for the 2012/2013 academic year. These changes are part of our multi-year effort to overhaul our undergraduate curriculum. Our key goals have been to align the contents of our courses with the changes in our field and with the changing capabilities and interests of our incoming students. Our intention is that these changes will improve student retention and overall performance. Note that the proposals below should be seen as a continuation of the changes began with COMP 1405 and 1406.

The changes to the theory courses are primarily designed to make those courses more approachable for incoming students with less mathematical background. 1805 will cover topics that we believe are a better fit for first year students. (Some topics have been added while others have been removed.) A new course, 2804, will handle the topics that were removed from 1805 and cover additional topics such as randomization that are not covered in currently required courses. 2804 can also serve as an alternative way to fulfill our stats requirement (e.g., substitute for STAT 2605, Probability Models). To make room for these changes, 2805 will no longer be a required course (DFAs will be covered now in 1805, while other formal language topics are omitted). COMP 3804 remains a required course.

The changes to the other courses are primarily designed to bring topics that are either taught in third year or, in some cases not at all, into second year. As part of this, we have embedded the teaching of specific programming languages within the context of other, related CS topics. COMP 2401, our C course, becomes a systems programming course that covers the fundamentals of UNIX-like operating systems and how they relate to basic systems architecture. 2404, the current C++ course, becomes an introductory software engineering course that (for now) is taught using C++. 2405, our currently optional Internet programming course, becomes a required course that covers the basics of dynamic runtime environments and databases as part of teaching about the foundations of modern web applications.

We also propose to eliminate COMP 2003, as its primary focus, assembly language programming, is now a specialized topic in computer science. Its other topics should be covered in other courses.

One potential benefit of these changes to second year is that they allow several currently required third year courses, namely COMP 3000 (Operating Systems), COMP 3005 (Databases), and COMP 3007 (Programming Paradigms), to become more specialized, advanced courses that are required by some, but not all of our streams. Which streams would require theses courses still remains to be decided as part of a general reworking of our streams.

In the rest of this document we first outline how topics that were covered in 2003 and other third year courses are being moved into second year. We then give specific course descriptions and rationales.

Courses to be Removed

• COMP 2003
  • assembly language => exposure through COMP 2401 and 2405
  • digital logic => COMP 1805
  • number representation => COMP 1805 and 2401
  • processor architectures, interrupts, devices => exposure in COMP 2401
  • multicore => cross-cutting concern

Courses to be Upgraded

We propose to keep the following courses, but not include them in the set of minimum required courses. To facilitate this, we have moved selected topics to other required courses. (Note that at this time we have not finished our design of third year or adjusted streams.)

• COMP 2805
  • finite automata => COMP 1805
  • rest of formal languages, computability, automata theory => stays
• COMP 3000: operating systems
  • programmer view of following => COMP 2401
    • process management
    • memory management
    • process coordination and synchronization
    • inter-process communication
    • file systems
    • networking
  • kernel view of above => stays
  • real-time clock management => stays
  • I/O device drivers => stays
• COMP 3005
  • SQL => COMP 2405
  • data models => COMP 2405
  • database design => COMP 2405
  • entity relationship modeling => stays
  • object-oriented database design, OQL => stays
  • the relational algebra => stays
  • normalization theory => stays
  • physical data organization => stays
• COMP 3007
  • functional languages, closures => COMP 2405
  • assignment-free programming => COMP 2405
  • recursive functions => cross-cutting, esp. COMP 1406
  • metacircular interpreter => stays
  • prolog, backtracking, cutting, negation => stays
  • semantics of functional programming => stays

COMP 1805: Discrete Structures I

Old Course Description

Introduction to discrete mathematics and discrete structures. Topics include: propositional and predicate calculus, Boolean algebra, introduction to complexity of algorithms, mathematical reasoning, counting, recurrences, relations, introduction to graphs.

Prerequisite: one Grade 12 university preparation mathematics course.

New Course Description

Introduction to discrete mathematics and discrete structures. Topics include: propositional logic, predicate calculus, set theory, complexity of algorithms, mathematical reasoning and proof techniques, recurrences, induction, finite automata and graph theory. Material is illustrated through examples from computing.

Prerequisite: one Grade 12 university preparation mathematics course.

Rationale

1805 is notoriously difficult for first-year students because in the current course, too many topics are covered for a one term introductory first-year discrete math course. Therefore, to address this situation, we propose to move some of the more advanced material into a second course (COMP2804 Discrete Structures II). Specifically, we propose to move Boolean algebra, counting, discrete probability, some of the more advanced functions and advanced sequences and sums, and methods on how to solve recurrence relations.

COMP 2804: Discrete Structures II

New Course Description

A second course in discrete mathematics and discrete structures. Topics include: counting, sequences and sums, discrete probability (including random variables, expectation, linearity of expectation, dependence, concentration results, distributions), basic statistics, recurrence relations, randomized algorithms. Material is illustrated through examples from computing.

Prerequisite: COMP 1805

Rationale

This is the course that contains the more advanced material from the original version of COMP1805. As noted above, we cover Boolean algebra, counting, discrete probability, some of the more advanced functions and advanced sequences and sums, and methods on how to solve recurrence relations. These are topics that are currently covered in COMP1805. However, students are having too much difficulty grasping all of the different topics in a one term course at the first year level. This course will also cover the basic probability and statistics that Computer Science majors should know, thus removing the need for a dedicated statistics course in second year.

COMP 3804: Design and Analysis of Algorithms I

Old Course Description

An introduction to the design and analysis of algorithms. Topics include: recurrence relations, sorting and searching, divide-and-conquer, dynamic programming, greedy algorithms, NP-completeness.

Prerequisites: COMP 2002 or COMP 2402, and either COMP 1805/MATH 1805 or both of MATH 2007 and MATH 2108, or equivalents.

New Course Description

An introduction to the design and analysis of algorithms. Topics include: divide-and-conquer, dynamic programming, linear programming, greedy algorithms, graph algorithms, NP-completeness.

Prerequisites: COMP 2002 or COMP 2402, and COMP 2805 or COMP 2804 or both of MATH 2007 and MATH 2108, or equivalents.

Rationale

This course description has been revised to reflect the fundamental topics that are being covered in 3804. Rather than emphasize sorting and searching, instructors may choose other algorithms to illustrate the taught concepts. Graph algorithms have always been covered in this course but did not appear in the course description. Note that recurrence relations are now covered in 2804.

COMP 2401: Introduction to Systems Programming

Old Course Description

Introduction to programming with procedures and primitive data types, designed for B.C.S. students. Topics include: arrays, strings, pointers, heap and stack memory allocation and deallocation, iterative and recursive linked list manipulations, system/library calls.

Precludes additional credit for COMP 1002, COMP 1402, COMP 2001, SYSC 1102, and ECOR 1606.

Prerequisite: COMP 1406.

Restricted to students registered in the B.C.S. program, combined Honours in Computer Science and Mathematics, Honours Computer Mathematics,and Honours Computer Statistics.

Lectures three hours a week.

New Course Description

Introduction to system-level programming with fundamental OS concepts, procedures, primitive data types and user-defined types, designed for B.C.S. students. Basic OS topics include programmer view of the following: process management, memory management, process coordination and synchronization, inter-process communication, file systems and networking. Other topics include: pointers, heap and stack memory allocation and deallocation, system and library calls.

Precludes additional credit for COMP 1002, COMP 1402, COMP 2001, SYSC 1102, and ECOR 1606.

Prerequisite: COMP 1406.

Restricted to students registered in the B.C.S. program, combined Honours in Computer Science and Mathematics, Honours Computer Mathematics,and Honours Computer Statistics.

Lectures three hours a week, tutorials one hour a week.

Rationale

The old 2401 course spent time teaching data structures that are better covered in 2402. Instead, we propose to teach C programming in the context in which it was developed, namely UNIX systems programming. Key OS concepts such as memory and process management are easily taught using relatively small C programs that also use most C language features. Lectures will cover higher-level OS and systems programming concepts; tutorials will cover the details of C programming.

COMP 2404: Introduction to Software Engineering

Old Course Description

Programming in C++

In-depth study of the language C++ from a software engineering perspective, with emphasis on features supporting the development of large efficient and reusable systems. Topics include: encapsulation, templates, references, constructors and destructors, overloading, memory management, exception handling, and the standard template library.

Precludes additional credit for COMP 2004 and SYSC 2004.

Prerequisite: COMP 2401. Restricted to students registered in the B.C.S. program, the combined Honours in Computer Science and Mathematics, Honours Computer Mathematics, and Honours Computer Statistics.

Lectures three hours a week.

New Course Description

Introduction to Software Engineering

Introduction to object-oriented software development, with emphasis on design and implementation of medium-sized programs. Topics include abstraction, modularity, encapsulation, reusability, and design patterns.

Precludes additional credit for COMP 2004 and SYSC 2004.

Prerequisite: COMP 2401. Restricted to students registered in the B.C.S. program, the combined Honours in Computer Science and Mathematics, Honours Computer Mathematics, and Honours Computer Statistics.

Lectures three hours a week and tutorials one hour a week.

Rationale

The original 2404 spent a significant amount of time discussing the minutiae of C++ without teaching students the rationale for its more significant features. The revised course will teach language features in the context of software engineering concepts and practice, thereby giving students a better appreciation for when and why to use the various features of C++.

COMP 2405: Internet Application Programming

Old course description

Design and implementation of Internet application programs. Topics include: fundamentals of the Web, introduction to client/server architectures, Internet programming, Web browsers, hypertext links, network programming.

Precludes additional credit for COMP 2005.

Prerequisite: COMP 2401 and COMP 1406.

Restricted to students registered in the B.C.S. program, combined Honours in Computer Science and Mathematics, Honours Computer Mathematics, and Honours Computer Statistics.

Lectures three hours a week.

New course description

An introduction to Internet application development that emphasizes the computer science fundamentals of the technologies underlying web applications. Topics include: scripting and functional languages, language-based virtual machines, database query languages, remote procedure calls over the Internet, and performance and security concerns in modern distributed applications.

Precludes additional credit for COMP 2005.

Prerequisite: COMP 2401.

Restricted to students registered in the B.C.S. program, combined Honours in Computer Science and Mathematics, Honours Computer Mathematics, and Honours Computer Statistics.

Lectures three hours a week, tutorials one hour a week.

Rationale

The modern web is arguably the most important programming platform today. Its fundamentals, however, were not taught in any required course. In addition, the old 2405 omitted the key features that make web programming different from standard Java or C/C++, namely the use of dynamic languages with many functional language features, and the use of databases as persistent stores.

We envision roughly two-thirds of the course on web programming languages - Javascript and PHP - and their implemenation, and one third on databases. The fundamentals of distributed programming, security, and the details of the web environment will be covered throughout the course through concrete examples used to illustrate the covered programming and database concepts.