Journal of Computing in Small Colleges, 14(4): 154-162, 1999

Amy Briggs and Matthew Dickerson

Department of Mathematics and Computer Science
Middlebury College
Middlebury, VT 05753

Of the many undergraduate courses offered by a typical computer science department, one of the most challenging to teach is an introductory course for non-majors. There are several difficulties that arise with such a course. Perhaps the central one is that students are not really interested in learning computer science; they are more often interested in "learning a little bit about computers" (or simply in being able to list a computer course on their transcript). By "learning about computers", they mean learning how to use a word processor, a spreadsheet, and maybe a database program. In fact, students often enter the course with the faulty assumption that learning some applications is what computer science is about. A related issue is that students expect to acquire some knowledge or skill that they view as directly "practical." This is a problem that an English professor teaching a course on Chaucer, for example, would not face.

A professor teaching an introductory course to such students is faced with some choices. Many faculty agree that some sort of breadth-first approach is appropriate for the course, but what material defines the breadth and how should that material be presented? One option, of course, is to give the students exactly what they want. At many institutions, the introductory non-majors course is either a computer literacy course, or a course on computer applications—word processing, spreadsheets, database programs, and more recently "using the web"—or some combination of the two with a sprinkling of computer terms and some instructions on some popular operating systems.

The approach described in this paper, by contrast, is to teach a real introductory course in computer science, covering some of the basic concepts of the discipline such as algorithmic thinking, programming, data abstraction, and also issues in operating systems, architecture, computer-human interaction, and computer networks. Most computer science faculty will agree that these are central topics in the science of computing, and in theory will approve of the breadth-first approach. But many wonder if such material is "practical" and whether it can be successfully taught at a non-major level to students with very different expectations. We believe that such a course is actually more useful to students in the long run. Although students may not realize it, they will benefit more by acquiring skills in abstract reasoning, algorithmic thinking, data and procedural abstraction, and Boolean logic.

In this paper, we present a syllabus and several ideas for an introductory course in computer science designed for non-majors. The goal was to present an enjoyable course that students saw as "practical" without sacrificing any of the real content of computer science. In particular, students completing the course will have seen a good introduction to algorithmic thinking, abstract reasoning, and data abstraction, and in the process will have acquired a basic knowledge of the structure, components, and working of a computer system. The course has proven highly successful as measured not only by student evaluations but also by having attracted several students to the computer science major. In particular, students have become enthusiastic about learning topics that computer scientists consider central to their discipline. An additional benefit of the approach outlined here is that it makes the course much more interesting to teach for a professor of computer science.

Below is a brief outline of the topics covered in the course. The course format is three lectures plus a 75-minute lab period per week.

Students are graded based on weekly homework assignments worth 35% of their final grade, two midterm exams each worth 15%, lab participation worth 10%, and a cumulative final exam worth 25%. Information on the course can be found at www.middlebury.edu/~briggs/Courses/CX103/ and cweb.middlebury.edu/s99/cx103a/. At the end of the semester, students evaluate the faculty and course via a written two page anonymous questionnaire. Among other things, students evaluate overall effectiveness of the instructors, usefulness of the class, fairness of grading, and their own effort including number of hours spent outside of class. The evaluation includes two summary numerical scores on a "poor" to "excellent" scales.

In the remainder of this section we will give an overview of the various parts of the class, with a brief summary of our goals and a few examples of topics. In the next section, we will give details on a few specific lectures that we have found successful.

In the first four weeks we focus on the concept of abstraction and on techniques for algorithmic problem solving. Abstraction is presented as a fundamental notion that arises everywhere, from driving a car, to using a computer, to designing solutions to problems. During this time we introduce networks and the Internet as well. This serves two purposes: in lecture we use the notions of the Internet, the web, HTML, etc., as examples of layers of abstraction; in lab we teach them HTML so they can create homepages to be maintained throughout the semester. Note that although students have access to WYSIWYG web authoring tools, we teach them HTML in order to show them at a more fundamental level how the web works. Another reason is our goal of introducing a "typesetting" or "description" language, which will later help introduce the idea of a programming language.

Following our discussion of networks and the Internet, we spend the next two weeks studying algorithmic problem solving. In class we present the notion of an algorithm and outline the techniques (e.g., sequencing, selection, iteration) for solving problems. A nice in-class exercise is to assign problems for groups of students to work on together in class for five minutes. The students are asked to describe a precise algorithm to solve a simple problem. Such problems might be of the form: Describe an algorithm for determining whether a positive integer is prime or not. After several groups of three present their solutions, we discuss together the relative merits of the proposed solutions, leading into our next topic of algorithm efficiency.

The central lecture topics during this unit are algorithms for searching and sorting. We present a number of different scenarios in which searching and sorting are required and then present algorithms in several different ways. For example, we have groups of volunteers come to the front and "act out" various sorting algorithms by instructing them how to sort themselves by height. We follow this up with demonstrations of Java applets illustrating the sorting algorithms, as well as presentations of pseudocode. The algorithms are reinforced in lab where we spend two consecutive lab meetings working with implementations of algorithms for linear search, binary search, insertion sort, selection sort, bubble sort, quick sort, and merge sort. The software accompanying our text includes a program illustrating the various sorting algorithms with scatter plots. Students learn how each algorithm works by working with the pseudocode and generating scatter plots such as the one below.

Figure 1: Selection sort scatter plot (from software accompanying [LW95]).

Our objectives during this unit of the course are to introduce students to algorithmic problem solving techniques and get them to think about the critical computer science issues of efficiency and robustness.

In the second part of the course, roughly weeks five through nine on our syllabus, we study computer hardware and software. Again, as a further example of abstraction and vehicle for developing problem solving skills, we introduce gates and logic circuits as the lowest level of a computer’s operation. Students learn to develop simple circuits such as the one below given a truth table.

Figure 2: Circuit diagram developed in lab (from software accompanying [LW95]).

In the following week we introduce the von Neumann architecture, and briefly touch on machine language and assembly language programming. Students experiment in lab with the fetch-decode-execute cycle, how registers work, and how instructions and data are stored in binary in memory. This gives us an opportunity to reflect on the layers of abstraction between the physical hardware at the gate level, and the high-level programs they see at the beginning of the course when we discuss algorithms. During this part of the course, we also cover the binary representation of integers and briefly discuss storage of other types of data.

For the next few weeks we return to higher-level topics such as operating systems and programming. Our approach to operating systems is to focus on the principles, functions, and goals of operating systems in general, rather than presenting the functionality and use of specific operating systems such as DOS, MacOS, etc. In lab, however, we take the opportunity to introduce the UNIX operating system and teach them some simple UNIX commands. All students at Middlebury have an account on the central UNIX cluster where they can mount a web page, read e-mail, and store files. Since most students in the class have limited computer backgrounds, almost none of them know even the basic navigational commands in UNIX and therefore are unable to take full advantage of their UNIX accounts. Students are usually quite appreciative of receiving this exposure to UNIX in the context of a week discussing operating systems. During this part of the course, most students are introduced to a command-line interface for the first time, which we contrast with the graphical user interfaces with which they are already familiar.

The last topic in the second part of the course is programming languages. We spend almost two weeks on higher-level languages and teaching some elementary programming. In lab, the students are given some simple Pascal programs to compile, run, and modify. These are often the Pascal equivalent of the machine language programs they experimented with a few weeks earlier, helping to emphasize the abstraction inherent in the hierarchy from low-level to high-level programming. We wrap up our treatment of programming by exposing them very briefly to several languages and programming paradigms: Pascal and C as examples of procedural languages, Java and Smalltalk as examples of object-oriented languages, Scheme as an example of a functional language, and Prolog as an example of a logic-oriented language. We emphasize that while these languages are all equivalent in terms of computational power and all are compiled to the same low-level machine code, various languages such as these have been developed to solve certain problems most effectively.

For the last three weeks of the course we address a number of issues relating to computers and society. These include, for example, how advances in technology have affected music, the arts, medicine, and business. As an example of how technology has changed music, in one lecture we bring in a MIDI keyboard and demonstrate MIDI composition and recording (for a detailed discussion of how the functioning of MIDI instruments and sequencing software can be incorporated into a computer science survey course, see [D97]). During this part of the course we bring in current interest articles from newspapers, magazines, or the web about issues such as privacy and security and encourage lively discussion of the topics in class.

We end the course with an overview of the field of computer science and a quick look at specific areas of interest such as artificial intelligence, robotics, computer vision, and computational geometry.

In lecture, we make an effort to draw connections between the material learned in class and real experiences of the students. Student participation and involvement in lecture is welcomed and encouraged by in-class discussion and occasionally having students break into small groups to solve problems or discuss issues. In this section we’ll comment on a few of the lectures that make our points in somewhat non-traditional ways.

One lecture that has proven, over several semesters, to be a student favorite is a lecture we use near the start of the semester. After introducing and defining the concepts of algorithms, computing, and information—and explaining how these three words are all closely related—we help students visualize both the basic concepts of information processing and also ideas of a Von Neumann architecture with an analogy to another kind of processing: a food processor. We call this the "milkshake lecture". A simple home blender is presented to the class. The blender itself (that is, the motor) is the processor. The blender container is the storage (memory) device that allows the blender to hold on to information while it is being processed. Of course it isn’t useful unless there are both input and output devices. We demonstrate the processing of a particular input and output by turning three big scoops of ice cream, two cups of milk, and some chocolate syrup into a milk shake. (Having a stack of small paper cups with which to share the shake adds to the popularity of the lecture.) Through a simple lecture and a very familiar analogy with simple props, students are introduced to some important concepts, and they are challenged to begin to think abstractly about the notion of data processing. Later in the semester when we introduce the basic components of a computer, we refer back to this analogy. We have found this visual picture of processing stays with students for a long time, and have met former students on campus who have asked if we still use milkshakes to explain the concept of processing.

Another set of lectures is drawn from the realm of music. In particular, we use digital sampling of music to introduce the notions of digital and analog data, and we compare the MIDI format with the standard CD format to discuss various forms of storing data, and the advantages and disadvantages of each. For more information on this particular topic, readers are referred to [D97]. A similar type of lecture that might introduce the transmission of bits (digital data) over an analog medium (wire) would be the use of a remote-control car, where the professor tries to communicate to the students a stream of bits, where a 1 is represented by the car moving at full speed, and a 0 by the car stopped. We have used this analogy in class and found that the analogy communicates our ideas well, but have as yet to bring in an actual remote control car. This idea could be extended to discuss why computers use binary rather than decimal or some other system: there are inherent problems in trying to distinguish between multiple voltage levels, as there would be to an observer who had to distinguish between ten different speeds as opposed to just start and stop.

In our section covering the structure and components of computers and computer architecture (weeks 5-6), we devote two lectures to binary arithmetic. At each step, we draw direct analogies between binary and base 10 representation of integers. Included is a description of twos-complement. One in-class exercise that has proven helpful (and fun) is teaching students to count to 31 (in binary) on one hand. In fact, this is how we introduce binary numbers. After explaining the system, we have races to see which students are the fastest at figuring out what certain patterns represent (decoding), and at hold up the correct fingers for a particular number (coding). Professors are warned, however, to avoid the number 4 (00100).

We assign weekly assignments throughout the course that are closely tied to the topic currently discussed, including, for example, algorithm design, circuit design, binary representation of data, scheduling issues in operating systems, and programming. In addition the students complete three assignments that grow out of their laboratory work. These include:

1. A personal web page in HTML with the minimal requirements of an image, at least one link, a list, and text in different fonts or colors.
2. A web page in HTML for a personal hobby or interest, with several links to outside sources.
3. A 10-15 page PowerPoint presentation on a topic in the area of computers and society. The presentation should directly address the question of how computers have made an impact on the area of that specific topic.

Some of the topics students have chosen include: how computers are being used in elementary and secondary education; how advances in technology affect the automotive industry; advances in medical technology; how computers are used in the sports of sailing, football, and others. An interesting problem we have experienced with this assignment is that students sometimes are so engrossed in their projects that they ignore our pleas for reasonably-sized projects and submit files that are several megabytes in size, quickly filling up the class quota on local servers.

We use a variety of media in teaching the class. Several lectures are presented using multimedia software (Microsoft PowerPoint). Others are presented (and later made available) as WWW documents. Not surprisingly, we make frequent use of computer software including language compilers, graphics design software, animation and rendering software, web browsers, and various Java applets. We also make use of various videos, for example demonstrations of computer animation techniques and clips of popular computer-animated movies or videos. And a considerable amount of material is presented traditionally using blackboard and overhead transparencies.

We recommend varied use of media, especially computer-based media, to help students experience first-hand one aspect of the impact of computing on society. Late in the semester, we raise the issue of the different types of media used and asked students to discuss pros and cons. When asked to explicitly analyze the form in which content is presented, many students proved very insightful into which media are actually effective at communicating, which are neutral, and which may even be detrimental and are used only because they are "new". A very small percentage of students (less than 2%, or about two students in three semesters) complained that the changes in media from day to day or even within the same class makes it more difficult for them to take notes. They argue that different lecture styles require different note-taking styles, which makes their job more difficult. We considered this an advantage as it requires even the note-taker to be more actively involved in class.

Judging from student feedback, both informal and in the form of student evaluations, students have enjoyed this course and have felt that they gained a good appreciation for the field of computer science. It is interesting to note that on several midterm evaluations done early in the semester, students wrote that they wanted more time spent on using computers rather than algorithm design and fundamentals. By the end-of-semester evaluations, these comments had disappeared. Some sample comments include:

We believe that students come to appreciate a fundamental introduction to how computers work which will continue to inform them as users of computers as technology continues to evolve.

[D97] Matthew Dickerson, "Music, MIDI, and the computer science survey course." The Journal of Computing in Small Colleges, Proceedings of the 2^nd Annual CCSC Northeast

[LW95] Kenneth Lambert and Thomas Whaley, An Invitation to Computer Science Laboratory Manual, West Publishing Company, 1995. Conference, 12:5 (1997) 57—70.

[SG95] G. Michael Schneider and Judith Gersting, An Invitation to Computer Science, West Publishing Company, 1995.