Curriculum Proposal to SCS Faculty May 2011

Overview

This document contains course changes proposed by the 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. 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 fewer topics and will have a greater emphasis on teaching mathematical reasoning. A new course, 2804, will handle the overflow topics 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 coupled 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.

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.

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

Introduction to discrete mathematics and discrete structures. Topics include: counting, sequences and sums, discrete probability (including random variables, expectation, linearity of expectation, dependence, concentration results, distributions), recurrence relations. Material is illustrated through examples from computing.

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.

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.

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.

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.

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 along with weekly one-hour tutorials.

Rationale

   * learn basics of modern web applications?
   * basics of dynamic languages
         o first class functions
         o functional programming concepts (non-mutability) 
   * basics of databases
         o data representation
         o query languages 
   * basics of distributed applications
         o latency vs. bandwidth
         o reliability concerns
         o state vs. stateless