D. J. Bernstein
Data structures and program structures
MCS 260, Spring 2001

What I did in class

20010108: Office hours, textbook. Assignment: read sections 1.1 through 1.11. Labs have moved to computer rooms. Lab rules. Unofficial prerequisite: have sent email using Pine from icarus. Official prerequisite: credit or registration in Math 180. Grading. References: Harbison and Steele; Plauger. A program is a sequence of instructions. Examples: sheet music; File click Open foo.doc OK File click Print OK; a COBOL program to print the date of Easter. Programming: writing (or ``building'') programs. Student goals: power; literacy; understanding. Sizes of some computer programs. Computers follow machine-language instructions. Machine language: very simple; very fast. How computers follow other instructions: compilers and interpreters. Picture of a compiler. Picture of an interpreter. UNIX commands to create, compile, and run a program.

20010110: What's the difference between using a computer and programming a computer? User: A B C D E Y A B C D E Z A B C D E. Programmer: program Q is A B C D E; Q Y Q Z Q. Desirable features of programs (* for features irrelevant to most programs): correct; easy to write; easy to read; easy to test; easy to debug; easy to modify; modular; *portable (works on many computers); *reliable (handles unusual input); *secure (handles malicious input); *fast. Magic incantations to be explained later:

     int main()
       return 0;
UNIX tip: uppercase and lowercase are different in filenames. Definitions of variables in easter.c. Memory picture. A variable is a collection of bytes in the computer's memory. A byte is, at each time, 0 or 1 or 2 or ... or 255. int year; defines a 4-byte variable. It also declares the variable: the program can use year later.

20010112: Assignment: read sections 1.12 and 14.7. How to start Exceed. Picture of memory changing over time. Instructions operate on memory. Memory picture after several int variable declarations. What

does to memory. More instructions. = to put a value into a variable. / to divide. Division of int throws away remainder. When in doubt, put in parentheses. * to multiply. Can't leave out the *. % for the remainder from division. An if with == and &&. -- to subtract 1 from a variable. -= to subtract anything. A variable name refers to the current value of the variable. A printf example. What debuggers do: step through your program, printing memory pictures.

20010115: No class.

20010117: UNIX tip: at the shell prompt, type ^W to erase a word. Notes on programming from home. UNIX tip: man gcc for the gcc section of the online manual. Assignment: read chapter 2. Basic types of symbols in C programs: preprocessor symbols; names (``identifiers''); numbers; strings; comments; miscellany. Examples of preprocessor symbols: #include lines; #define lines; etc. Don't add semicolons. Examples of names. Name is a letter or underscore, followed by any number of letters or underscores or digits. Warning about length limits. Uppercase letters are different from lowercase letters. Examples of numbers. Warning about 0 for base 8. Warning about 0x for base 16. Some floating-point numbers. Examples of quoted characters as numbers. Examples of quoted backslashed characters.

20010119: UNIX tip: creating shell scripts. Examples of strings. Backslash combinations in strings. String starts with double quote, continues until closing double quote. Backslashed quote does not stop a string. Splitting a string into two. Using backslashes to split a line into two. Warning about space after backslash. Warning about spaces on next line after backslash. Examples of comments. Comment starts with /*, continues until */.

20010122: UNIX tip: mv -i and mv. /* /* /* */ versus /*/*/**/. Use comments, indentation, and blank lines to help the reader. Example: consistent indentation inside main(){}; a ``Julian correction'' comment. Example: consistent indentation inside an if(){}; a ``should not happen'' comment. All the miscellaneous symbols; how to read them. A byte (``char'') variable. Characters are letters, symbols, etc. The characters 7, C, space, 3, D, newline are represented inside a computer as bytes 55, 67, 32, 51, 58, 10. What scanf("%c",...) does. What printf("%c",...) does. Example: program that reads and writes one character. What program does if user types 7, C, newline.

20010124: Assignment: read chapter 3. Warning about lab schedule. UNIX tip: rm -i and rm. An int variable. Possibilities for an int: -2147483648, -2147483647, ..., -2, -1, 0, 1, 2, ..., 2147483647. Portability warning: different compilers may have different int sizes. What printf("%d",...) does. What scanf("%d",...) does. Example: program that reads and writes one number in decimal. What program does if user types space, 3, 2, 1, space, 7, 3, newline. printf("Hello"), printf("%%"), printf("\n"). Combining multiple printf statements.

20010126: UNIX tip: cp -i and cp. Output buffering: printf saves results in a buffer. Situations where the buffer is flushed: end of program, print newline, scanf() on some systems, fflush(stdout). #include <stdio.h> before using stdout. Input buffering: user's line is not fed to scanf() until user presses return. Example of user editing a line. Using float variables. What can fit into a float variable. Using double variables. What can fit into a double variable. scanf("%f",...). printf("%f",...). scanf("%lf",...). printf("%lf",...). A few safe mixtures of printf() types. Example: program that reads an integer, writes the corresponding byte. Example: program that reads a real number and prints its cosine. Warning about -lm.

20010129: UNIX tip: ls, ls *.c, ls /bin. Control flow: if, while, do, etc. Example of a while(){} loop. The while() condition is not tested continuously; it is tested at the top of the loop. Example: i = 0; while (i < 10) { ++i; printf("%d\n",i); }. Memory pictures. After i reaches 10, it is printed, and then the condition is tested. Example of a do{}while() loop. Equivalence of while() with if()do{}while(). Ways to leave a loop: break; goto; setjmp/longjmp; return. Try to avoid goto, setjmp, longjmp.

20010131: UNIX tip: lpr. goto. Rephrashing while(){} in terms of goto. Rephrashing do(){} in terms of goto. The break and continue statements. for(){} loops. Rephrashing for(){} in terms of goto. An almost equivalent while(){} loop; what happens with continue. An equivalent while(){} loop. break looks for nearest while, do, for, switch; continue looks for nearest while, do, for.

20010202: UNIX tip: < infile > outfile. Examples of switch(){}. Using break inside switch(){}. Examples of control flow.

20010205: UNIX tip: pipelines. More examples of control flow; using scanf() as a number. Functions with no parameters returning void.

20010207: UNIX tip: gzip foo; gunzip foo; quota -v. Functions with parameters returning void. Arguments are copied to parameters. The return statement.

20010209: UNIX tip: echo. Functions with parameters returning int.

20010212: UNIX tip: tail -5. printf("%d\n",scanf(...)). Equivalent: r = scanf(...); printf("%d\n",r). Picture of the scanf data flow. Side effects: anything produced by a function other than its return value. Differences between mathematical functions and C functions. Sample midterm problem: write a program that reads a sequence of integers and prints the last 5 integers. Building the solution.

20010214: UNIX tip: head -5. Midterm review.

20010216: Midterm review.

20010219: Midterm #1.

20010221: Comments on midterm.

20010223: Comments on midterm.

20010226: Comments on midterm.

20010228: Comments on midterm.

20010302: UNIX tip: grep. Final comments on midterm. When arrays are useful. Example: program to read 3 integers, print them in opposite order. Same program with an array of 3 integers. Same program with variable array indexing. What variable array indexing means.

20010305: UNIX tip: review of shell scripts; $1 and $2 in shell scripts. Recap of arrays. Terminology: elements, array of floats. Security warning: running off the end of an array might cause program to change or remove files, make network connections, etc.; attacker who can provide input may be able to take control of the program; simplified memory picture; range checking. Program to compute and print the first 10 powers of 2. Memory pictures.

20010307: UNIX tip: while ... do ... done in shell scripts. Partially filled arrays.

20010309: UNIX tip: if ... then ... else ... fi in shell scripts. Partially filled arrays of char.

20010312: No class.

20010314: No class.

20010316: No class.

20010319: UNIX tip: for i in ... do ... done in shell scripts. Two-dimensional arrays. A program to read and print 10 lines.

20010321: Midterm review.

20010323: Midterm #2.

20010326: Comments on midterm.

20010328: Comments on midterm.

20010330: Comments on midterm.

20010402: UNIX tip: the directory hierarchy; the current working directory; cd. Example of function to print a fixed-length array. Example of function to add the elements of a fixed-length array. Example of function to read numbers into a fixed-length array. Arrays are effectively copied out of function upon return; actually, array parameter overlaps array argument. Memory pictures.

20010404: UNIX tip: mkdir; rmdir. int sum5(int x[5]) same as int sum5(int x[]). Can pass array of any length as argument, if array elements have the proper type. void printarray(int x[],int xlen). int sumarray(int x[],int xlen). void readarray(int x[],int xlen). Reminder that array parameter overlaps array argument. Memory pictures for readarray(u,3); readarray(v,5).

20010406: An extended example of a program passing a partially filled array to functions: main() calling pfa_read(), pfa_print(), pfa_sum().

20010409: Grading scale for course. Picture of main() above pfa_read() etc.; high level, low level. Picture of communication between main() and pfa_read(). An extended example of a program with several functions manipulating a partially filled array defined outside the functions: main() calling x_read(), x_print(), x_sum(). Basic advantage of variables outside functions: easy to use; no need to define parameters. Basic advantage of arguments and parameters: can use the function for any array of the right type.

20010411: UNIX tip: while read line in shell scripts. ``Global variables'' are variables defined outside functions: visible to all subsequent functions. ``Local variables'' are parameters and other variables defined inside a function: visible only to that function. Variable name refers to a global variable or a local variable in the same function. Local variable q in function f is unrelated to local variable q in function g. Advantage of global variables: can collect all important variables at the top of the program. Advantage of local variables: can easily see all variables used by a function. Advantage of global variables: can recognize any use of a variable. Advantage of local variables: other functions cannot change variables without permission. Example of an unexpected change to a global variable. Examples of expressions, non-expressions. Each expression has a type: e.g., void, int, float. Each non-void expression has a value. Each expression has a sequence of side effects, maybe none. Variable names as expressions: type is type of variable; value is current contents of variable; no side effects (except for volatile variables).

20010413: Expressions of the form p+q: possible types, value, side effects. Warning that side effects of p may occur before, after, or interleaved with side effects of q. Example of incorrect code: inc() + dbl() affecting the same variable. Recap: how to evaluate p+q; similarly p-q, p*q, etc. Expressions of the form v=q: type, value, side effects. Example: m=n=0. Warning that side effects of q may occur before, after, or interleaved with change of v. Example: m=n++. Example of incorrect code: n=n++. Similarly v+=q, v-=q, v*=q, etc.; ++v same as v+=1; --v same as v-=1. Example: m=++n.

20010416: Expressions of the form v++: type, value, side effects. Example: j++ + ++k. Similarly v--. Mnemonic to remember v++ and ++v. Expressions of the form x[p]=q, x[p], x[p]+=q. Example: x[i++]=j; common for partially filled arrays. Example: x[++i]=j. Expressions of the form p?q:r. Examples.

20010418: Expressions of the form p&&q. Expressions of the form p||q. Expressions of the form p,q.

20010420: Expressions of the form f(p,q). Casts. Expressions of the form sizeof p. Examples of statements.

20010423: Every statement has a sequence of effects. Statements of the form p;. Examples. Block statements: {s t u} etc. Examples. Defining variables in a statement. Examples of initializers. Examples of array initializers. Statements of the form while(p)s. Example: while(n--) { printf("%d\n",x[n]); } Example: while(n) { --n; printf("%d\n",x[n]); } Similarly for if(p)s etc.

20010425: putchar(). What getchar() does: sample code. Typical use: int c; while ((c = getchar()) != EOF) { ... } What goes wrong with char c. What tolower() does: sample code. What toupper() does. What islower() does: sample code. What isupper() does. Review.

20010427: Review.