CMPT

Main objective of class

learn about the concepts of Computing Science and Programming

Algorithms

a sequence of instructions to complete a task or solve a problem

Programming

the action of communicating an algorithm to computers using a specific language

Data structures

specific ways for computers to store a collection of data for better management (e.g., insert, remove, search)

The Compilation Process - Interpreted programming language (e.g., Python, Javascript)

Implement algorithms into code, interpreter runs one instruction at a time when executing the program

you (algorithm) → interpreter (source code)→ output (running program)

The Compilation Process - Compiled programming language (e.g., C/C++, Java)

you (algorithm) → compiler (source code)→ computer (machine code) → output (running program)

Interpreted VS Compiled

INTERPRETED

• Errors caught only when interpreter is trying to run them

• Can test code quicker because interpreter directly runs it

• Program less optimized because interpreter needs to convert the code into machine code internally every time

COMPILED

• Some errors can be caught during compile time so they can be fixed earlier

• Takes longer to get code running because of compilation process

• Program often performs better because some optimizations for the operating system and architecture can be done by the compiler

What was C designed to do

map to typical machine instruction

Provides low-level access to system memory via pointers

Variables

containers to hold values when program is running

Declaration of a variable

includes specifying:

• its type (what kind of value it is storing)

• its name (how is it going to be referred to in the remainder of the program)

Initialization of a variable

is to give (i.e., assign) the variable a value when it is declared

• usually a default value like 0, an empty string

• you should always do that (some compilers will do that automatically, but don’t count on that!)

Type

set of values together with a set of operations that can be applied to those values

int

specifies all 32-bit integers (negative/zero/positive) and the arithmetic they support (+-*/)

Bits and Bytes

Bit - single 0 or 1

Byte - combination of Bits

How many Bytes for int, long, double, and char?

calculate 1 byte and 4 bytes

int = 4

long = 8

double = 8

char = 1

(4 byte calculated as 2^(8×4), and ranges from negative to positive

Strongly-Typed VS Weakly-Typed

Strongly-typed language – all variables need to declare a type and stay at that type

• Compiler & run-time system check to make sure no unsupported operations applied

• C, C++, Java, C#, Pascal

Weakly/loosely-typed language – variable types are converted implicitly

• Javascript, Perl

Built-in (Primitive) Types in C

chat - charecter

int - integer

long - larger integer

float - decimal

double - larger decimal

for numbers “unsigned” only 0 and positive, doubles max possible value by giving up negatives

how to display each built in types

1. integer

2. decimals

3. scientific notation

4. characters

5. strings

6. pointers

1. integer - %d

2. decimals - %f

3. scientific notation - %e

4. characters - %c

5. strings - %s

6. pointers - %p

Pointers

variables to store addresses

make pointer: int* pt = &x

get value of pointer: *pt

values of pointers change every time program is run

Dereferencing Pointers

When * is used in the rest of the code, it means “dereference” the pointer, that is, “go to the memory address the pointer is pointing to and use that instead”

Pointers VS Data Variables

Why Are Pointers Useful?

• They allow functions to modify parameters passed to them

• They allow passing larger data types to a function using just the address (takes less space and the function can modify them)

• Optimize code as it allows reference to the data to reduce duplication of the data

• Let programmers to use arrays and strings

Write code for Pointer swap function

int main() {

int a = 2;

int b = 3;

printf("a is %d and b is %d\n", a,b);

swap(&a, &b);

printf("a is %d and b is %d", a,b);

return 0;

}

#include <stdio.h>

void swap(int* a, int*b){

int temp = *a;

(star)a = (star)b

*b=temp;

}

int main() {

int a = 2;

int b = 3;

printf("a is %d and b is %d\n", a,b);

swap(&a, &b);

printf("a is %d and b is %d", a,b);

return 0;

}

Arrays

array elements occupy continuous block of memory

index starts at 0, goes to length-1

name is pointer to 0th element

what does this output?

x=10

y=5

write code for making string 1-10

#include <stdio.h>

int main(void) {

char str[11];//declares an array of char with a bound of 11 for 10 char with null

for (int i=0; i<10; i++){

str[i] = '0'+i;

}

str[10] = '\0'; //null character is copied to the final element of the array str[10]

return 0;

}

what is array[i] equivalent to?

what is &(arr[7]) equivalent to?

*(array+i)

arr+7

Print array using for loop

#include <stdio.h>

int main(void) {

int arr[3]= {1,3,5};

for (int i=0; i<3; i++){

printf("%d", arr[i]);

}

return 0;

}

Print array and location using pointers code

#include <stdio.h>

int main(void) {

int arr[10]= {1,2,3,4,5,6,7,8,9,10};

for (int i=0; i<10; i++){

printf("arr[%d] at %p =%d\n", i, (arr+i), *(arr+i));

}

return 0;

}

An array in C is simply a…

…pointer to the first element of the array

Arrays being pointers means we can have…

…a different pointer pointing to the same array

But cannot change value of original pointer

difference between

1. arr[i]

2. &arr[i]

3. arr

4. arr+1

5. *(arr+i)

6. *arr=2

7. *(arr+4)=11

8. arr[i]+2

9. arr++

1. array element value of ith+1(%d)

2. array location of element ith +1 (%p)

3. array location of first element (%p)

4. array location of second element (%p)

5. array value of ith+1 element (%d)

6. changes first element value to 2

7. changes fifth element value to 11

8. array element value 2 past i

9. invalid

Print array of 0-9 using while loop

int main(void) {

int arr[10]= {0,1,2,3,4,5,6,7,8,9};

#include <stdio.h>

int main(void) {

int arr[10]= {0,1,2,3,4,5,6,7,8,9};

int i=0;

while (i<10){

printf("%d", arr[i]);

i++;

}

return 0;

}

find average of array code

float getaverage(float array[], unsigned int size){

}

int main(void) {

float array[10]= {-1,0,3,4,5,22,-3,9,8,10};

printf("%.2f\n", getaverage(array, 10));

return 0;

}

#include <stdio.h>

float getaverage(float array[], unsigned int size){

float avg = 0;

for (int i=0; i<size; i++){

avg+=array[i];

}

return avg/size;

}

int main(void) {

float array[10]= {-1,0,3,4,5,22,-3,9,8,10};

printf("%.2f\n", getaverage(array, 10));

return 0;

}

Make function to copy one array to another

int main(void) {

int intarr[4]={3,6,4,7};

int intarrcpy[4]={9,4,7,6};

copyarr(intarrcpy, intarr, 4);

#include <stdio.h>

void copyarr(int* dest, int* src, unsigned int size){

for (int i =0; i<size; i++){

dest[i]=src[i];

}

}

int main(void) {

int intarr[4]={3,6,4,7};

int intarrcpy[4]={9,4,7,6};

copyarr(intarrcpy, intarr, 4);

for (int i=0; i<4; i++){

printf("%d", intarrcpy[i]);

}

return 0;

}

How to indicate a constant variable

use all caps

1. int* const

2. int const*

1. constant pointer - modifying value pointed to is okay

2. pointer to a constant - modifying the pointer is okay

spiral rule

what can type char represent?

one symbol (letter / digit / punctuation mark / special symbol)

what does each do?

1. strlen

2. strcpy

3. strcat

4. strcmp

5. strstr

1. string length (excluding \0)

2. copies the C string into another array pointed to by a char pointer

3. appends a copy of the C string to another C string

4. compares two C strings and returns an integer indicating if they have the same sequence of characters

5. returns a pointer to the first occurrence of a C string within another C string

strlen function

make code

strlen(const char* str)

Returns the length (number of characters) of the string, excluding the null character \0 (stops counting when sees null)

#include <stdio.h>

int main(void) {

char str[20]= "hello";

int length = strlen(str);

printf("string is %s and length is %d", str , length);

return 0;

}

strcpy function

make code

strcpy(char* dest, const char* src)

Duplicate C strings

will stop at null, also copies null over

#include <stdio.h>

#include <string.h>

int main(void) {

char str1[]="hello";

char str2[40];

char str3[40];

strcpy(str2,str1);

printf("%s", str2);

strcpy(str3, "world");

printf("\n%s", str3);

return 0;

}

strcat function

make code

strcat(char* dest, const char* src)

Combining 2 C strings to make a new one

stops at null, also copies null over

#include <stdio.h>

#include <string.h>

int main(void) {

char str1[20]="";

char str2[]="hello";

strcat(str1, str2);

printf("\nstr1 is %s and has length %d", str1, strlen(str1));

strcat(str1, " world");

printf("\nstr1 is %s and has length %d", str1, strlen(str1));

return 0;

}

strcmp function

make code

strcmp(const char* str1, const char* str2)

Returns 0 if contents of both C strings are equal

Returns non-zero upon the first mismatch: < 0 if the mismatch character in str1 has a lower value than in str2, >0 otherwise

#include <stdio.h>

#include <string.h>

int main(void) {

char str1[]="abcd";

char str2[]="abCd";

char str3[]="abcd";

int result;

result = strcmp(str1, str2);

printf("%d", result);

result = strcmp(str1, str3);

printf("\n%d", result);

return 0;

}

strstr function

make function

Looks for the presence of a C string in another C string

Stops at the first occurrence and returns the pointer to it

#include <stdio.h>

#include <string.h>

int main(void) {

char str1[]="this is a very very important message";

printf("str1 is %s and has a length of %d", str1, strlen(str1));

char *key1 = "super";

char *key2 = "very";

char *match1 = strstr(str1, key1);

char *match2 = strstr(str1, key2);

if (match2 == NULL){

printf("not found");

}

else{

printf("found");

}

return 0;

}

What are C strings

character arrays with the null character \0 to indicate end of the sequence

Must include the string.h library

3 different methods to make strings and how to print them

1. char str2[] = {‘w’, ‘o’, ‘r’, ‘d’, ‘\0’};

2. char* str3 = “word”;

3. char str4[]=”world'“;

printf(“%s”, str);

2D Arrays

what does [2][3] mean and how is it declared

a 2D array is a pointer to an array of pointers

[rows][columns]

[2][3]={{0,0,0},{0,0,0}}

Make for loop for 2D Array

int arr[20][30];

for (int i = 0; i<20; i++){

for (int j = 0; j<30; j++){

arr[i][j]=0

}

}

How to access each element of a[3][4]

for “row-oriented 2D array”

Passing 2D Arrays into Functions

Specify at least the column dimension of the array (row dimension is optional)

Complete function for 2D array

void reduce_by_one(int arr[][3], int r){

int main(void) {

int arr[2][3] = {{1, 2, 3}, {4, 5, 6}};

reduce_by_one(arr, 2);

return 0;

}

#include <stdio.h>

void reduce_by_one(int arr[][3], int r){

for (int i = 0; i<r; i++){

for (int j=0; j<3; j++){

arr[i][j]-=1;

printf("\n%d", arr[i][j]);

}

}

}

int main(void) {

int arr[2][3] = {{1, 2, 3}, {4, 5, 6}};

reduce_by_one(arr, 2);

return 0;

}

Use a nested for-loop to initialize a 5-by-6 2D array with increase even numbers starting from 0 (i.e., first row 0, 2, 4, 6, 8; second row 10, 12, 14, 16, 18, …etc.)

#include <stdio.h>

int main(void) {

int evennum=0;

int a[5][6];

for (int i=0; i<5; i++){

for (int j=0; j<6; j++){

a[i][j]=evennum;

evennum+=2;

printf("\n%d", a[i][j]);

}

}

return 0;

}

what does (*(array+2))[4] in a 4-by-5 2D array point to?

type casting

Conditionals

Programming structures that control the flow of the program by determining which code is executed and which code is not, based on a condition

A condition is an expression that yields a yes/no answer, for example

The Boolean Variable Type

Conditions in C are represented by a different variable type called Boolean that has 2 possible values: true/false

Need to include the stdbool.h library

Write boolean for finding even number in array

include <stdio.h>

#include <stdbool.h>

int main(void) {

int j = 0;

bool evennum = false;

int arr[10]={1,3,7,6,-2,-7,4,5,8,2};

while (!evennum && j<10){

if (arr[j]%2==0){

evennum=true;

}

j++;

}

if (evennum){

printf("yes it is value %d index %d", arr[j-1], j-1);

}

else{

printf("no");

}

return 0;

}

what do &&, ||, and ! mean

and, or, not

Switch statements

Make struct with pointer, char, and int

access all

struct keyword and typedef

use . to access variables

To access the fields when the composite variable is a pointer, use (*…). or ->

Enum (Enumeration)

Enums allow us to define a type and assign names to integers

Function definition

A function is a self-contain block of code that can be reused as components of larger programs

A special type of function: void function, has no returned values, but can still use the return keyword to terminate

Local variables are stored on…

Dynamically allocated memory are store on…

Local → stack

Dynamic → heap

Compiler gcc on the source code file causes what to happen? (4)

C preprocessor

• scan the source code file and make some changes

C compiler

• translates the C code into assembler code specific to system

C compiler

• translates assembler code into binary to be read by the computer

C compiler

• links other object files/libraries to create executable program

Preprocessor Directives (Macros)

• #include “some_file”

• #include <some_file>

• #define

• #ifndef – #define – #endif

#include “some_file” makes the compiler look for some_file in the same directory where the directive is at

#include <some_file> makes the compiler look for some_file in the directory where it is configured to look for standard header files (e.g., stdio.h, string.h, stdbool.h)

#define – defines a macro so that whenever it is seen in the code it gets replaced with its corresponding value

if something is not defined, include the code between #ifnded and #endif for compilation, otherwise skip the code

Global VS Local

Global = outside of main

as rule of thumb, define and use variable in same {}

If there is a name conflict (same variable name used in a local scope), the local variable is used

Static variables

static in …

keeps variable when adding to it, for example when counting

malloc function

Need to include the stdlib.h library

realloc function

ptr = (int*)realloc(ptr, 2*sizeof(int))

realloc returns the same memory address from the heap with the specified size, but if it can’t, it will:

• allocate space somewhere else, copy the content over, free the original space, & return the address of the new space (if no new space is available, it’ll return NULL)

The free() Function

When memory is allocated using malloc, it has to be manually released

not releasing memory can cause memory leaks

rule of thumb: when there is malloc, must be free

The Dangling Pointer Issue

When free() is called, the memory pointed to by the parameter is de-allocated, but the pointer variable will still be storing the address, this situation is called having a dangling pointer

Typically happens when

• free() is called but the pointer is not set to NULL afterwards by the programmer

• Multiple pointers are pointing to the same memory, free() is called with one of them, programmer forgets to set all to NULL

• This is an issue because if later this pointer is used, the dereferenced value can be anything (unused, or allocated to some other dynamic variable requests)

Dynamic Memory Allocation And Arrays using malloc

get numbers from input and reprint them

#include <stdio.h>

#include <stdbool.h>

int main(void) {

int arrsize=0;

printf("how many numbers do you have: ");

scanf("%d", &arrsize);

int* arrptr = malloc(sizeof(int)*arrsize);

printf("enter 1 num at a time: ");

for (int i = 0; i<arrsize; i++){

scanf("%d", &arrptr[i]);

}

printf("you have enetered: ");

for (int i = 0; i< arrsize; i++){

printf("%d", arrptr[i]);

}

return 0;

}

Write a function that gets a parameter int n and returns the array of ints of length n, where array[i] = i^2

int main(void) {

gensquare(6);

return 0;

}

#include <stdio.h>

#include <stdbool.h>

int* gensquare(int n){

int* arr=(int*)malloc(sizeof(int)*n);

for (int i=0; i<n; i++){

arr[i]=i*i;

printf("\n%d", arr[i]);

}

}

int main(void) {

gensquare(6);

return 0;

}

rule of thumb for array size

if dont know size, use dynamically allocated memory

MSB & LSB

most significant bit and least significant bit

maximum number of unique values in a byte

Unicode…

255

Unicode uses up to 4 bytes to represent more characters

binary decimal places

use 32 bits

1 sign: 0=+, 1=-

8 exponents: ranging from -127 to 128

23 fractions: b22=1/2, b21=1/4…

binary decimal places smallest and largest possible numbers

Floating Point Encoding (example -3.625)

Recursion

functions calling the same function with a “smaller” parameter

To create a function that implements recursion (aka recursive function), you need (3)

• Some part of the function will call itself with a parameter modified from the original parameter

• At least one base case where the function will stop calling itself

• the modified parameter needs to move towards the base case (i.e., “smaller”)

write a recursive function to encode a decimal integer into a binary integer

int main(void) {

binary(6);

return 0;

}

#include <stdio.h>

#include <string.h>

void binary(unsigned int number){

if (number==0){

printf("0");

}

else if (number==1){

printf("1");

}

else{

binary(number/2);

printf("%d", number%2);

}

}

int main(void) {

binary(6);

return 0;

}

selection sort main idea

Time complexity best and worst case

Set current min to first value, look in array for smaller value, set as current min

Swap current min to front

Set next value of current min, scan and repeat

Best and worst = O(n²)

Selection sort pseudo code

let A be the array, N be the size of the array

Step 1: for i = 0 to N-1

• Step 1.1: minIndex ← i

• Step 1.2: for j = i+1 to N-1

  • Step 1.2.1: if A[j] < A[minIndex]

    • Step 1.2.1.1: minIndex ← j

  • Step 1.2.2: end if

• Step 1.3: end for

• Step 1.4: Swap A[i], A[minIndex]

Step 2: end for

Mergsort Pseudo-code

merge 2 arrays while also sorting them

let A be the destination array with size N, L & R be the 2 sorted arrays with size S & T (L[S] & R[T] = ∞)

• i ← S-1, j ←T-1

• for k = 0 to N-1

• if L[i] <= R[j]

• A[k] = L[i]

• i ← i+1

• else

• A[k] = R[j]

• j ← j+1

• end if

• end for

Write selection sort using recursion

void sort(int array[], unsigned size, unsigned int start){

int main(void) {

sort((int[]){4, 7, 5, 8, 3}, 5, 0);

return 0;

}

#include <stdio.h>

#include <string.h>

void sort(int array[], unsigned size, unsigned int start){

if (size-start>1){

unsigned int minIndex = start;

for (int i=start+1; i<size; i++){

if (array[i]<array[minIndex]){

minIndex=i;

}

}

int temp = array[minIndex];

array[minIndex]=array[start];

array[start]=temp;

printf("swapping %d with %d\n", array[minIndex], array[start]);

sort(array, size, start+1);

}

}

int main(void) {

sort((int[]){4, 7, 5, 8, 3}, 5, 0);

return 0;

}

What is a good algorithm?

criteria and desirable qualities

#1 Criteria: Correct

#2 Desirable qualities:

• easy to code & debug

• user-friendly interface to use

• small memory requirement

• takes little time to finish

• does not crash easily with edge case inputs

• modular to support modification & maintenance

2 Ways to Examine “Goodness” of An Algorithm

• Time complexity: is time used efficiently?

• Space complexity: is space used efficiently?

Define efficiency in terms of code

Efficiency is an essential quality to consider for large size problems!

• Another common description of the efficiency of an algorithm is “performance”

Order of Algorithm & Problem Input Size

Order = number of critical operations that get carried out,

larger problem = more operations

Can express order as a function of the problem input size, which can be:

• dimensions of lists or matrices

• number of values to be added

• number of values within which we search

• number of values to be sorted

Time Complexity of An Algorithm

Function of problem input size

• approximate number of operations

• order of an algorithm

• time complexity of an algorithm

• We use such function of problem input size to rank different algorithms

• To make it easier to read and compare, we use a few reference functions:

what does O(n) algorithm mean

for a sufficiently large n, the time that the algorithm takes (by executing critical operations) will be proportional to the reference function n, where n is the problem input size (e.g., if we need to sort 1000000 numbers, n is 1000000)

How Do We Calculate Time Complexity?

Count the number of times a critical operation is executed

• Assume all elementary operations run in 1 time unit each

• Usually assignments/calculations and in loops

Disregard “constants” (e.g., print a few lines in the entire code, declare a variable)

• Usually seen as un-indented lines and/or independent of the input size

Disregard “lower exponent (or order) terms” (e.g., disregard n when both n2 & n are present)

• Keep the highest exponent term and compare it to one of the reference functions by putting them in the form O(reference function), e.g., O(1), O(logn), O(n), …etc.

Why Can We Drop Multiplicative Constants in big-O notation?

We can drop multiplicative constants because they correspond to the number of critical operations which won’t change as N changes

• when N becomes large, two algorithms with different multiplicative constants but the same highest order terms are essentially the same

Mathematically Speaking, Big-O Is…

Measuring performance of algorithms

#1 Criteria: It has to be correct

#2 Criteria: easy to code & debug, needs less memory, takes less time, …etc.

Some Simple Rules for Deriving Big-O Mathematically

Big-O

1. recursion

2. mergesort

1. O(N²)

2. O(NlogN)

Linear search (Boolean) pseudo-code

1 for i = 0 to N-1

2 if array[i] == key

3 return true

4 end if

5 end for

6 return false