This page contains notes and discussions related to the SCS Curriculum Reinvention Committee.

The content below has gratuitous markup so as to make it obvious how to add more stuff.

To edit this page, you first need to create an account - click the link in the top-right of the page. Then click on the edit tab just about the page headline. Or, you can edit individual sections.

Requests for more data

Why are students leaving SCS?
- What are the grades in SCS-related courses for students who change majors out of SCS?
- What majors do they switch to? After how many terms?
DFW and A/B rates for 2009/2010 versus past years in 1405, 1406, 1805?

Courses to be examined

Introductory Programming

COMP 1405 - Introduction to Object-Oriented Programming
COMP 1406 - Design and Implementation of Computer Applications

Theory

COMP 1805 - Discrete Structures
COMP 2805 - Introduction to Theory of Computation
COMP 2402 - Abstract Data Types and Algorithms
COMP 3804 - Design and Analysis of Algorithms I

Intermediate Programming

COMP 1402 - Introduction to Systems Programming
COMP 2404 - Programming in C++

Other Core-ish Courses

COMP 2003 - Computer Organization
COMP 2405 - Internet Application Programming
COMP 3000 - Operating Systems
COMP 3002 - Compiler Construction
COMP 3004 - Object-Oriented Software Engineering
COMP 3005 - Database Management Systems
COMP 3007 - Programming Paradigms
COMP 3008 - User Interface Architecture
COMP 3203 - Principles of Computer Networks
STAT 2507
STAT 2605

CR: COMP 1405/1406 Redesign

Recommendations Summary

"Objects first" is not working, too many students DFW in first year. Also, we've already moved away from objects first in practice. Some leading CS departments, e.g. Waterloo, UofT, & MIT, do not teach objects first (objects are just one topic among many). We're proposing to do the same.
Only cover objects as data structures in first year: no inheritance until last few weeks of 1406.
Inheritance will be covered in 2404 (Programming in C++) - title should change to "Object-Oriented Programming in C++". 2401 covers C and UNIX in the Fall, 2404 covers C++ in the Winter.
Emphasize problem solving in a general-purpose programming language.
Teach only basic programming language structures: loops, conditionals, functions, procedures, exceptions.
No required special applications in 1406.
1405 is an introduction to problem solving through programming, 1406 is a second course on the same topic.
Advanced students would start with 1406 and skip 1405; 1406 shouldn't require knowledge of the specific language syntax used in 1405.
3007 becomes Functional and Concurrent programming. (e.g., cover MapReduce)
2402 will give students extra experience with Java beyond 1405 and 1406.
Challenge: where do students get more experience with object-oriented Java? (How much do they need?) Question: could 3004 provide this, or do we need a new course, maybe just for the software engineering stream?

Required Programming Courses

1405 and 1406
2401, 2402, & 2404
3004 and 3007

Old Course Descriptions

COMP 1405 [0.5 credit] Introduction to Object-Oriented Programming A first course in problem solving and computer programming designed for B.C.S. students. Introduction to object-oriented programming; syntactic constructs, data abstraction, classification and inheritance, typing and polymorphism, testing and debugging. Precludes additional credit for COMP 1005 and SYSC 1100. Prerequisite: 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, tutorial one and a half hours a week.

COMP 1406 [0.5 credit] Design and Implementation of Computer Applications A continuation of COMP 1405 focusing on the design and implementation of complete applications. Topics covered include persistence, graphical user interface design and implementation, event-driven programming, recursion, drawing and manipulating 2D graphics and networking. Precludes additional credit for COMP 1006 and SYSC 1101. Prerequisite: COMP 1405. 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, tutorial one and a half hours a week.

New Course Descriptions

COMP 1405 [0.5 credit] Introduction to Programming I

A first course in programming emphasizing problem solving and computational thinking. Topics include an introduction to computer science, pseudocode, variables, conditionals, iteration, arrays, objects, functions, sorting, searching, and simulation.

COMP 1406 [0.5 credit] Introduction to Programming II

A second course in programming emphasizing problem solving and computational thinking. Topics include object-oriented programming, abstract data types, linked data structures, testing and debugging, recursion, encapsulation and information-hiding, specification, program efficiency, state machines, and exception handling.

Links for May 10, 2010

From Doug

Toronto [1] CSC108 and CSC 148 (150 is an accelerated combo)

Topics:

Program structure: elementary data types,statements, control flow, functions, classes, objects, methods, fields. Lists; searching, sorting and complexity.

Abstract data types and data structures for implementing them. Linked data structures. Encapsulation and information-hiding. Object-oriented programming. Specifications. Analyzing the efficiency of programs. Recursion.

Waterloo [2] CS 135 and 136

Topics:

Syntax and semantics of a functional programming language. Tracing via substitution. Design, testing, and documentation. Linear and nonlinear data structures. Recursive data definitions. Abstraction and encapsulation. Generative and structural recursion. Historical context.

It introduces 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; abstract data types and their implementations.

Princeton [3]

Potential topics from Princeton: hardware and software systems; programming in Java; algorithms and data structures; fundamental principles of computation; and scientific computing, including simulation, optimization, and data analysis.

Alberta [4] CMPUT 174 and 175

Potential topics from Alberta for 1405 and 1406:

computation, states, events, transitions
state machines, simple pattern matching
programming basics (variables, input, output, while, if, etc.)
search
lists, arrays, and hashes
regular expressions and pattern matching
functions, subroutines, and testing
recursion
references and data structures
expression and binary trees
abstract data types
simulation
sorting
abstract data types
objects
graph algorithms
exceptions
little languages
closures

Email to Faculty

The "curriculum reinvention" committee (Anil x 2, Michiel, Mark, Doug, Dave) have been discussing revising our curriculum with the goal of improving engagement and retention of our students, i.e. doing a better job of teaching them. Lately, we've been focusing on the first year programming courses, and would like to get your input on a proposal for a substantial change to 1405 and 1406 (leaving 1005 and 1006 aside for now). Below is a summary of the changes followed by a calendar-like description of the courses.

We're interested in any views you might have. Nothing is set in stone at this point.

The key change we are proposing is to change their focus from learning Java to learning how to solve problems using programs. Key programming concepts are to be taught in as language-independent a manner as possible, e.g., through the use of pseudo-code. Object-oriented programming concepts are present in the courses but are not presented first. 1405 will cover objects as simple data structures, but methods, inheritance etc will be postponed until 1406. Instead, a wide range of basic programming skills will be taught.

The new courses will be structured in some ways as a unit; however, the topics are partitioned so that students with substantial programming experience in any language will have a decent chance of going directly to 1406 (via a placement test).

For the initial course delivery, we are tentatively planning on emphasizing weekly assignments structured around multiple small problems rather than fewer, larger assignments. Also, while Java will be used for both courses, 1405 will use Processing, a Java "subset" designed for image creation. We believe Processing will facilitate more engaging assignments.

These changes will have limited impact on the rest of the curriculum. 2402 (Abstract Data Types) will continue to be taught in Java. 2404, our C++ course, will focus more on problem solving using object-oriented programming and design with C++.

Old Course Descriptions (prereqs etc omitted)

COMP 1405 [0.5 credit] Introduction to Object-Oriented Programming

A first course in problem solving and computer programming designed for B.C.S. students. Introduction to object-oriented programming; syntactic constructs, data abstraction, classification and inheritance, typing and polymorphism, testing and debugging.

COMP 1406 [0.5 credit] Design and Implementation of Computer Applications

A continuation of COMP 1405 focusing on the design and implementation of complete applications. Topics covered include persistence, graphical user interface design and implementation, event-driven programming, recursion, drawing and manipulating 2D graphics and networking.

New Course Descriptions

COMP 1405 [0.5 credit] Introduction to Programming I

A first course in programming emphasizing problem solving and computational thinking. Topics include an introduction to computer science, pseudocode, variables, conditionals, iteration, arrays, objects, functions, sorting, searching, and simulation.

COMP 1406 [0.5 credit] Introduction to Programming II

A second course in programming emphasizing problem solving and computational thinking. Topics include object-oriented programming, abstract data types, linked data structures, testing and debugging, recursion, encapsulation and information-hiding, specification, program efficiency, state machines, and exception handling.

1805 redesign

Jit's comments

Hi Everyone,

Currently, the textbook used is Kenneth H. Rosen, Discrete Mathematics and its Applications, (sixth edition), McGraw-Hill, 2007. This textbook and all other textbooks I have seen so far in Discrete Math all suck. The reason I used this one is because the online materials available to students is quite helpful. I am thinking of converting my notes into a document to either compliment the text or even replace it.

The topics that are currently scheduled to be covered in COMP 1805 are (chapters/sections are in brackets):

1. Logic and Proof, Sets, and Functions: Propositional calculus, predicates and quantifiers. Methods of proof. (1.1 - 1.7) 2. Sets and Functions (2.1-2.4) 3. Algorithms and Their Complexity (Selected material from 3.1 - 3.8) 4. Induction and Recursion. (4.1 - 4.5) 5. Counting: Basic definitions, pigeonhole principle, permutations and combinations. (5.1 - 5.5) 6. Discrete Probability (6.1 - 6.4) 7. Relations: Basic definitions, representation of relations, closures, equivalence relations, partial orderings. (8.1 - 8.6)

8. Elementary Graph Theory: Basic definitions, planar graphs, connectivity, and computer representations of graphs. (9.1 - 9.8)

9. Trees: Paths, cycles, directed trees, search trees, spanning trees. (10.1 - 10.5) 10. Boolean Algebra: Boolean functions and their representation. (11.1 - 11.3)

Over the last 5 or 6 times that I have taught this course, I have never been able to cover everything. I usually decide on the fly which topics to omit or which ones to spend more time on based on feedback that I get from the students via their test marks, assignments and tutorials (I used to teach the tutorials as well). Some years, I did not cover boolean algebra, others I did not teach discrete probability.

After the double cohort, there was a noticeable drop in the level of the students. Prior to the double cohort, the 2 times that I taught this course, in fact, I co-taught with Frank Fiala, I was able to cover everything. So we need to address the reality of our current situation which is that students coming in are weaker and/or do not have as much of a mathematical background/maturity as they used to have. This is why I believe that we should actually introduce a second year course. This would give us the opportunity to spend more time on certain basic topics in first year and more advanced topics in second year.

I believe that one of the main difficulties that the students are having with the material covered in this course is that there are too many new concepts that are taught in a very short period of time. In the past, students in highschool were supposed to take a math course (I forget the number) that actually covered induction, logic and proofs. Many students used to tell me that the first half of the course was a nice review for them. However, I believe we dropped this requirement in our admission criterion, as such, this is the first time that students are seeing many of these concepts.

As I mentioned above, our proposal is to take a few of the topics and move them into a second year discrete math course. Pat Morin, Anil, Michiela and I had looked into finding a nice division of the topics that would give two coherent courses with basic topics being covered in the first year course and more advanced topics in a second year course. I have attached the description below of what we had come up with.

Suggestions for 1805:

I think that the topics that should be kept in 1805 are: Logic/Proofs, Sets and Functions, Intro to Algorithms, Induction/Recursion, Relations/Graphs.

I think that the approach on how the material is taught should be changed. I have been thinking a lot about various ways of introducing/presenting this material. I believe that the best way to present this material is to use many visual examples. I really liked David Mould's idea of using processing as a way of introducing both Logic and Induction/Recursion. Furthermore, I think that Graphs should play a more central role since that is the topic that I found students were able to grasp most easily. In fact, I was thinking that everything (sets, logic, proofs etc) can be taught from a graph point of view. Students are able to relate to finding paths in graphs etc. As such, presenting proof techniques, logic, set theoretic concepts etc from a graph theoretic point of view may really help them grasp the material more easily. For example, when I show them depth first search as a graph exploration method, most students understood the recursion right away. Now, I must admit that I am uncertain if this is because by the time I teach graphs, we are nearing the end of the term and they have seen all the concepts already or if graphs are really a structure they are able to grasp and relate to easily. In either case, this is something I think is worth considering.

COURSE DESCRIPTIONS (Including the new second year course):

COMP1805 Discrete Structures I

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, functions, relations 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 will 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.

COMP2804 Discrete Structures II

Introduction to discrete mathematics and discrete structures. Topics include: counting, Boolean algebra, 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.

Prerequisite: COMP1805

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.

2402 Abstract Data Types and Algorithms

Introduction to the design and implementation of abstract data types and to complexity analysis of data structures. Topics include: stacks, queues, lists, trees, graphs, sorting and searching .

Precludes additional credit for COMP 2002 and SYSC 2002.

Prerequisite: COMP 1406, COMP1805. Restricted to students registered in the B.C.S. program, combined Honours in Computer Science and Mathematics, Honours Computer Mathematics, and Honours Statistics. Lectures three hours a week.

Rationale: Updated the calender description and added COMP1805 as a prerequisite. It seems that this was an oversite and that this course assumes that students are familiar with topics covered in 1805. Specifically, complexity of algorithms and graph theory are assumed when students take this course.

COMP 3804 Design and Analysis of Algorithms I

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

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

Rationale: Added COMP2804 in the list of courses that can be considered as a prereq. Revised the course description to add Graph Algorithms as one of the topics that are covered. Graph Algorithms have always been covered in this course but did not appear in the course description.

COMP 4804 Design and Analysis of Algorithms II

A second course on the design and analysis of algorithms. Topics include: randomized algorithms, amortized analysis, approximation algorithms for NP-Complete problems, advanced graph algorithms. Also offered at the graduate level, with additional or different requirements, as COMP 5703, for which additional credit is precluded.

Prerequisite: COMP 3804 and one of (COMP 2804, Stat 2605) or permission of the School.

Rationale: Updated the course description to reflect what will be taught in the course and also updated the prereqs.

CR: Other CS approaches to Math/Theory

CR: New course descriptions and rationale

CR: Survey of theory requirements in other Canadian Honours programs

CR: Reducing the Core Size