Table of Contents

  1. Intro Class
  2. Intro Tutorial 0
  3. Tutorial 1
  4. Tutorial 2
  5. Midterm Notes
  6. Tutorial 8
  7. Tutorial 9
  8. Tutorial 10
  9. Tutorial 11
  10. Tutorial 12



Intro Class

September 08, 2016

CS 136

Professor: Dave Tompkins Call him “Dave”, Dr. Tompkins

Assignments due Wednesdays at 9:00pm Box Info

Textbook: “C Programming: A Modern Approach” (CP:AMA) by K. N. King. (strongly recommended)

10 assignments per term

For the iclickers, people in the lowest chosen answer among ABCDE, get a bonus mark

The answer was E with 7, and luckily I was among the 7.

0.0333% in marks if you get an iclicker wrong

READ assignment questions carefully

Movie before class is either “My Neighbour Totoro” or “Iron Giant”. We were left on a cliffhanger and will see what it is on Tuesday, September 13, 2016

Academic integrity will be strictly enforced for gold questions.

Marmoset Assignments are submitted to the Marmoset submission system: http://marmoset.student.cs.uwaterloo.ca/

There are two types of Marmoset tests:

  • Public (basic / simple) tests results are available immediately and provide simple feedback to ensure your program is “runnable”. Public tests do not thoroughly test your code.
  • Private (comprehensive / correctness) tests are available after the deadline and are used to fully assess your code.

Put comments in code as you go, not at the end




Intro Tutorial 0

September 12, 2016

CS 136 Tutorial 0

Clicker Code: AD
ISA: Vuk (pronounced Vook, not like “yuck”)

Lab Hours

A computer lab is booked exclusively for CS 136 use:

  • MC 3005
  • Tuesdays, 2:30 – 6:30pm

Office Hours

Office Hours will be updated on the course website:
www.student.cs.uwaterloo.ca/~cs136/officeHours
Many will be held in the CS Learning Centre (MC 4065)

Seashell [DEMO]

http://www.student.cs.uwaterloo.ca/seashell

Marmoset

  • checks the work
  • Public (simple / basic) tests
  • vs. Private (full / comprehensive) tests

Reminders

  • A0 must be completed before you can receive any other assignment marks.
  • Register your clickers



Tutorial 1

September 19, 2016

CS 136 Tutorial 1

9:30 - 10:30 am

Full Racket

#lang racket

(f a b) (f a) (f)

Anything that is not false, is true #t for true #f for false

and produces the last argument (if it is empty it is #t, and #f if it has #f) or produces the first non-false argument (or produces #f for all #f)

Conditionals

(cond [q1 a1] [q2 a2] [else a3])

Lists




Tutorial 2

September 26, 2016

CS 136 Tutorial 2

9:30 - 10:30 am

Sample C Program

  • #include
  • purpose statement, require in contract
  • use of {}, (), indentation,
    rest seen in powerpoint



Midterm Notes

October 29, 2016

CS 136 Midterm Notes

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

modularization:

  • sharing among a team is easier
  • can use helper function that help other functions
  • good style to store each module in a separate file (if it breaks, fix module, not whole program) main reasons for modularization:
  • re-usability: re-used and construct large programs more easily
  • maintainability: easier to test and debug a single module
  • abstraction: understand what functionality it provides, but not need to understand how it is implemented

terminology:

  • client requires functions that a module provides
  • module dependency graph cannot have any cycles
  • root or main file acts as a client

Scope:

  • local only visible inside of the local region (or function body) where it is defined
  • global identifiers are defined at the top level and are visible to all code following the definition

global can have either program or module scope:

  • module identifiers are only visible in the module(file) they are defined in
  • program identifiers are visible outside of the module they are defined in

Module Interface

  • module interface is a list of functions that the module provides
  • implementation is the code, interface is what the client would need to use the module
  • interface is provided, implementation is hidden

Interface documentation:

  • overall description of the module
  • list of functions it provides
  • contract and purpose for each provided function
  • white box tests cannot be tested by a client

Designing Modules:

  • high cohesion all interface functions work towards a “common goal”
  • low coupling little interaction between modules

Coupling Info

##Interface vs Implementation

  • information hiding where the interface is designed to hide any implementation details from the client
  • security is important because it prevents the client from tampering with data used by the module
  • flexibility to change the implementation in the future

Data structures and abstract data types

  • abstract data type
  • implemented as data storage modules and the implementation is hidden from the client

dictionary adt:

  • lookup: keys and retrieve corresponding value
  • insert: add a new key/value pair
  • remove: deletes a key and its value

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

Typing:

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)

Initialization:

const int my_number = 42;

”= 42” is called the initialization

C operators

  • (+, -, *, \/)
  • / operator rounds towards zero

The % operator: (remainder)

  • modulo
  • 21 % 2 = 1

Function Terminology:

  • call a function, function is passed, returns a value

Entry Point:

  • OS needs to know where to start, this is called the entry point
  • most languages entry point is at the top, for C the entry point is the special function main
  • main successful is zero, and if an error occurs it is non-zero
  • return optional, defaults to zero
  • printf part of C stdio (standard i/o module)
  • “%04d\n” pad with 0s to make it 4 digits long
  • similar to Racket, C short-circuits and stops evaluating an expression when the value is known

Functions

  • a function (or identifier) must be declared before any expression it appears in
  • a declaration communicates to C the type of an identifier
  • subtle difference between definition and declaration
  • declaration: specifies the type of an identifier (like a movie trailer)
  • definition instructs C to “create” the identifier (definition includes a declaration) (the actual movie)
  • extern declares variables but not defined

C Modules:

  • no built-in functions in C
  • standard modules (or libraries) with many useful functions
  • stdio standard module provides the printf function
  • some assert, stdbool, limits, string, stdlib
  • to include stdio module: #include
  • to include a “regular” module: #include “mymodule.h”

Creating a Module in C

  • place interface and the implementation into separate files
  • interface (.h) we place declarations for the functions and variables that the module provides
  • in the implementation (.c) we place all of the definitions

#include

  • preprocessor directive

Scope

  • Racket each global identifier has module scope
  • C each global identifier has program scope
  • to declare a C global function or variable has module scope, ‘static’ keyword is used
  • C cannot have any top-level expressions

Assert standard module

  • assert(e) stops when the expression s is false, and if e is true, nothing happens
  • assert the requirements when feasible

bool type:

  • stdbool standard module

floating point type

  • inexact numbers in Racket
  • double is still inexact but has significantly better precision

Structures

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

struct posn {
  int x;
  int y;
};
  • structure operator (.) which selects the value from the requested field
  • equality operator does not work with structures, must define own equality function
  • “return {px. * f, p.y * f}” is INVALID

Chapter 4: Imperative C

  • functional means to produce a value depending only on the parameters
  • functional programming paradigm is to only use constant values that never change, functions produce new ones rather than existing ones
  • imperative uses a sequence of statements to give instructions to the computer
  • begin in C is similar to local in Racket

Side Effects

  • printf is a side effect with output
  • functional programming has no side effects
  • add effects to a contract if there are any side effects
  • printf returns the number of characters printed
  • expression statement is followed by a semicolon, and the value at the end of the expression is ignored

Block Statements

  • a block ({}) is a compound statement that contains a sequence of statements
  • a C block ({}) is similar to Racket’s begin statemetns that are evaluated in sequence
  • a block ({}) does not “produce” a value, so return is needed
  • a block can contain local scope definitions which are not statements two types of C statements:
  • compound statements (a sequence of statements)
  • expression statements (for producing side effects)
  • other type is control flow statements

Control Flow Statements

  • return leaves a function to return a value
  • if (and else) statements execute statements conditionally

Coupling Info

State

  • defining imperative programming paradigm is the manipulative state
  • state ‘moment in time’
  • in a program each variable is in a specific state
  • functional programming, each variable has only one possible state
  • imperative programming, each variable can be one of many possible states
  • hence the name variable can change during the execution of the program

Mutation

  • changing variable
  • good style to use const
  • mutation achieved with assignment operator (=)
    int m = 5; //initialization
    m = 28;    //assignment operator
    

= used in initialization is not the assignment operator

  • functional programming paradigm, a function cannot have any side effects and the value it produces depends only on the parameters
  • imperative programming paradigm a function may have side effects and its behaviour may depend on the state of the program

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

Chapter 5 Memory and Control Flow

  • one bit of storage (in memory) has two possible states: 0 or 1
  • a byte is 8 bits in store, each byte in memory is in one of the 256 possible states
  • position of the byte is the address

C encounters a variable definition:

  • reserves or finds space in memory to store a variable
  • “keeps track of” the address of that storage location
  • stores the initial value of the variable at that location

  • variable definition reserves space, but a declaration does not.

sizeof for int

  • how much space in memory depends on the type of variable
  • size operator produces the number of bytes to store a type
  • int is 4 bytes, only \(2^32\) possible values (4,294,967,296)
  • %zd is placeholder for a size
  • int storage in memory is 4 consecutive bytes of memory
  • integer limits -\(2^{31}\) to \(2^{31}\)-1
  • using #include has constants INT_MIN and INT_MAX

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

char type

  • one byte of storage for a char
  • \(2^8\) (256) possible values for a char and the range of values (-128, … 127)

ASCII

C Characters

  • single quotes (‘) use to indicate ASCII characters
    char letter_a = 'a';
    char ninety_seven - 97;
    

    both are the exact same

Sructure in Memory

  • only reserved when a struct variable is defined
  • amount of space is at least the sum of sizeof each field, but may be larger
  • floats have more precision, more memory used

Sections of Memory

  • code, read-only data, global data, heap, stack
  • section combined into memory segments
  • memory outside is a segmentation fault

Code

  • converted to machine code that is ‘machine readable’
  • machine code placed in code section

Read-only and Global Data Sections

  • global variables are placed in read-only data section (constants) OR global data section (mutable variables)
  • global variables’ space is reserved before the program begins execution
  • code from program (and modules) is scanned and all global variables are identified
  • next space for each global variable is reserved
  • memory is properly initialized, this happens before main is called

Control Flow

  • keep track of program location
  • when a function is called, the program jumps to the start of the function
  • return “returns” back to the location of the calling function
  • location to remember where to jump back is called the “return address”

Call Stack

  • history is known as the call stack
  • each time a function is called, a new entry is pushed to the stack
  • when return occurs the entry is popped off the stack

Stack Frames

  • entries pushed onto the call stack are known as stack frames
  • each function call creates a stack frame stack frame contains:
  • argument values
  • local variables
  • return address

  • with Racket, before a function is called, all of the arguments must be values
  • C makes a COPY of each argument value and places the copy in the stack frame
  • space for local variable is only reserved when the function is called
  • space is reserved within a newly created stack frame
  • when the function returns the variable (and the entire frame) is popped and effectively “disappears”

Stack Section

  • bottom of the stack is placed at the highest available memory address

Uninitialized Memory

  • all global variables will automatically initialize the variable to zero
  • local variable has an arbitrary initial value

Model

  • state has combination of program location and memory
  • calling a function is control flow
  • stack frame is created
  • copy of argument is placed in the stack frame
  • current program location is placed in the stack frame as the return address
  • program location is changed to the start of the new function
  • initial values of local variables are set when their definition is encountered

Return

  • when it returns current program location changes back to the return address
  • stack frame is removed (“popped from Stack memory”)

If Statement

Loops

  • while(expression) statement
  • loops repeatedly until the expression is false
  • a copy of each argument is passed to the function, so the function sum is free to mutate its own copy of k

While Errors

  • endless loops

Do While

  • statement is always executed at least once, and the expression is checked at the end of the loop

Break

  • break form the middle of a loop
  • terminates from the (innermost) loop
  • usually breaks a (purposefully) infinite loop

Continue

  • control flow statement that skips over the rest of the statements in the current block ({}) and “continues” with the loop

For Loop

  • for(setup; expression; update) { body statement(s) }
  • setup can include a definition

Chapter 6 Pointers

Address Operator

  • expose underlying memory model
  • address operator (&) produces the starting address of where the value of an identifier is stored in memory
  • printf placeholder to display an address is “%p”
  • storing an address a pointer
  • value of a pointer of a address
  • size of a pointer is always 8 bytes (regardless of type of data stored at that address)

Indirection Operator

  • (*) known as the dereference operator is the inverse of (&)
  • *p produces the value of what pointer p “points at”

Pointers to Pointers

  • pointer p points to p is an error
    int *p = &p;
    

Null Pointer

  • points to “nothing” or “invalid”
  • if you dereference a NULL pointer, the program will probably will likely crash

Function Pointers

  • Racket, functions are first-class values
  • Racket functions are values stored in variables and data structures
  • in C, functions are not first-class values, but function pointers are ``` int add 1(int i) {return i + 1;}

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]); } } ```




Tutorial 8

November 07, 2016

scan in words from i/o ``` int main(void){ int num_words = 0; // state == 0 if we’re looking for a new word // state == 1 if we’re currently reading through a word int state = 0; char input; int result = scanf(“%c”, &input); while (result == 1){ if ((input <= ‘Z’ && input >= ‘A’) || (input <= ‘z’ && input >= ‘a’)){ if(state == 0){ ++num_words; } } else { if (state == 1){ state = 0; } } result = scanf(“%c”, &input); } printf(“%d\n”, num_words); }




Tutorial 9

November 14, 2016

Efficiency and Dynamic Memory





Tutorial 10

November 21, 2016

  • Dynamic Memory realloc doubling strategy
  • Abstract Data Types (ADTs)
  • Intro to Linked Lists

associative array


freq

reverse linked list (data structure)




Tutorial 11

November 28, 2016

PostOrder

  • go to furthest left and then right, and then the node itself

Doubly Linked Lists

  • pointer to front and back
  • pointers to before and after of each node
void dll_print(struct doublylinked *dll) {
  for(struct dllnode *current = dll->front;
      current != NULL; current = current->next){
  printf("[%d]->", current->item);
  }
  printf("NULL\n");
}

void dll_reverse(struct doublylinked *dll) {
  struct dllnode *temp = dll->front;
  dll->front = dll->back;
  dll->back = temp;
  for(struct dllnode *current = dll->front;
      current != NULL; current = current->next){
    struct dllnode *temp = current->next;
    current->next = current->prev;
    current->prev = temp;
  }
}



Tutorial 12

December 05, 2016

String is a pointer to a null terminated array of characters

[malloc][][][]

char *array []

HEAP [LL head]

head points to the first node

[node 1 next item] node has an item and a pointer to the next one

[node 2 next item]

[node 3 next item]

NULL

in freeing, get a temp pointer to the next node, and then free the current node