# Week 2 - Dynamic Arrays

## Team

Team name:
Date:

Members
Viggo
Max
Tim
Daan

| Role | Name |
|-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|------|
| **Facilitator** keeps track of time, assigns tasks and makes sure all the group members are heard and that decisions are agreed upon. |Viggo|
| **Spokesperson** communicates group’s questions and problems to the teacher and talks to other teams; presents the group’s findings. |Tim|
| **Reflector** observes and assesses the interactions and performance among team members. Provides positive feedback and intervenes with suggestions to improve groups’ processes. |Daan|
| **Recorder** guides consensus building in the group by recording answers to questions. Collects important information and data. |Max|

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

Set up a project in CLion to write the small programs needed in some of the activities.

### Activity 1: Random access

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

#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
This is how you include code listings in your markdown document:

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

de capacity houd de hoeveelheid data dat de array aan kan
de count houd het aantal objecten bij dat in de array zit
de float houd de positie van de data bij

### Activity 3: Correct initialization

array_t *array_init(array_t *pArray, size_t capacity);

array_t* array_init(array_t *pArray, size_t capacity) { // version 3
 if (pArray != NULL) {
 if (capacity != 0){
 pArray->data = malloc(sizeof(float[capacity]));
 pArray->count = 0;
 saxion.edu
 pArray->capacity = pArray->data != NULL ? capacity : 0;
 }
 else{
 pArray->data = NULL;
 pArray->count = 0;
 pArray->capacity = 0;
 }
 }
 return pArray;
 }

### Activity 4: Cleaning up

// program 2
12 int main(void) {
13 array_t *array = (array_t *) malloc(sizeof(array_t));
14 array_init(array, 10);
15 // .... do some work ...
16 // finally, clean up
17 array_destroy(array);
18 free(array);
19 }

Record your answer here

### Activity 5: Resizing an array

void array_reserve(array *p_array, size_t min_capacity) {
    size_t capacity = p_array->capacity;
    while (capacity < min_capacity) {
        capacity = (capacity + 1) * 1.5
    }
   realloc(p_array, capacity *sizeof(float));
    p_array->capacity = capacity;
}

### Activity 6: Appending values

void array_append(array_t * array, float value){
    if(array->count >= array->capacity) {
        array_reserve(array, array->capacity+1);
    }
    array->data[array->count] = value;
    array->count++;
}

### Activity 7: Inserting values

void array_insert(array * arr, int index, float value);

void array_insert(array_t *array, int index, float value) {
    if (array->count >= array->capacity) {
        array_reserve(array, array->capacity + 1);
    }
    for (unsigned long i = array->capacity; i > (unsigned long)index - 1; --i) {
        float tempvalue =  array->data[i];
        array->data[i + 1] = tempvalue;
    }
    array->data[index] = value;
    array->count++;
}

### Activity 8: Removing by index

void array_remove(array * arr, int index);

void array_remove(array_t * array, int index){
    for (unsigned long i = index; i < array->count; ++i) {
        array->data[i] = array->data[i+1];
    }
    array->count--;
}

### Activity 9: Finding a value

int array_find(const array * arr, float value);

int array_find(const array_t * array, float value){
    for (unsigned long i = 0; i < array->count; ++i) {
        if(array->data[i] == value){
            return i;
        }
    }
    return -1;
}

### Activity 10: Constant time complexity

lookup omdat
O(1)

### Activity 11: Worst-case time complexity

| Operation | Worst-case time complexity |
| --------------- | -------------------------- |
| Insert | O(n) |
| Remove | O(n) |
| Find | O(n) |
| Lookup / access | O(1) |

Record your answer here

### Activity 12: Complexity of *append*

O(n)
Bij de average kan je wat bijna nooit gebeurd uitsluiten.

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

#include <stdio.h>
#include <malloc.h>

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

void array_reserve(array_t *p_array, size_t min_capacity);

array_t *array_init(array_t *pArray, size_t capacity);

void array_append(array_t *array, float value);

void array_insert(array_t *arr, int index, float value);

void array_remove(array_t *arr, int index);

int array_find(const array_t *array, float value);

void input_grades(array_t *array);

float average(array_t *array);

int num_passed(array_t *array);

void array_destroy(array_t *pArray);

int main() {
    array_t grades;
    array_init(&grades, 4);
    input_grades(&grades);

    printf("Average grade: %.2f\n", average(&grades));
    printf("%d out of %lu students num_passed\n", num_passed(&grades), (long) grades.count);

    array_destroy(&grades);
}

void array_reserve(array_t *p_array, size_t min_capacity) {
    size_t capacity = p_array->capacity;
    while (capacity < min_capacity) {
        capacity = (capacity + 1) * 1.5;
    }
    realloc(p_array, capacity * sizeof(float));
}

array_t *array_init(array_t *pArray, size_t capacity) { // version 3
    if (pArray != NULL) {
        if (capacity != 0) {
            pArray->data = malloc(sizeof(float[capacity]));
            pArray->count = 0;
            pArray->capacity = pArray->data != NULL ? capacity : 0;
        } else {
            pArray->data = NULL;
            pArray->count = 0;
            pArray->capacity = 0;
        }
    }
    return pArray;
}

void array_append(array_t *array, float value) {
    if (array->count >= array->capacity) {
        array_reserve(array, array->capacity + 1);
    }
    array->data[array->count] = value;
    array->count++;
}

void array_insert(array_t *array, int index, float value) {
    if (array->count >= array->capacity) {
        array_reserve(array, array->capacity + 1);
    }
    for (unsigned long i = array->capacity; i > (unsigned long) index - 1; --i) {
        float tempvalue = array->data[i];
        array->data[i + 1] = tempvalue;
    }
    array->data[index] = value;
    array->count++;
}

void array_remove(array_t *array, int index) {
    for (unsigned long i = index; i < array->count; ++i) {
        array->data[i] = array->data[i + 1];
    }
    array->count--;
}

int array_find(const array_t *array, float value) {
    for (unsigned long i = 0; i < array->count; ++i) {
        if (array->data[i] == value) {
            return i;
        }
    }
    return -1;
}

void input_grades(array_t *array) {
    printf("Grades:\n");
    int grade = 0;
    for (unsigned long i = array->count; i < array->capacity; ++i) {
        scanf("%d", &grade);
        array->data[i] = grade;
        array->count++;
    }
}

float average(array_t *array) {
    int total = 0, average = 0;
    for (unsigned long i = 0; i < array->count; ++i) {
        total += array->data[i];
    }
    average = total / array->count;
    return average;
}

int num_passed(array_t *array) {
    int passed = 0;
    for (unsigned long i = 0; i < array->count; ++i) {
        if (array->data[i] >= 5.5) {
            passed++;
        }
    }
    return passed;
}

void array_destroy(array_t *pArray) {
    if (pArray != NULL) {
        free(pArray->data);
        array_init(pArray, 0);
    }
}

## 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/).