CS 136 Midterm Notes

module: provides a collection of functions that share a common aspect or purpose.




global can have either program or module scope:

Module Interface

Interface documentation:

Designing Modules:

Coupling Info

##Interface vs Implementation

Data structures and abstract data types

dictionary adt:

stack: only touch top queue: lineup sequence: line where remove anywhere in adt

stack: push: add new item to top pop: remove top item top: returns the top item is-empty: determines if it is empty

queue: add-back: add item to the end remove-front: remove from the front front: returns the item at the front is-empty: determines if the queue is empty

sequence: item-at: returns the item at given position insert-at: insert new item at given position remove-at: removes an item at given position length: return number of items in sequence

C names must start with a letter, and only contain letters, underscores, and numbers


Racket uses dynamic typing: the type of the identifier is determined while the program is running C uses static typing: the type of the identifier must be known before the program is run. (The type is declared in the definition and cannot change)


const int my_number = 42;

”= 42” is called the initialization

C operators

The % operator: (remainder)

Function Terminology:

Entry Point:


C Modules:

Creating a Module in C



Assert standard module

bool type:

floating point type


(struct posn (x y)) (in C)

struct posn {
  int x;
  int y;

Chapter 4: Imperative C

Side Effects

Block Statements

Control Flow Statements

Coupling Info



= used in initialization is not the assignment operator

prefer: ++x; –x;
x++; x–;

Chapter 5 Memory and Control Flow

C encounters a variable definition:

sizeof for int

overflow occurs when it goes under the int_min or over the int_max

char type


C Characters

Sructure in Memory

Sections of Memory


Read-only and Global Data Sections

Control Flow

Call Stack

Stack Frames

Stack Section

Uninitialized Memory



If Statement


While Errors

Do While



For Loop

Chapter 6 Pointers

Address Operator

Indirection Operator

Pointers to Pointers

Null Pointer

Function Pointers

int main(void){ int (*fp)(int) = add1; printf(“add1(3) = %d\n”, fp(3)); }

add1(3) = 4

## Mutation & Parameters
- "pass by value" in C, copy of an argument is passed to a function
- "pass by reference" where a variable is passed to a function can be changed by the function
- C can emulate pass by reference by passing the address of the variable we want the function to change (still considered "pass by value" since we pass the **value** of the address)

- don't return an address in its stack frame because all memory within the frame should be considered invalid

## Passing Structures
- a **copy** of each argument value is placed into a stack frame, for large struct this can be inefficient
- arrow selection operator (->) combines the indirection and the selection operators

## Const Parameters and Pointers

void cannot_change(const struct posn *p){ p->x = 5; // INVALID }

p can change, but must always point at a const int
The rule is "const" applies to the type to the left of it, unless it's first, and then it applies to the type to the right of it.

int my_function(const int x){ //mutation of x here is invalid // … }

Because a **copy** of the argument is made for the stack, it does not matter if the original argument value is constant or not. A **const** parameter communicates that **the copy** will not be mutated

## Opaque Structures in C

struct posn; // INCOMPLETE

struct posn my_posn; // INVALID struct posn *posn_ptr // VALID

## Chapter 7 I/O Testing
Input & Output (I/O for short)
- scanf("%d", &i); // read in an integer, store in i
- return value of scanf is the number of values successfully read in

count = scanf(“%d”, &i);

if (count != 1){ printf(“Fail! I could not read in an integer!\n”);”) }

scanf("%d", &i) will ignore whitespace (spaces and newlines) and read in the next integer
If the next non-whitespace input to be read in is not a valid integer (e.g. a letter), it will stop reading and return zero

## Chapter 8 Arrays and Strings
- two built-in "compound" data storage:
structures and arrays

int my_array[6] = {4,8,15,16,23,42}

- **fixed number** of elements and all have the **same type**
- to define an array we know the **length** of the array in advance
- each individual value in the array is known as an element
- to access an element, its index is required
- index starts at 0
- entire array cannot be assigned at once
- each individual element must be mutated
- unitialized **global** arrays are zero-filled
- unitialized **local** arrays are filled with arbitrary ("garbage") values from the stack
- remaining values are initialized to zero (even with local arrays)

int b[5] = {1,2,3}; // b[3] & b[4] = 0 int c[5] = {0}; // c[0] … c[4] = 0

length can be omitted and automatically determined from number of elements in initialization

int b[]; // INVALID

Only valid if the array is initialized

## Array Size
- length if number of elements in the array
- size is the number of bytes it occupies in memory
- array of k elements is, each size s is k x s bytes

Array of siz elements (int a[6]) is (6 x 4 = 24)

C does not keep track of the array length as part of the array data structure

## Array identifier
- value of an array (a) is the same as the **address** of the array (&a) which is also the address of the first element (&a[0])

## Passing Arrays to Functions
- only the **address** of the array is copied to the stack frame, this is more efficient than copying the entire array to the stack

## Pointer Arithmetic
- if p is a pointer, (p + 1) **depends on the type** of the pointer p
- (p + 1) adds the sizeof whatever p points at
- rule is p + i x sizeof(\*p)
- subtracting works the same way
- mutable pointers can be incremented or decremented (++p is equivalent to p = p + 1)
- can't add two pointers
- subtract two pointers if they are the same type:
(p - q)/sizeof(\*p)
- pointers of the same type can be compared with comparison operators <,<=, ==, !=, >=, >

## Pointer Arithmetic and Arrays
- a[i] is equivalent to \*(a + 1)

## Array Map

// effects: replaces each element a[i] with f(a[i]) void array_map(int (*f)(int), int a[], int len) { for (int i=0; i < len; ++i) { a[i] = f(a[i]); } } ```