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,.

1. Introduction

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.

2. Course Contents

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.

Course outline 0.5 Predicate Logic and Gates 12   Propositions (Rosen 1.1) 0.5   And, Or, Not, Xor, Nand, Nor, Truth Tables (Rosen 1.1; Bebop 5) 1.5   Conditional, Logical Equivalences (Rosen 1.1, 1.2; Bebop 9) 2   How a computer represents values (Bebop 8) 2.5   Adders, decoders, multiplexers (Rosen 10.3; Bebop 11) 2   Minimization, Karnaugh maps (Rosen 10.4; Bebop 10) 1.5   Predicates, quantified statements (Rosen 1.3, 1.4) 2 Proofs 8   Proof techniques (Rosen 1.5; Velleman 3) 5     Introduction, rules of inference, and Direct proofs 2     Indirect proofs 2   Induction (Rosen 3.3, 3.4) 4     Introduction 1     Strong and weak induction 3 Sets, Relations and Functions 8   Set theory (Rosen 1.6, 1.7) 2.5   Functions (Rosen 1.8) 1   Relations (Rosen 7) 4.5 Finite automata 3   The idea of state, flip flops (Bebop 11) 1   Formal definitions and applications 2 A simple Fetch Decode Execute machine 3

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.

3. Details about the first offering

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.

• Lab 1 started just after we had introduced gates in class, and was divided in two parts. The first part was an introduction to TkGate. The students were asked to go through parts of the tutorial that comes with TkGate, to simulate a simple circuit consisting of a few gates, switches and LEDs, and to make small changes to that circuit. In the second part, they learned how to use the Magic Box and the breadboard, and implemented their circuit from the first part.
• Lab 2 dealt with arithmetic operations, and started right after we had discussed adders in class. First the students learned how to combine multiple wires into a bus using TkGate. Then they used that knowledge to implement a circuit that can either add or subtract, and then a simple multiplier. That last part was done in TkGate only, and was not implemented on the breadboard, because it would have required an excessive number of wires). Most students found the part about the multiplier difficult.
• Lab 3, starting shortly after we had talked about Karnaugh maps in the lectures, asked the students to design some simple combinatorial circuits and to minimize them using Karnaug maps.
• Lab 4 was an introduction to state and flip-flops, and took place a little bit before we discussed that topic in class. The lab did not assume understanding of how flip-flops are built. All the students needed to learn was how to use them. We asked the students to design a shift register, and then a counter that could count either up or down, and load a value specified by the positions of the switches. The students did not have any major difficulties learning how to use flip-flops, but they found the counter difficult to design.
• Lab 5, like lab 1, was split into two fairly clearly separated parts. In the first part, the students experimented with reading value from and writing values to a small memory chip. In the second part, they used TkGate to see how a simple computer executes a machine-language program, and were then asked to modify that program.

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.

4. Student's reactions

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:

• What did you like most/least about the tutorials?
• What did you like the best about the labs and what improvements would you suggest we make to the labs?
• How much (and how) did you use each of the textbooks for the course? Were they helpful? What did you like/dislike about each of them?
• Do you feel we succeeded in showing the relationships between the two components of the course (the mathematical portion and the hardware portion)? Why, or why not?
• Did the course help you get excited about computer science? Why or why not?

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.

5. Possible changes following students' reactions

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.

• Allow students to work in pairs in the lab. This will help address the complaints about the length of the labs, and make them more pleasant for students who do not like to wire up circuits (as long as they team up with a student who likes that aspect of the labs). It will also reduce the number of questions that the teaching assistants need to answers, and hence reduce the delay between the time where a student raises his/her hand, and the time where a teaching assistant is available to answer the question. Finally, students will also be able to buy the Magic Box as a team, thus halving the cost from $70 to $35 per student.
• Replace the ``Bebop to the Boolean Boogie'' text by a custom handout that discusses only the topics that we need for the purposes of the course, and covers the one or two aspects of Computer Hardware that we discuss, but are not covered by ``Bebop to the Boolean Boogie'' (for instance adders -- a very surprising omission). We would still keep ``Bebop to the Boolean Boogie'' on our list of reference, and add it to the reserve list at the library. However the students, a majority of which found it almost useless, will not have to buy it any longer.
• Introduce formal proofs and rules of inference earlier. Proofs are a fundamental part of CPSC 121. However, because of the need to discuss basic concepts of both logic and circuits, the current ordering of the topics delays them until about one month into the course. Students needs to see proofs early and often if they are to become comfortable proving theorems by the end of the course. An earlier introduction of direct proofs would help with this.
• Move our discussion of relations to the end of the course. In term 2, we ran into problems because we had not covered enough about the Simpler Computer by the time the students needed the information for their lab. We thus had to make part 2 of lab 5 optional. Postponing relations would allow us to resolve that problem. Also, by the time students had learned about indirect proofs, proofs by induction, set theory and functions (all back to back), they were ready for a change. Inserting our discussion of how to build a simple computer at that point would achieve that.
• Some aspects of the course, more specifically proofs, set theory, and relations, do not relate well to accessible topics in Computer Hardware. We will try to find other areas or applications on these topics in Computer Science, and possibly have part of one lab dedicated to them. For instance, we might get the students to query an SQL database to gain hands-on experience on how relations are used.

6. Conclusions and Future Plans

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).

Acknowledgements

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).