NOTE: On 4/18 I added ten new lines, each of which is marked with the word ``NEW'' at the right.

The final examination will cover the following parts of your textbook ("Problem Solving in C Including Breadth and Laboratories" by Angela Shiflet, West Publishing Co., NY, 1995):

Chapters 1--5, 6.1--6.2, 7, 8, 9.1--9.5, 10, 11.1, 11.2, 11.4, 12.1, 12.2, 12.7, and 16.1.

The final will cover graphics as well, but only as presented in lecture, not as presented in 11.7.

No books, papers, or other materials and NO CALCULATORS can be used.

This outline includes all the basic concepts on which you might be tested. Some detail for which you are responsible is omitted.

I. Basic Definitions

A. Algorithm
B. Computer
C. Program (also "code" means "program" or part of a program)
D. Programming Language

II. Computer System


A. Hardware + Software = Computer System
B. Hardware Components

1. Input unit (keyboard, for example)
2. Output unit (monitor screen, for example)
3. Secondary storage: slow, large, non-volatile
4. Central processing unit (CPU) (Intel's Pentium, for example)

a. Control unit
b. Arithmetic/logic unit (ALU),
c. Register(s): Program Counter, Instruction Register, Accumlator, and (usually) others.
d. The fetch-execute cycle
5. Main memory, or primary storage: fast, small, volatile
C. Operation of the "von-Neumann" architecture (a PC, for example)

1. Stored-program concept (instructions stored like data)
2. CPU cycle: fetch, decode, execute
3. Main memory organization: addresses, cells, bits, bytes

III. Computer Languages


A. Syntax
B. Machine language

1. Machine dependent (i.e., different for each computer)
2. Not easily read by humans (nothing but ones and zeros!)
3. Instruction = operation code (Opcode) and operand(s)

C. Assembly language

1. Machine dependent
2. Mnemonic words and numbers in place of ones and zeros
3. One statement translates into typically one machine instruction.

D. High-level language (C, for example)

1. Machine independent (the same for many computers)
2. Human readable (if you call C "readable"!)
3. Program is called ``source'' code.
4. Translated to machine language

a. Preprocessor and compiler
b. Identifiers instead of memory addresses
c. One statement translates into typically many machine instructions.
d. Separate compilation (with preprocessing) of source files.
e. Compiler's output is called ``Object'' code.

5. Linker combines object code from separate compilations.

a. Libraries of object files (functions provided with language)
b. Object files from user-written source files
c. Linker's output is almost* executable code.
[*``Loader'' converts linker's output into fully executable code.]

IV. Solving problems on the computer


A. Four steps to a solution

1. Analyze (order of a., b., and c. will vary):

a. Describe input
b. Describe process
c. Describe output

2. Design (order of a., b., and c. will vary):

a. Draw structure chart
b. Choose data structures
c. Write algorithms in pseudocode
3. Implement: Edit---->Translate to Machine Code---->Run
^ | |
| (Compile-time error) |
| | (Run-time error)
|-----<----<-------' |
| |

`-----<----<-----Trace-----<----<------'
4. Test: Choose input---->Run---->Examine Output
^ |
`------<----<----<--------'

B. Modular programming

1. One function for each block in the structure chart
2. Precondition, Postcondition, and Algorithm for each function

C. Top-down design, or Step-wise Refinement

1. First "solve" the big problem, then solve the subproblems
2. Implement with stubs


V. Encoding of numbers in the computer


A. Integers

1. Binary encoding

a. Converting to and from decimal notation
b. Addition

2. Two's complement notation

a. Converting to and from decimal notation
b. Changing the sign
c. Addition (same as for binary encoding!)
d. Checking for overflow after addition

3. Excess notation: converting to and from decimal notation

B. Binary fractions: converting to and from decimal notation
C. Floating point notation

1. Three parts: sign, exponent, mantissa
2. Exponent uses excess notation.
3. Mantissa uses normalized notation.


VI. Structured Programming


A. The flow of control should be easy to visualize from the code.
B. Use only these four control structures:

1. Modular (C provides function )
2. Sequential (i.e., control order is the same as code order.)
3. Selection (C provides if, if-else, and switch.)
4. Looping, or iteration (C provides while, do-while, and for.)


VII. Logical Expressions


A. Truth tables
B. Equivalence of expressions (i.e., by using a truth table)


VIII. C language


A. We use the ANSI standard.
B. Layout

1. Free-format
2. Comments---ANSI style: /*...*/ and C++ style: //...<end-of-line>

C. Preprocessor

1. Example: #include <foo.h> // copies the file foo.h
2. Example: #define FOO x+y // replaces FOO with x+y (everywhere)
NEW --- 3. Example: #define NEG(a) (-(a)) // replaces NEG(x) with (-(x))

D. Legal identifiers
E. Variable declaration statements

1. Examples: int x; int x,y; long int x1; float x; double foo;
2. Initialization examples: int x = -14; float y = 24.5;

F. Types

1. Primitive (provided with the language)

a. Integer types: int, long int, unsigned int, unsigned long int
b. Floating point types: float, double

2. Derived (combinations of primitive types)

a. Arrays (see below)
b. Pointers (see below)
c. Structures (see below)

G. Functions

1. Function call
2. Argument, or actual parameter (used in the call)
3. Prototype
4. Function definition

a. Header
b. Body

5. Formal parameter (used in the header)
6. Call by value (argument's value is copied to formal parameter)
7. The return statement
8. The first function to be executed is main().

H. Scope

1. The range of statements over which a variable has meaning
2. Globle vs. local scope

I. Library functions

1. Input/output

a. #include <stdio.h>
b. printf() and scanf()
d. Conversion codes: %d, %nd, %-nd, %n.mf and %-n.mf (only)

2. Math

a. #include <math.h>
b. All arguments and returned values are of type double
c. pow(), sqrt(), ceil(), floor()

J. Expressions

1. Operators operate on operands (Is that pretty clear?)
2. Unary operator (one operand), binary operator (two)>
3. Order determined by operator precedence (table will be provided)
4. The operator "returns" the value of its operation.

K. Specific operators

1. The address-of operator, &
2. The assignment operator, =

a. Left operand must be a variable, or "lvalue"
b. Right expression, or "rvalue", is evaluated first
c. Value of expression is copied into variable on left
d. Value is returned (this is surprising)

3. Arithmetic operators

a. Unary + and -
b. Binary +, -, * take both integer and floating point perands
c. Integer arithmetic (no fractional parts)

(1) Used only when both operands are integers
(2) % and integer-divide (/)

e. Floating point arithmetic uses approximations

4. Conversion (from one type to another), or "coercion"

a. Implicit (int to float when one binary operand is a float)
b. Explicit, or "cast"

5. Updating assignment operators

a. +=, -=, *=, /=
b. ++, --: prefix and postfix

6. Logic
a. True is nonzero. False is zero.
b. Relational operators: <, >, <=, >=, ==, !=
c. Logical operators: !, &&, ||

7. Sizeof operator
8. The conditional operator (ie., op1 ? op2 : op3)
9. Pointer and structure operators (see below)

L. Selection statements:

1. if, if-else, switch
2. Nesting rules for if and if-else

M. Looping, or iteration, statements: while, do-while, for
N. Compound statements (i.e., {...;...;...}) are used in L. and M.
O. Characters

1. Characters are stored as numbers
2. ASCII
3. Character functions: putchar(), getchar(), tolower(), toupper(), isspace()

P. Arrays (1-d and 2-d only)

1. Contiguous sequences of items of the same type
2. Declaring and referencing

a. Syntax
b. Initialization at declaration: e.g., int x[][] = {{1,2},{3,4}};
c. Index starts with zero.
d. Calculating the address of an element

NEW---3. Strings

NEW---a. A string is a 1-d array of char containing a null character.
NEW---b. String length equals the index of the first null.
NEW---c. String functions: strlen(), strcmp(), strstr().

Q. Pointers

1. A pointer is an address
2. ``Dereferencing operator'' (*)
NEW---3. Call by reference

NEW---a. Parameter is the address of a variable.
NEW---b. Dereferencing operator is used in body of function.
NEW---c. Called function can alter variable in calling function.
4. Relationship to arrays

a. Name of array is a pointer to its first element.
b. *(x +i) is equivalent to x[i].
c. x + i is equivalent to &x[i].
d. Passing an array to a function means passing address.

(1) Syntax of prototype and of header
(2) Function can modify caller's array.

R. Dynamic memory allocation

1. p = malloc(num_bytes);
2. NULL is the address of "nowhere"

S. Structures

1. Declaring and referencing

a. Keyword "struct" plus tag
b. Members

2. Operations on structures

a. Structure member operator (.), e.g., s.foo
b. Assignment (entire structure is copied---unlike array!)
c. Passing to and returning from functions
d. Pointer operator: p->foo equals (*p).foo

T. Defining types with typedef (inventing synonyms)


IX. Searching and Sorting


A. Searching an unordered array with a sequential search
B. Searching an ordered array

1. Sequential search
2. Binary search

C. Sorting by selection sort


X. Graphics


A. Input is description, output is picture
B. Vector vs. Raster
C. Pixel is smallest controllable element in raster
D. Pseudocolor vs. true color
E. Color map


XI. Linked lists


A. Linked list is a chain of ``nodes''.
B. A node contains two parts:

1. An ``item'' (could be a number, a letter, a string, etc.)
2. A pointer

C. The pointer is the address of the next node.
D. The last node's pointer points to nil (meaning nothing).
NEW---E. The first node is called the ``head'', the last is the ``tail''.
F. Implementation in C

1. Nodes are declared to have the type of a two-member struct.
2. The first member of the type represents the item (any type).
3. The second member is a pointer to the same type as the node.
4. The "nil" address is NULL.


XII. Graphs


A. A set of "vertices" (e.g., nodes) connected by "edges" (e.g., pointers).
B. A vertex may be connected to more than one other vertex.
C. Any vertex may be connected to any other!
D. Examples:

1. "cycle" (e.g., token-ring computer network)
2. "tree" (e.g., DOS/UNIX directories)
3. arbitrary (e.g., World Wide Web)