CR: Theory course 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.