# Week 2 - Dynamic Arrays

## Team

>Members:
>
>-Sean Bos [532785]
>-Boxing Jiang [521516]
>
>
> Date:

## Activities
Make sure to have the activities signed off regularly to ensure progress is tracked.

Before you start, download the project from Blackboard and explore the code contained in it.

### Activity 1: Random access

Rewrite the code by replacing **all** expressions in which pointers are dereferenced with equivalent ones that use the *array index operator* ("[..]").

#include <stdio.h>
#define COUNT (50)

void fill_fibonacci(unsigned long long * storage, int count) {
	*storage = 0;
	*(storage + 1) = 1;
	for (int i = 2; i < count; i++) {
		*(storage + i) = *(storage + i - 1) + *(storage + i - 2);
	}
}

int main(void) {
	unsigned long long array[COUNT];
	fill_fibonacci(array, COUNT);
	for (int i = 1; i < COUNT; i++) {
		printf("f(%d) = %llu\n", i, array[i]);
	}
}

Rewritten:

#include <stdio.h>
#define COUNT 50

void fill_fibonacci(unsigned long long * storage, int count) {
    storage[0] = 0;
    storage[1] = 1;
    for (int i = 2; i < count; i++) {
        storage[i] = storage[i - 1] + storage[i - 2];
    }
}

int main(void) {
    unsigned long long array[COUNT];
    fill_fibonacci(array, COUNT);
    for (int i = 1; i < COUNT; i++) {
        printf("f(%d) = %llu\n", i, array[i]);
    }
}

### Activity 2: Array definition

Explain what each of the three fields of the `array_t` structure listed below is used for.

Find out, for your system, what the maximum number of elements is that can be stored in the array.

typedef struct array {
    size_t capacity;
    size_t count;
    float *data;
} array_t;

`Capacity` is the maximun amount of elements the array can hold.
`Count` is the current amount of elements the array is holding.
`Data` is the pointer for us to access the array values.

From my system, the maxinum value of size_t is 18446744073709551615 bytes, which is about 18 quintillion, so the array can hold about 2.25 quintillion elements.

### Activity 3: Correct initialization

Version 1 is incorrect because it is returning the pointer of a local variable, which can result in undefined behavior. Also, it is not allocating memory on the heap so it is not creating a dynamic array. To fix this, we can use the malloc function to allocate some memory to make a actual dynamic array just like in version 2.

array_t* array_init(array_t *p_array, size_t capacity) { // version 2
    
    if (p_array != NULL) {
        
        p_array->data = malloc(sizeof(float[capacity]));
        p_array->count = 0;
        
        //If p_array->data is not NULL, then capacity is assigned to p_array->capacity, 
        p_array->capacity = p_array->data != NULL ? capacity : 0;
    }
    return p_array;
    
}

### Activity 4: Cleaning up

Record your answer here.

Program 1 is correct. On program 2, the variable array didn't allocate any memory unlike program 1, it's freeing the first element of the automatic lifetime variable array which would result in undefined behavaior.

//program 1 
int main(void) {

     array_t *array = (array_t *) malloc(sizeof(array_t));
     array_init(array, 10);
     // .... do some work ...
     // finally, clean up
     array_destroy(array);
     free(array);
    }


// program 2
int main(void) {
    array_t array;
    array_init(&array, 10);
    // .... do some work ...
    // finally, clean up
    array_destroy(&array);
    free(&array);
}

### Activity 5: Resizing an array

Record your function definition here.
The growth rate of dynamic array can be 1.5.

// enlarges the array geometrically so that it can contain at least min_capacity elements

#define ARRAY_GROWTH_RATE 1.5

void array_reserve(array_t *p_array, size_t min_capacity) {

    size_t capacity = p_array->capacity;

    while (capacity < min_capacity) {
        capacity = (capacity + 1) * ARRAY_GROWTH_RATE;
    }

    if (capacity != p_array->capacity) {

        p_array->data = realloc(p_array->data, (sizeof(float) * capacity));


        if (p_array != NULL){ // check if allocation worked

            p_array->capacity = capacity;

        }

        else{

            p_array->capacity = 0;

        }
    }
}

### Activity 6: Appending values

void array_append(array_t * arr, float value){

    //check if there's enough space and extend the space if not
    if (arr->capacity == arr->count){
        
        array_reserve(arr, arr->count + 1); //we are just adding one new element

    }

    arr->data[arr->count] = value;
    arr->count++;

}

### Activity 7: Inserting values

Record your function definition here.

void array_insert(array_t * arr, size_t index, float value) {
    

    if (index <= arr->capacity) //must be a valid index
    {

        array_append(arr, 0); //since we are inserting, we need extra slot for the old values

        for (size_t i = 0; i < (arr->count - index); i++){

            arr->data[arr->count - i] = arr->data[(arr->count - i) - 1]; //make the 'next' element value to be the 'previous' element value

        }

        arr->data[index] = value;

    }

}

### Activity 8: Removing by index

Record your function definition here.

void array_remove(array_t * arr, size_t index) {
    
    for (size_t i = index; i < arr->count - index; i++) {

        arr->data[i] = arr->data[i + 1];

    }

    arr->count--;
}

### Activity 9: Constant time complexity

Consant time complexity means the program takes the same time to run no matter what the input size is.


### Activity 10: Worst-case time complexity

| Operation | Worst-case time complexity |
| --------------- | -------------------------- |
| Insert | Add value to the first index O(n) |
| Remove | Remove the first index value O(n) |
| Lookup / access | Since it's random access, so O(1) |

At both the worst-case of `Insert` and `Remove` operations, all elements of the array needs to be shifted, so it's O(n), it scales with the size of the array as it's shifting n amount of elements.

### Activity 11: Complexity of *append*

The average time complexity should be O(1) because you are just inserting a new element. When you don't enouh enough array size and you need to allocate new size, you will just allocate a bigger capacity with realloc and the array doesn't need a new address.

### Activity 12: Storing grades in a dynamically growing array

// keep asking the user to enter a grade, stop when user enters 0
void input_grades(array_t * grades){

    float userInput;
    int studentNumber = 1;

    printf("Enter student %d's grade: \n", studentNumber);
    scanf("%f", &userInput);
    array_append(grades, userInput);

    while (userInput != 0){

        studentNumber++;
        printf("Enter student %d's grade: \n", studentNumber);
        scanf("%f", &userInput);
        array_append(grades, userInput);

    }
}


// computes and returns the average grade
float average(const array_t * grades){

    float gradeSum = 0;

    for (int i = 0; i < (grades->count - 1); i++){

        gradeSum = gradeSum + grades->data[i];


    }

    return (float) gradeSum / (grades->count - 1);

}


// counts and returns the number of grades that are at least the threshold
int num_passed(const array_t * grades, float threshold){

    int numPassedAmount = 0;

    for (int i = 0; i < (grades->count - 1); i++){


        if(grades->data[i] >= threshold){

            numPassedAmount++;
        }

    }

    return numPassedAmount;
}


int main() {

    array_t grades;
    array_init(&grades, 0);
    input_grades(&grades);
    float averageNum = average(&grades);
    int passed = num_passed(&grades, 5.5f);
    printf("Average grade: %.2f\n", averageNum);
    printf("%d out of %zu students passed\n", passed, grades.count - 1);
    array_destroy(&grades);

}

## Looking back

### What we've learnt

Formulate at least one lesson learned.

### What were the surprises

Fill in...

### What problems we've encountered

Fill in...

### What was or still is unclear

Fill in...

### How did the group perform?

How was the collaboration? What were the reasons for hick-ups? What worked well? What can be improved next time?

> Written with [StackEdit](https://stackedit.io/).