# Week 2 - Dynamic Arrays

## Team

Team name: FreeFlexers
Date:03/03/2022

Members

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

## 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] = 0;
    storage[0 + 1] = 1;

    for (int i = 2; i < count; i++) {
        storage[i] = storage[i - 1] + storage[i - 2];
    }
}

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

findings: *(someArray) is the same as someArray[0]
*(someArray + 1) is the same as someArray[1]

### 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;

Capacity- used to store size of array
Count- used to keep us on track and know which location we are at in the array
data- pointer to the chunk of memory of the array location

max values of size_t = 2^64 - 1.
maxvalues of float = 2^32

### Activity 3: Correct initialization

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;
    }

Version 3 seems to be the correct one.
Version 1 and 2 are incorrect because there is no explicit declaration for the malloc function. A void* is needed for it to work. Syntax: void *malloc(size_t size). Malloc is a function that is used to allocate memory at run time. It accepts an argument size and it is of type size_t. Size_t is defined as unsigned int in stdlib.h so it has to be included.

### Activity 4: Cleaning up

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

The program 2 is the correct one because it uses malloc to allocate memory dinamically then it uses free function to deallocate the memory.

### Activity 5: Resizing an array

void array_reserve(struct array *p_array, size_t min_capacity) {
    size_t capacity = p_array->capacity;
    while (capacity < min_capacity) {
        capacity = (capacity + 1) *1.5;
    }
    if (capacity == p_array->capacity) return;
    
    float * ptr = (float*)realloc(p_array->data,capacity);
    if (ptr != NULL) {
        p_array->data = ptr;
        p_array->capacity = capacity;
    }
}

### Activity 6: Appending values

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

### Activity 7: Inserting values

void array_insert(struct array * arr, int index, float value){
    array_reserve(arr, arr->count + 1);
    
    for(int i=arr->count;i> index;i--){
        arr[i]=arr[i - 1];
    }
 
    arr->data[index]=value;
   
}

### Activity 8: Removing by index

void array_remove(struct array * arr, int index){
    for(int i=index;i < arr->count;i++){
        arr[i]=arr[i+1];
    }

Record your answer here

### Activity 9: Finding a value

int array_find(const struct array * arr, float value){
    for(int i=0;i<= sizeof(arr);i++){
        if(arr->data[i]==value){
            return i;
        }else return -1;
    }
}

Record your answer here

### Activity 10: Constant time complexity
an algorithm has CTC If it takes the same time regardless of the number of inputs. 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*

Amortized time is the way to express the time complexity when an algorithm has the very bad time complexity only once in a while besides the time complexity that happens most of time. With Ammortized time, bad compleexity takes once in a while whilst the worst case time complexity means the maximum amount of time required for inputs of a given size.

Worst case time complexity of append: O(N)
Amortized complexity: O(1)

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

#include <stdio.h>
#include <stdlib.h>

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

void input_grades(array_t * grades);
float average(const array_t * grades);
int num_passed(const array_t * grades);

void array_destroy(array_t *grades);

array_t* array_init(array_t *grades, int size ){

if (grades != NULL) {
if (size != 0){
grades->data = (int*) calloc(size, size * 4);
grades->count = size;
grades->capacity = grades->data != NULL ? size * 4 : 0;
}
else{
grades->data = NULL;
grades->count = 0;
grades->capacity = 0;
}
}
return grades;
}
void input_grades(array_t * grades){
grades->data[0] = 1;
grades->data[1] = 20;
grades->data[2] = 30;
grades->data[3] = 10;
}
float average(const array_t * grades){
int sum = 0;
for (int i = 0; i < grades->count; ++i) {
sum += grades->data[i];
}
float average = sum / grades->count;
return average;
}

int num_passed(const array_t * grades){
int count = 0;
for (int i = 0; i < grades->count; i++){
if(grades->data[i] >= 5.5){
count++;
}
}
return count;
}
void array_destroy(array_t *grades){
if (grades != NULL){
free(grades->data);
array_init(grades, 0);
}
}

int main() {
array_t grades;
array_init(&grades, 4);
input_grades(&grades);
float avg = average(&grades);
int passed = num_passed(&grades);

printf("Average grade: %.2f\n", avg);
printf("%d out of %lu students passed\n", passed, grades.count);

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