Table of Contents
- Intro Class
- Intro Tutorial 0
- Tutorial 1
- Tutorial 2
- Midterm Notes
- Tutorial 8
- Tutorial 9
- Tutorial 10
- Tutorial 11
- Tutorial 12
Intro Class
September 08, 2016
CS 136
Professor: Dave Tompkins
Call him “Dave”, Dr. Tompkins
Assignments due Wednesdays at 9:00pm
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
##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)
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
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:
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
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:
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
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
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