EECS 100 : Introduction to Computing Systems

From Bits and Gates to C and Beyond
(A First Course in Computer Science and Engineering)

A Rationale for this Text Book.(and EECS 100)

Preface  postscript  or  pdf 

Table of Contents  postscript  or  pdf 

 Chapter 1 Welcome Aboard : postscript  or  pdf  or  ASCII .

1 Welcome Aboard.
1.1 What we will try to do.
1.2 How will we get there.
1.3 A Computer System
1.4 Two Very Important Ideas.
1.5 Computers as Universal Computational Devices
1.6 How do we get the electrons to do the work?
1.6.1 The Statement of the Problem.
1.6.2 The Algorithm.
1.6.3 The Program.
1.6.4 The ISA.
1.6.5 The Microarchitecture.
1.6.6 The Logic Circuit.
1.6.7 The Devices.
1.6.8 Putting it together.
1.7 Exercises.

 Chapter 2 Bits, Data types, and Operations :  postscript  or  pdf  or  ASCII .

2 Bits, Data Types, and Operations.
2.1 Bits and Data Types.
2.1.1 The Bit as the Unit of Information.
2.1.2 Data types.
2.2 Integer Data Types.
2.2.1 Unsigned Integers.
2.2.2 Signed Integers.
2.3 2's Complement Integers.
2.4 Binary-Decimal Conversion.
2.4.1 Binary to Decimal Conversion.
2.4.2 Decimal to Binary Conversion.
2.5 Operations on bits -- Part I: Arithmetic.
2.5.1 Addition and Subtraction.
2.5.2 Sign-extension.
2.5.3 Overflow.
2.6 Operations on bits -- Part II: Logical operations.
2.6.1 The AND function.
2.6.2 The OR function.
2.6.3 The NOT function.
2.6.4 The Exclusive-OR function.
2.6.5 Examples.
2.7 Other representations.
2.7.1 Floating Point Data Type.
2.7.2 ASCII codes.
2.7.3 Hexadecimal notation.
2.8 Exercises.


 Chapter 3 Digital Logic Structures :  postscript  or  pdf  or  ASCII .

3 Digital Logic Structures.
3.1 The transistor
3.2 Logic Gates.
3.2.1 The NOT gate (or, inverter).
3.2.2 OR and NOR gates.
3.2.3 AND and NAND gates.
3.2.4 DeMorgan's Law.
3.2.5 Larger Gates.
3.3 Combinational logic structures.
3.3.1 DECODER
3.3.2 MUX
3.3.3 FULL ADDER circuit.
3.3.4 Logical Completeness.
3.4 Basic Storage Elements.
3.4.1 The R-S Latch.
3.4.2 The gated D latch.
3.4.3 A Register.
3.5 The Concept of Memory
3.5.1 Address Space.
3.5.2 Addressibility.
3.5.3 A 2^2 by 3 bit Memory.
3.6 The Data Path of the LC-2.
3.7 Exercises.


 Chapter 4 The Von Neumann Model :  postscript  or  pdf  or  ASCII .

4 The Von Neumann Model.
4.1 Basic Components.
4.1.1 Memory.
4.1.2 Processing Unit.
4.1.3 Input and Output.
4.1.4 Control Unit.
4.1.5 Summary: The LC-2 as an Example of the Von Neumann Model.
4.2 Instruction Processing.
4.2.1 The Instruction.
4.2.2 The Instruction Cycle.
4.2.3 Examples.
4.3 Changing the Sequence of Execution.
4.4 Stopping the computer.
4.5 Exercises.


 Chapter 5 The LC-2 :  postscript  or  pdf  or  ASCII .

5 The LC-2.
5.1 The ISA, Overview.
5.1.1 Memory Organization.
5.1.2 Registers.
5.1.3 The Instruction Set.
5.1.4 Opcodes.
5.1.5 Data Types.
5.1.6 Addressing Modes.
5.1.7 Condition Codes.
5.2 Operate instructions.
5.3 Data movement instructions.
5.3.1 Immediate mode.
5.3.2 Direct mode.
5.3.3 Indirect mode.
5.3.4 Base+offset mode.
5.3.5 An Example.
5.4 Control instructions.
5.4.1 Conditional Branches.
5.4.2 An Example.
5.4.3 Two Methods for Loop Control.
5.4.4 Example: Adding a Column of Numbers, Using a Sentinel.
5.4.5 The TRAP instruction.
5.5 Another Example: Counting Occurrences of a Character.
5.6 The Data Path Revisited.
5.6.1 Basic Components of the Data Path.
      The Global Bus.
      Memory.
      The ALU and the Register File.
      The PC and the PCMUX.
      The MARMUX.
5.6.2 The Instruction Cycle.
      FETCH.
      DECODE.
      EVALUATE ADDRESS.
      OPERAND FETCH.
      EXECUTE.
      STORE RESULT.
5.7 Exercises.


 Chapter 6 Programming :  postscript  or   pdf  or  ASCII .

6 Programming.
6.1 Problem Solving.
6.1.1 Systematic Decomposition.
6.1.2 The three constructs: Sequential, Conditional, Iterative.
6.1.3 LC-2 Control Instructions to Implement the Three Constructs.
6.1.4 The Character Count Example from Chapter 5, Revisited.
6.2 Debugging.
6.2.1 Debugging Operations.
      Set Values.
      Execute sequences.
      Display Values.
6.2.2 Example: Debugging a Program by Examining an Execution Trace.
6.3 Exercises.

 Chapter 7 Assembly Language :  postscript  or  pdf  or  ASCII .

7 Assembly Language.
7.1 Assembly Language Programming---Moving up a level.
7.2 An assembly language program
7.2.1 Instructions.
      Opcodes and Operands.
      Labels.
      Comments.
7.2.2 Pseudo-ops (assembler directives).
      .ORIG
      .END
      .BLKW
      .FILL
      .STRINGZ
7.2.3 Example: The Character Count Example of Section 5.5, Revisited.
7.3 The Assembly Process
7.3.1 Introduction.
7.3.2 A Two-Pass Process.
7.3.3 The first pass: Creating the Symbol Table.
7.3.4 The second pass: Generating the machine language program.
7.4 Beyond Assembly of a single assembly language program.
7.4.1 The Executable Image.
7.4.2 More than one object file.
7.5 Exercises.

 Chapter 8 I/O :  postscript  or  pdf  or  ASCII .

8 I/O.
8.1 I/O Basics.
8.1.1 Device Registers.
8.1.2 Memory-mapped I/O vs. Special Input/Output Instructions.
8.1.3 Asynchronous vs. synchronous.
8.1.4 Interrupt-driven vs. Polling.
8.2 Input from the Keyboard.
8.2.1 Basic Input Registers (the KBDR and the KBSR).
8.2.2 The Basic input service routine.
8.3 Output to the monitor.
8.3.1 Basic Output Registers (the CRTDR and the CRTSR).
8.3.2 The Basic output service routine.
8.3.3 Example: Keyboard Echo.
8.4 A more sophisticated input routine.
8.5 Interrupt driven I/O.
8.5.1 Element 1: The Interrupt Signal.
8.5.2 Element 2: The Test for Interrupts.
8.6 Exercises.


 Chapter 9 TRAP routines and Subroutines :  postscript  or  pdf  or  ASCII .

9 TRAP Routines and Subroutines.
9.1 LC-2 TRAP routines.
9.1.1 Introduction.
9.1.2 The TRAP mechanism.
9.1.3 The TRAP instruction.
9.1.4 The RET instruction.
9.1.5 An example.
9.1.6 TRAP routines for handling I/O.
9.1.7 TRAP routine for halting the computer.
9.1.8 Saving and Restoring Registers.
9.2 Subroutine calls/returns.
9.2.1 The JSR/RET mechanism.
9.2.2 The JSR and JSRR instructions.
      JSR (JMP)
      JSRR (JMPR)
9.2.3 An example.
9.2.4 Another subroutine: Writing a character string to the monitor.
9.2.5 Library Routines.
9.3 Exercises.

 Chapter 10 And, finally... :  postscript  or  pdf  or  ASCII .

10 And, finally...
10.1 The Stack -- A very important storage structure.
10.1.1 The Stack -- An abstract data type.
10.1.2 Two example implementations.
10.1.3 Implementation in Memory.
       Push.
       Pop.
       Underflow.
       Overflow.
10.1.4 The Complete Picture.
10.2 Arithmetic using a stack.
10.2.1 The Stack as temporary storage.
10.2.2 An example.
10.2.3 OpAdd, OpMult, and OpNeg.
       The OpAdd Algorithm.
       The OpMult Algorithm.
       The OpNeg Algorithm.
10.3 Data type conversion.
10.3.1 Example: The bogus program: 2+3=e.
10.3.2 ASCII to Binary.
10.3.3 Binary to ASCII.
10.4 Our final example: the Hand Calculator.

 Chapter 11 Introduction to Programming in C. :  postscript  or  pdf  or  ASCII .

11 Introduction to Programming in C.
11.1 Our Objective.
11.2 Motivation for a higher level.
11.2.1 Pitfalls of programming at the low levels.
11.2.2 Adding programming conveniences.
11.3 Translating higher level programs.
11.3.1 Interpretation.
11.3.2 Compilation.
11.3.3 Pros and Cons.
11.4 The C programming language.
11.4.1 The C compiler.
11.4.2 Using the C compiler.
11.5 A simple example.
11.5.1 Formatting.
11.5.2 Preprocessor commands.
11.5.3 Input and Output.
11.6 Exercises.


 Chapter 12 Variables and Operators :  postscript  or  pdf  or  ASCII .

12 Variables and operators.
12.1 Variables.
12.1.1 Three basic types: int, char, double.
12.1.2 Variable identifiers and declarations.
12.1.3 Scope: globals and locals.
12.1.4 Some examples.
12.1.5 Symbol table.
12.1.6 Allocating space for variables.
12.2 Operators.
12.2.1 A special operator: Assignment.
12.2.2 Arithmetic operators.
12.2.3 Bitwise operators.
12.2.4 Logical operators.
12.2.5 Relational operators.
12.2.6 C specialties.
12.2.7 Conditional expressions.
12.2.8 Evaluation rules and parentheses.
12.2.9 Type conversions.
12.3 A comprehensive example.
12.4 Exercises.


 Chapter 13 Control structures. :  postscript  or  pdf  or  ASCII .

13 Control structures.
13.1 Condition constructs.
13.1.1 The if statement.
13.1.2 The if-else statement.
13.1.3 The switch statement.
13.1.4 An example program.
13.2 Iteration constructs.
13.2.1 The for statement.
13.2.2 The while statement.
13.2.3 The do-while statement.
13.2.4 The break and continue statements.
13.3 C Syntax.
13.3.1 Declarations.
13.3.2 Statements.
13.4 Examples
13.4.1 Example 1 : finding prime numbers between 1 and 100.
13.4.2 Example 2 : detecting a sequence of text.
13.4.3 Example 2 : Approximating the value of pi.
13.5 Exercises.


 Chapter 14 Functions. :  postscript  or  pdf  or  ASCII .

14 Functions.
14.1 Introduction.
14.2 High-level programming structure.
14.3 Functions in C.
14.3.1 The declaration.
14.3.2 The call.
14.3.3 The definition.
14.3.4 The return value.
14.4 Another Examples
14.5 The Run-Time Stack.
14.5.1 The activation record.
14.5.2 Activation records during execution.
14.6 Implementing Functions in C.
14.6.1 The call.
14.6.2 Starting the called function.
14.6.3 Ending the called function.
14.6.4 Returning to the calling function.
14.6.5 Tying it all together.
14.7 A detailed example, with complete translation.
14.8 Exercises.


 Chapter 15 Debugging. :  postscript  or  pdf  or  ASCII .

15 Debugging.
15.1 Introduction.
15.2 Types of Errors.
15.2.1 Syntactic errors.
15.2.2 Semantic errors.
15.2.3 Algorithmic errors.
15.3 Debugging techniques.
15.3.1 Ad-hoc techniques.
15.3.2 The source-level debugger.
15.4 Exercises.


 Chapter 16 Recursion. :  postscript  or  pdf  or  ASCII .

16 Recursion.
16.1 Introduction.
16.2 A High-Level Example: binary search
16.3 Another High-Level Example: Towers of Hanoi
16.4 A Detailed Example in C
16.5 Another detailed example in C.
16.6 Exercises.


 Chapter 17 Pointers and Arrays.  :  postscript  or  pdf  or  ASCII .

17 Pointers and Arrays.
17.1 Introduction.
17.2 Pointers.
17.2.1 Declaring pointer variables.
17.2.2 Pointer operators.
17.2.3 A useful application of pointer variables.
17.2.4 More examples using pointer variables.
17.3 Arrays.
17.3.1 Declaring arrays and accessing elements.
17.3.2 An example program.
17.3.3 Arrays as parameters.
17.3.4 Strings in C.
17.3.5 The Relationship Between Arrays and Pointers.
17.3.6 More examples.
17.3.7 Common pitfalls with arrays in C.
17.4 Exercises.


 Chapter 18 I/O in C. :  postscript  or  pdf  or  ASCII .

18 I/O in C.
18.1 Introduction.
18.2 A Brief Note about the the C Standard Library.
18.3 I/O Basics.
18.4 The Mechanics of a printf Call.
18.5 The Mechanics of a scanf Call.
18.6 Conclusion.
18.7 Exercises.

 Chapter 19 Data Structures. :  postscript  or  pdf  or  ASCII .

19 Data Structures.
19.1 Introduction.
19.2 Structures.
19.2.1 The basics of structures in C.
19.2.2 Arrays and pointers with structures
19.3 A Foray into Dynamic Allocation
19.4 A Fundamental Data Structure: The Linked List.
19.4.1 What is a linked list?
19.4.2 An example using linked lists.
19.5 Exercises.

 Chapter 20 Analysis of Algorithms  :  postscript  or  pdf  or  ASCII .

20 Analysis of Algorithms
20.1 Introduction: Quantifying Growth.
20.2 Big-O notation.
20.3 Previous Examples Analyzed.
20.4 Algorithmic Complexity Versus Efficient Coding.
20.5 Recursion vs. Iteration

 Appendix A :  postscript  or  pdf  or  ASCII .

A The LC-2 ISA.
A.1 Overview.
A.2 Notation.
A.3 The Instruction Set.

 Appendix B From LC-2 to x86 : postscript  or  pdf 


 Appendix C The Microarchitecture of the LC-2 :  postscript  or  pdf 


 Appendix D :  postscript  or  pdf  or  ASCII .

D The C Programming Language
D.1 Overview.
D.2 C Conventions.
D.2.1 Source files
D.2.2 Header files
D.2.3 Comments
D.2.4 Constants
      Integer
      Floating point
      Character
      String constants
D.2.5 Formatting
D.2.6 Keywords
D.3 Indentifiers, Types and Declarations.
D.3.1 Indentifiers
D.3.2 Basic types
      integer
      float
      double
      char
D.3.3 Type qualifiers
      signed, unsigned
      long, short
      const
D.3.4 storage class
D.3.5 Derived types
      arrays
      pointers
D.3.6 structures
D.4 Declarations
D.4.1 variable declarations
D.4.2 function declarations
D.5 Operators.
D.5.1 assignment operator
D.5.2 arithmetic operators
D.5.3 bitwise operators
D.5.4 logical operators
D.5.5 relational operators
D.5.6 Special operators
D.5.7 conditional expression
D.5.8 Pointer, array, structure operators
D.5.9 Miscellaneous operators
D.5.10 precedence
D.6 Expressions and Statements.
D.6.1 expression
D.6.2 statements
D.7 Control flow.
D.7.1 if
D.7.2 if-else
D.7.3 switch
D.7.4 while
D.7.5 for
D.7.6 do-while
D.7.7 break
D.7.8 continue
D.7.9 return

E Extending C to C++.

 Appendix F :  postscript  or  pdf  or  ASCII .

F Useful Tables
F.1 Conversion Specifications for C I/O.
F.2 ASCII code table
F.3 Commonly Used Numerical Prefixes

To obtain EECS100 book chapters :
(The book chapters are not for students)

• Professor Yale Patt and Sanjay Patel are developing a textbook for EECS100. The current state of the manuscript is available to those interested in knowing more about the EECS 100 approach to introducing students to Computer Science and Computer Engineering. The authors are very much interested in feedback on both the approach and on the book.
  
  

• To obtain access, send email to swkpeter@eecs.umich.edu with the following information:
  
  1. Your name
  2. Job title, or other descriptor to help us identify you
  3. e-mail address
  4. Brief statement as to why you would like to see "From Bits and Gates to C and Beyond"
  
  Password access to the manuscript will be sent to you by return email.
  
  

• The copyright is currently owned by Professors Patt and Patel. Please do not distribute the manuscript without their permission.
  
  

• Students enrolled in EECS 100 may not access the manuscript via this mechanism. See your instructor for information about obtaining the EECS 100 Coursepack, which includes the latest version of the text.
  
  

The manuscript can be obtained in either postscript, pdf or ASCII format, and either in its complete current state or by individual chapters.

• To obtain the complete current state, access All (postscript) or All (pdf file) or All (ASCII) .
  
  

• To obtain an individual chapter, access the corresponding postscript, pdf or ascii link for that chapter (above).