The Department of Computer Science at the University of British Columbia started offering its new first and second-year program in September 2003. One of these new courses integrates topics normally discussed in a stand-alone Discrete Mathematics course with closely related topics that can usually be found in an introductory course on Computer Organization. In this paper, we discuss the motivations that lead to the creation of this course, its organization, and finally the students' reactions.
Keywords: discrete mathematics, circuits, first-year course,.
In the Fall of 2001, members of a committee in the Department of Computer Science at the University of British Columbia began discussing a major redesign of the first two years of its programs. This redesign involved replacing all of the first and second year courses. One of our goals was to better show the relations between the topics that are typically discussed at that level.
It is still too early to tell how effective our redesign was, as we are only halfway through the second term with our new program, and over half of the new courses still haven't been taught. The topic of this paper is one of our new first-year courses: CPSC 121. This course offers an introduction to two topics that are intimately related: Computer Hardware, and Discrete Mathematics (including logic). Somewhat surprisingly, we have been unable to find any other similar course in North America.
The main principle underpinning the course is that most low-level computer organization is closely related to a mathematical concept. For instance, combinatorial circuits rely almost exclusively on propositional logic. Sequential circuits, on the other hand, can be modeled using finite state machines. In the first and second-year courses that we are replacing, the topics related to machine organization were covered in one course (CPSC 218), while the more mathematical ones were discussed in another course (CPSC 220). Worse, since neither course was pre-requisite to the other, both courses needed to cover propositional logic, and they did it from different viewpoints without being able to relate one viewpoint to the other. This is the type of problems that we are trying to correct with this new course.
The remainder of this paper is organized as follows: we start by discussing the topics that are covered in the course. Next, we describe some details of the first two offerings of the course, especially the labs, and the feedback we got from students about the course. We then list some of the changes that we are thinking of making for future offerings. Finally, we summarize our experiences in teaching the course.
The lectures introduce the discrete mathematics concepts, and the related hardware implementation, with an emphasis on problem-solving. Following the principle discussed in the introduction, hardware topics related to a specific mathematical concepts are covered with the mathematical concept, not separately. The contents of the course are listed below. The numbers at the right indicate the number of lecture hours we spent on each topic (approximately), with colors used to differentiate between chapters, sections and subsections.
The biggest downside we have found so far with this ordering is the fact that we don't get to formal proofs until almost the middle of the term. We are currently trying to find a way to introduce them earlier, as this is a concept that the students need to be exposed to early and often. We should also point out that the remaining topics in Discrete Mathematics that are covered in a typical undergraduate Computer Science course on the subject will be discussed in CPSC 221, our new second-year Data Structures course.
Because the course touches on two areas, we used two required textbooks: a book by Rosen for the Discrete Mathematics portion of the course (this book will also be used in CPSC 221), and a rather unusual text titled "Bebop to the Boolean Boogie" by Clive Maxfield for the hardware concepts.
The course format consists of three hours of lecture, a one-hour tutorial, and a two-hour lab per week. Weekly written assignments help the students practice the concepts introduced in the lectures, and are where the mathematical concepts introduced in the course are exercised. Topics related to computer organization are practiced mostly in the labs, although they also appear on assignments from time to time.
For the first offering of the course, we designed a set of five two-week labs that guide the students through the design of solutions to specific problems. The students implement their solutions on a simple hardware kit that we have designed, and that we called The Magic Box (see the figure).
The use of the kit helps make the solutions more concrete. In order to avoid being tedious, none of the labs require more than 30 wires to implement. Solutions that would be too tedious to wire up are instead implemented using a software application called TkGate, where the students are able to cut and paste parts of their designs, group multiple wires into one, etc.
We in fact ask the students to implement and debug all of their solutions using TkGate before they implement them on the Magic Box.
Here is a short description of the labs contents, as well as where we were (or expected to be) in the course at the beginning of the lab.
Most labs also contained a challenge problem: a problem much more difficult than the other problems in that lab, which was worth a small number of bonus marks. The challenge problems were aimed at the top students in the class, who might otherwise have been bored by questions that they found too easy.
In the first term that the course was offered, we did two short surveys to ascertain how the course was going. The first survey was conducted about halfway through the term, while the second one was done near the end of the term. The reactions of the students who took the course were overall positive. Most of the complaints seemed related to the length of the labs. Upon further inspection, it seems that many of these stemmed from wiring problems that caused students to waste a lot of time finding the one wire that was not connected properly on their Magic Box.
We conducted a more extensive survey near the end of the second term. The students were first asked to tell us how they found the pace at which we had covered the various topics (a bit too slowly, just the right speed, a bit too fast, or much too fast). We then asked the following questions:
Students generally found that we had gone a bit too fast on proof techniques (except for mathematical induction), sets, functions and relations. That is not entirely surprising, as these were also the sections that students had difficulties with in the more traditional second-year Discrete Mathematics course that is being replaced by CPSC 121 and 221.
Most students said they had enjoyed the labs, although many found that wiring their designs on the breadboard connected to the Magic Box was time consuming. Almost all of them found TkGate useful, fairly intuitive and relatively easy to use. In tutorials, we had the TAs ask the students to work on some problems in groups, and present their solutions as a group. This seemed generally appreciated, although it took a few weeks before the students became comfortable with this approach.
Some students found the textbook by Rosen useful, although many students found it dry and difficult to read. It has large numbers of problems that aren't matched by any other textbooks we have seen, a fact that the students liked. Opinions on the other textbook ("Bebop to the Boolean Boogie") were even more sharply divided: some students liked it a lot; others hated it. The majority however said they didn't think it was useful or necessary.
With regard to showing the relationships between the two components of the course, it seems that the connection between some of the early sections of the course and combinatorial logic worked well. However students had a much more difficult time seeing the relevance of set theory, functions or relations.
Finally, we had mixed feedback on our last question. Some students felt strongly that the course helped them get excited about computer science. Others found that it turned them off because it was too difficult and mathematical, or simply stated that CPSC 111 (our other first year course, an introduction to programming that uses Java) was more their idea of what Computer Science is about. We believe that reaction is a consequence of the difficulties students had in seeing how set theory, functions and relations might be useful in Computer Science.
We are presently contemplating several changes that might enable us to keep intact all of the aspects of the course that worked well, while improving on aspects that did not work as well.
Our main goal for the next year is to try out some or all of the possible changes explained in Section 5. There are undoubtedly several other things we can try to introduce proofs at an earlier stage of the course, and yet still maintain the nice continuity that we currently have in the first section of the course, where topics move naturally from their mathematical aspect to their implementation, and then back to the mathematics. We also want to develop new labs that will hopefully better integrate the two subjects than the ones we currently have, and that are somewhat hardware-centric.
Finally, our long-term plans are to determine whether or not the current format of the course is optimal, and to study whether or not the students retain a better understanding of the interplay between hardware and mathematics (and, in a broader setting, whether they gain an appreciation for the way in which the various areas of Computer Science interact and come together).
Several people made invaluable contributions throughout the development of the course and its first offerings, and I would be remiss not to thank them. Thus, thanks go to Mark Greenstreet for his help with the computer hardware topics of the course (Mark also co-taught the first offering), to Anthony Winstanley for the design of the Magic Box, to Ian Cavers for his notes and discussions on the more theoretical aspects of the course, to Adam Longton for his work on the labs, and to the TAs and students for being willing to act as guinea pigs, and for their feedback (admittedly, they had little choice in the first matter).