D. J. Bernstein
Data structures and program structures
MCS 275, Fall 1997

What I did in class

19970825: [Course announcement handout.] Summary of course topics: more about the C language; C library functions; programming tools. Summary of student goals: power; literacy; understanding. Advanced topics: code portability; code efficiency; code reliability; code security. Overview of monitoring tools: execution trace tools, interactive debuggers, profilers. Example of using gdb. Informal homework assignment: find most recent C program and run it under gdb.

19970827: [Syllabus handout.] The memory picture. How variables are stored in memory. How variable assignment affects the memory picture. Finding location of a variable (``dereferencing''). Finding (unnamed) variable at a location (``referencing''). Defining location variables (``pointer variables''). Example of call-by-value: bad swap routine. Example of call-by-reference: working swap routine. Analysis of working swap routine. General procedure to convert call-by-value to call-by-reference.

19970829: [First homework assignment. Announcement that lab has moved to 2249F SEL.] Using call-by-reference for return values. Example: division with remainder. Comments on the 0 pointer. When arrays are useful. Defining array variables. Accessing array elements. Common idiom for partially filled array. Example of filling in array.

19970901: No class.

19970903: [Quiz on pointers.] Example of copying array. Example of copying array in reverse order. Initializing arrays. Portability of initializing arrays inside functions. Initializing character arrays. Using double quotes for character array initializations. Initializations without explicit array sizes. Using sizeof to find number of elements of character array.

19970905: [Last day to drop course.] Initializations with zero filled in. Warning that uninitialized arrays are not necessarily filled in. Using sizeof to find number of elements of any array. The value of an array as a pointer. Examples of pointer arithmetic. Example of sum() function using pointer arithmetic.

19970908: Pointer arithmetic generally. The meaning of pointer + integer. The meaning of pointer - integer. The meaning of pointer - pointer. Examples. Analysis of the sum() function. Fake array notation in function parameters. Fake array notation for accessing pointers. Consistency of fake array notation with real array notation. Warning that array arguments are not copied. Multidimensional arrays. Example of 2x2 arrays. Example of a function for adding 2x2 arrays.

19970910: When structs are useful. Creating struct types. Defining struct variables. Accessing struct components. Differences between struct and array: one struct can have more than one component type; struct variables are first-class; arrays can be of any length. Example of struct date. Example of struct exactdate. Union variables. Initializing struct variables. Warnings about struct initialization.

19970912: [Quiz on passing arrays to functions.] Memory picture for struct copying. The div() function. The arrow notation. Struct comparison not permitted. The concept of an object. Goals of linked lists.

19970915: General idea of linear lists. Operations on linear lists. Easy operations on arrays. Hard operations on arrays. Easy operations on linked lists. Hard operations on linked lists. Three forms of linked lists. Example of linked list in first form: two arrays. Code for printing linked list. More examples of linked lists. Deleting an element from a linked list: before and after.

19970917: Code for deleting element from linked list. Code for inserting element into linked list. Examples. Typical initialization of linked list. Example of linked list in second form: array of structures. Definitions of variables for linked list. Examples of expressions involving example.

19970919: [Second homework assignment.] Code for printing linked list. Example. Code for deleting from linked list. Example. Third form of linked list: dynamic linked list. Goal of dynamic linked list. Relation between dynamic linked list and array of structures. Example of using malloc() for integers. Portability notes about malloc() type. Calling malloc() more than once. Reliability notes on free(). Example of using malloc() for intlist. Checking whether malloc() failed.

19970922: More intlist allocation examples. General code for inserting element into dynamic linked list. Example. Code for printing dynamic linked list. Example. Examples of using struct for first-class arrays. Introduction to managing large projects.

19970924: Example of recording foo.c->foo in Makefile. Warning about use of tabs in Makefile. Example of recording foo.c,bar.c->foo in Makefile. Warning about completely blank lines in Makefile. Examples of using .o files. General form of Makefile rules. Dependency checking, part 1: make skips commands for targets newer than all dependencies. Dependency checking, part 2: make creates dependencies before creating target. Examples of dependency checking. Comments on missing dependencies. Example of CC macro in Makefile.

19970926: [Quiz on punctuation.] Problem in splitting up program into separate files: have to add declarations. General concept of declarations. General concept of definitions. Example of files with extern declaration. General rule: exactly one definition, any number of extern declarations. Portability notes on multiple definitions. General concept of scope. Examples of scope. Function declarations. Example of many declarations: main.c, kill.c, stdio.c.

19970929: Difficulty of maintaining code with many declarations. #include. #include for system files. Using #include to keep declarations in one file; the .h convention. Example of static variables. Meaning of static. Example of many separate static variables in different files under same name. Using static for functions. Example. Convention of using static whenever possible. 0 initialization. 0 initialization for static variables. 0 initialization for extern variables. 0 initialization for auto variables. Static variables inside functions.

19971001: [Review for first midterm.]

19971003: [First midterm.]

19971006: General concept of strings. The C string convention: string stored in byte array terminated by 0. Inability to use 0 inside strings. Octal names for bytes 0-255. Printable names for bytes 32-126. Backslash names for special bytes. Initializing a byte array with separate characters. Initializing a byte array with characters inside double quotes. String constant: pointer to first element of byte array initialized by compiler. Examples. Portability warning: string constants may be unwritable.

19971008: [Comments on first midterm.]

19971010: [Third homework assignment.] Printing strings. Finding the length of a string. Using pointers instead of array indices. Comparing strings. Checking string prefix. Checking string suffix.

19971013: Defining main() parameters. How the system calls main() with command-line arguments. Using main() parameters. Using getchar(). EOF from getchar(). Warning about getchar() return value. Reading characters into an array. Reliability warning: files can legitimately contain 0. Using malloc() to make space for a string.

19971015: Memory picture for command-line arguments. List of string.h functions on one system. What strlen does. What strcmp does. What strcpy does. Requirement that strcpy destination have enough space. Security warning about strcpy buffer overflows. Code for strdup.

19971017: What strcat does. Code for strcat. Code for strcpy. Memory picture for strcpy and strcat. Requirement that strcat destination have enough space. Example of sorting a two-dimensional array of strings. Example of sorting strings in command-line arguments.

19971020: Overview of the standard I/O library: formatted I/O and file I/O. The concept of a file: any device that reads or writes a stream of characters. The concept of a randomly accessible file. Conventional use of stdin, stdout, stderr. How the basic UNIX redirection symbols affect stdin and stdout. How to print an error message on stderr. The concept of opening a file. Input buffers.

19971022: [Review for second midterm.]

19971024: [Second midterm.]

19971027: Examples of printf. What goes after %: flags, width, precision, size, conversion. Flag - for left justification instead of right justification. Flag 0 for 0-filled justification instead of space justification. Flag + to print + for positive numbers. Minimum width. Variable minimum width. Precision. Variable precision. Size l for long. List of conversions. Integer conversions: %d, %ld, %o, %lo, %x, %lx, %u, %lu.

19971029: [Comments on second midterm.] String and character conversions: %s and %c. Floating-point conversions: %e, %f, %g.

19971031: [Fourth homework assignment.] More printf conversions: %p, %n, %%. Examples of scanf. What goes after %: flags, width, size, conversion. Flag * for discarding result. Maximum width. List of conversions. Miscellaneous conversions: %p, %n, %%. Integer conversions: %d, %o, %x, %u. Floating-point conversions: %e, %f, %g. String conversions: %c, %s, %[.

19971103: What scanf returns. How whitespace interacts with scanf maximum width. Importance of proper size for scanf. Overview of reading and writing files on disk. Example of program to read integers from a file on disk. Modes for fopen. Truncate versus append. Portability warning: text files are different from binary files in DOS. When fclose is necessary.

19971105: Example of writing files. Using perror to print reason for fopen failure. Using strerror. Using feof and ferror to determine reason for EOF. Using ftell. Examples of ftell. Using fseek. Examples of fseek. Portability comments on fseek.

19971107: Update modes: opening a file for reading and writing. Restriction on update modes: have to seek between read and write. Example of using a file in an update modes. Contents of a FILE. More buffering examples.

19971110: Examples of sscanf. Warning that sscanf always starts from beginning of string. Examples of sprintf. C preprocessor. How to use the C preprocessor. Basic commands in C preprocessor: #include, #define, #undef, #ifdef, #ifndef, #else, #endif. Example of preprocessor commands. General concept of macros. Examples of macros. The uppercase convention. fgetc versus getc. How getchar is defined. fputc versus putc. How putchar is defined. Predefined macros.

19971112: Example of using __LINE__ and __FILE__. Macro using __LINE__ and __FILE__. Using macros to avoid reserved words in compiler. Removing macros with #undef. Examples of discarding code with #ifdef. Meaning of #ifdef-#endif. Meaning of #ifdef-#else-#endif. Meaning of #ifndef-#endif. Meaning of #ifndef-#else-#endif. Goal of protected #include files. Example of nested #include files.

19971114: [Fifth homework assignment.] Scaling problems with nested #include files. Protected #include files. What protection does. Example of recursive function. Stack pictures. Stack pictures for a recursive function. Effect of static. Random topic: VT100 codes for moving around the screen.

19971117: Results of stack smashing. Example of code allowing stack smashing. Detail #1 about stacks: stacks grow from right to left. Detail #2 about stacks: return addresses are on stack. How function calls are implemented with stacks and goto. What stack looks like allowing a buffer overflow. How stack smashing works. Numbers in base 2. Bit operations: and, or, xor, not. Examples of left and right shifts.

19971119: What shifts do. What rotates do. Example of rotation. Warning to always use unsigned for bit operations. Common applications of bit operations: saving space; saving time with bit-parallel operations; cryptography. The sieve of Eratosthenes. Programming the sieve of Eratosthenes with one flag per byte. Programming the sieve of Eratosthenes with one flag per bit.

19971121: Memory picture for bits in the sieve of Eratosthenes. Space savings. Time savings. Dates and times generally. Difference between calendar time and process CPU time. Getting low-resolution CPU time. Getting low-resolution real time. Notes on obtaining higher-resolution real time. Converting real time to broken-down calendar time. Converting calendar time to string.

19971124: [Quiz on bit operations.] Diagram of some of the interfaces available for computer graphics. Text screen: two-dimensional array of characters. Character: fixed-size picture depending on screen. Graphics screen: two-dimensional array of dots. Dot: fixed-size rectangle of some color. Color: some amount of red plus some amount of green plus some amount of blue. VT100: converts stream of bytes into text drawing instructions.

19971126: Text window libraries. Graphics window libraries. Sample program using curses. More curses capabilities. What the IBM PC text screen looks like in memory. What a Sun 256-color graphics screen looks like in memory. What a 2-color graphics screen looks like in memory.

19971128: No class.

19971201: General idea of signals. What signals do by default. Examples of signals: SIGHUP, SIGINT, SIGQUIT, SIGILL, SIGFPE, SIGKILL, SIGBUS, SIGSEGV, SISPIPE, SIGTERM, SIGTSTP. Using the kill program. Using signal() to handle signals. SIG_DFL and SIG_IGN. Portability warning: signal() is unreliable on some systems.

19971203: [Review for final.]

19971205: [Review for final.] What's coming up in 360.

19971212: Final examination, 8:00-10:00.