The course covers three major topics: computer organization and architecture, programming in C, and algorithm analysis. The major thrust of the course is to first give the student a fundamental understanding of how a computer works, and then tie high level constructs (control structures, functions, arrays and structures, pointers, etc.) to that fundamental understanding. In point of fact, each time a C construct is introduced, the student sees what a compiler would generate in terms of machine code to carry out this task. Thus the student sees how activation records are generated at run time, as well as how physical I/O is handled through device registers by the operating system.
1.A. Some non-technical information about the course. EECS 100 is a prerequisite for EECS 270, Digital Logic Design, and for EECS 280, Programming and Data Structures. [The University of Michigan numbering system uses the first digit of a course number to indicate the year in which a course is expected to be taken -- 1:freshman, 2: sophomore, etc.] The course was offered for the first time this past academic year to 130 students (Fall term) and 170 students (Winter term). [Winter term at the University of Michigan is equivalent to what most universities call their Spring semester.]
The course consists of 41 50-minute lectures, meeting three times a week for lecture and once a week for a discussion session with a graduate student TA. The course was team taught this first year by Professor Kevin Compton and me. We are both regular members of the EECS faculty. Professor Compton's specialty is algorithms and compiler technology; my work is in computer architecture and high performance implementation.
Students were required to write six programs (one in LC-2 machine language, two in LC-2 Assembler, and three in C) and complete several problem sets. There were two one-hour exams and a final in the course.
1.B. A more detailed description of the course. The first lecture introduces computing from a number of perspectives: from the standpoint of what is computable (Turing machines, etc.), as well as from the standpoint of multiple levels of transformation that are required to convert a problem from a natural language description to the electronic devices that actually carry out the task,
From there, we go on to explain that information is carried along wires in the form of the absence or presence of voltages (0 or 1), and introduce various codes for representing information. We explain the difference between ASCII codes for representing characters and 2's complement integers to represent signed numbers. We show both logical and arithmetic operations on this information. Next, we describe both P-type and N-type CMOS transistors, and construct inverters, logic gates, latches, muxes, decoders, and finally a small unit of random access memory consisting of four locations of three bits each. Our observation is that this introduction to memory clears the mystery of "what is memory," resulting in far fewer student problems when pointers are introduced later in the course.
From there, we introduce the Von Neumann execution model, followed quickly by an introduction to the LC-2 [for Little Computer 2], the next generation of the LC-1 which I have successfully used in junior level computer organization courses for about 15 years. The LC-2 is a 16 bit machine; its ISA is Load/Store, with 8 general purpose registers. Opcodes are 4 bits wide, and include LD/ST using direct, indirect, and base-offset addressing, operates (ADD, AND, and NOT), procedure call/return, and conditional branches on N, Z, and not-Z condition codes. I/O is handled by the TRAP instruction which vectors the processor to one of two operating system routines which does physical I/O from a keyboard data register or to a monitor data register. Keyboard and monitor status registers support the I/O activity.
Students first program the LC-2 in machine language, and then move on to LC-2 assembler. Students hand-assemble their first assembly language program, creating the symbol table, and producing an object file. Students learn about global variables and linking to library routines in creating an executable image. Subsequent programs written in LC-2 assembly language are assembled by our LC-2 Assembler.
We have created a simulator of the LC-2 that takes as input a machine language version or an LC-2 Assembler version of a program, and executes it. The simulator contains mechanisms for single stepping (if desired), setting breakpoints, depositing and examining values in registers and memory, etc.
Once the student is solid on the intracies of the LC-2, we introduce a high level language. This first year, we used C, but are considering moving to C++ in the fall. [The reader's opinions on this matter are hereby solicited.] In our treatment of C, we cover the usual constructs in a serious introductory course in high level language programming, as well as some of the stuff that beginning students never get to see, like activation records and the run-time stack. The main topics we cover in this part of the course include: variables and activation records, control, functions, basic input/output, the run time stack, recursion, arrays, structures, pointers, and basic file i/o.
We have found that the pace can be accelerated and additional insights can be provided specifically because the student has a foundation in the underlying structure of the computer. Explanations of C constructs in terms of these underlying structures solidifies the knowledge faster than we have found to be the case when the student does not have this foundation.
The final block of material of the course teaches some elementary analysis of algorithms. The student is introduced to big-O notation, and is shown how various algorithms grow. For example, since the student has been exposed to recursion, he/she can understand the differences in growth between generating the Fibonacci sequence recursively and doing so iteratively.
1.C. More observations. Almost all the feedback we have received has been very supportive. Students enjoy the course enormously, -- we think because they are given a comprehensive understanding of what is going on, rather than having to learn rules that make no sense to them.
Constructs that have proven difficult for students to master in the past do not seem to offer the same challenge in this course. Pointer variables are a piece of cake after analyzing the design of a four by 3-bit memory earlier in the course. Recursion is no longer magic after understanding activation records, and in particular the linkage between a calling function and the function it calls. Once the student sees how function A calls function B, it is a very small step to function A calling itself.
We attempt to start with notions that are concrete, and then work up to greater levels of abstraction, always attempting to remove "magic" from how things work.
I think the bottom line is that this approach works because it does what education in science is good at, building knowledge from the bottom up. Each time the student is presented with something new, he/she has a foundation on which to pin the concepts, so it becomes part of a coherent fabric, rather than one more isolated entity.
I hear that assembly language programming is obsolete, since we don't program in assembly language anymore. But assembly language programming was never (or not for the past 20 years anyway) taught in order to train assembly language programmers. If it were, it would have been an advanced course, not an elementary course. Assembly language programming was in the curriculum to give students a more fundamental understanding of how computers work and how data structures are actually represented. The upside is that with this knowledge, one has a better chance of being able to seriously analyze an algorithm that has to execute on real hardware.
I also hear that calculus (or any other math, for that matter) is not worth the time it takes up in the curriculum. "Students have different learning styles, and we should not saddle them by requiring them to suffer through math courses." Also, "Just get on the WEB and boogie." The last statement from a senior faculty member at one of our "top ten" universities, who advocates this with total sincerity.
I think we are turning out a lot of students who know a lot "about computers," but can't synthesize anything with this knowledge. Many can't write a program or design a logic circuit that works, on their own. Programs don't get written and circuits don't get designed by magic. Networks are just so much more magic if one does not have a solid grasp of how operating systems work. I suggest that an important part of this problem is that we don't insist on mastery of fundamentals, preferring instead to concentrate on exposing students to a whole lot of the "good" stuff.
One of the position statements written for this workshop argues that our discipline is about algorithms. If it is, then it requires fundamental understanding of computer organization, data structures, and problem solving/programming before we get to the algorithm, and then solid mathematics coupled with all of the above before we can analyze how good that algorithm is.
Whether or not the typical graduate ever writes an assembly language program, designs a microprocessor, or writes a compiler or operating system, I believe that an understanding of those topics is fundamental to his/her strong foundation in our discipline.
I appreciate that distributed computing, other network issues, and multimedia are all important to current applications of computers. But I would prefer we not make it harder for our students to do solid work in those areas by not first providing them with the underpinnings captured by the fundamentals.