# Week 2 - Dynamic Arrays

## Team

Team name: Totally Useless Inc.
Date:16/02/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. |Adelina|
| **Spokesperson** communicates group’s questions and problems to the teacher and talks to other teams; presents the group’s findings. |Justas|
| **Reflector** observes and assesses the interactions and performance among team members. Provides positive feedback and intervenes with suggestions to improve groups’ processes. |Ines|
| **Recorder** guides consensus building in the group by recording answers to questions. Collects important information and data. |Tautvydas|

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

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

-The capacity of an array is the total number of cells you can use in this array.
-The size of an array is the number of cells that have data in them(the number of cells used out of the total capacity).
-The data of an array is the values or variables stored in each cell of the array. The array is a data structure consisting of a collection of elements identified by an index or key.

In theory, an upper limit is the maximum value representable by std::size_t. This value is implementation defined.
In practice, other limitations exist. It depends on the storage duration, and the system.

### Activity 3: Correct initialization

The correct initialization is the third one:

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

It is the correct initialization because the function initializes in the heap first checks if pArray is null and if it isn't it dynamically allocates memory in the heap. For the data as the malloc function can't have 0 passed to it there is a check to it and an else in case a 0 is passed to it.

array_t* array_init(array_t *pArray, size_t capacity) { // version 1
  if (pArray != NULL){
    float data[capacity];
    pArray->capacity = capacity;
    pArray->data = data;
    pArray->count = 0;
 }
  return pArray;
 }

The first version is incorrect due to the array being in the stack rather than the heap meaning that after the if statement it will no longer exist. It is not dynamic.

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

The second version of the code is incorrect simply because it is incomplete in the checking of whether or not the data is NULL.

### 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 right program is the one found above, program 2, because we want to create a dynamic array and in order to do that, we need to use the heap based array which is the one with dynamic memory allocation.

### Activity 5: Resizing an array

It was discovered that 1.5 is the typical growth rate of dynamically allocated arrays. Since realloc is a function that uses up relatively a lot of resources, it is resized using the growth rate to reduce the amount of times the realloc function is called. 2.0 is also used as growth rate, although 1.5 is the more efficient choice.

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;
    }
    p_array->data = (float *) realloc(p_array->data, sizeof(float) * capacity);
    p_array->capacity = capacity;
}

### Activity 6: Appending values

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

### Activity 7: Inserting values

void array_insert(array_t * arr, int index, float value){
    if (arr != NULL) {
        if (arr->data == NULL) {
            array_init(arr, index);
        }
        if (arr->capacity <= arr->count) {
            array_reserve(arr, (1 + arr->capacity));
        }
        for(int i = (int)(arr->count-1); i >= index-1; i--){
            arr->data[i+1]=arr->data[i];
        }
        arr->data[index-1]= value;
    }
}

### Activity 8: Removing by index

void array_remove(array_t * arr, int index){
    if(arr != NULL){
        if(arr->data == NULL){
            printf("There is nothing to remove, dumbo");
        }
        for(size_t i = index; i <= arr->count-1; i++){
            arr->data[i] = arr->data[i+1];
        }
    }
}

### Activity 9: Finding a value

#include <stdio.h>


int array_find(const float * arr, float value){
 int index=-1,element;
for (element=0;element<10;element++){
    if(*(arr+element)==value && index==-1){
        index=element;
    }
}
 return index;
}
int main(){
    const float numbers[10]={2,3,8,9,10,22,7,45,2,3};
    float x;
    int index;
    printf("enter the value you want to search for:\n");
    scanf("%f",&x);
    index=array_find(numbers,x);
    printf("the index of your value %f is: %d\n",x,index);
    return 0;

}

### Activity 10: Constant time complexity

Constant time complexity means that an algorithm takes the same amount of time run regardles of input size. For example, if it is needed to get the first item of an array, it will take the same amount of time whether there were 10 inputs or 1 thousand.

As a result, T(n) ∊ O(1). In other words it means that T(n) is smaller than some fixed constant, whose value isn't stated, for all large enough values of n. An algorithm with T(n) ∊ O(1) is said to have constant time complexity.

From lookup, append, insert, remove and find operations only append has a constant worst-case time complexity.

### Activity 11: Worst-case time complexity

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

### Activity 12: Complexity of *append*
The average case time complexity of the append opperation is amortized O(1) and it is different from the worst case time complexity because the worst case time complexity is O(n) which would mean that all the elements from the append function would be copied from "one room" to another, and that is a costly operation but on the other hand in the amortized time complexity we ignore the rare occasions and we ignore the multiplicative/divisive operations, we ignore constant terms making it 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 *pArray);
array_t* array_init(array_t *pArray, size_t capacity);


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

void input_grades(array_t * grades){
    for(size_t i = 0; i < grades->capacity; i++){
        printf("Please input the %zu grade: \n" , i);
        float value = 0;
        scanf("%f", &value);
        grades->data[i] = value;
        grades->count++;
    }
}

float average(const array_t * grades) {
    float sum = 0;
    for (int i = 0; i < grades->count; i++)
        sum += grades->data[i];
    return (sum / grades->count);
}

int num_passed(const array_t * grades){
    int passed_number = 0;
    for(int i = 0; i < grades->count; i++){
        if(grades->data[i] >= 5.5){
            passed_number++;
        }
    }
    return passed_number;
}

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

array_t* array_init(array_t *pArray, size_t capacity){
    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;
}

## Looking back

### What we've learnt

The concept of time complexity.
How to create a dinamically sized array.

### What were the surprises

* We didn't encounter any surprises, we actually used some of last week's knowledge and tried to solve the new activities with the same strategy.

### What problems we've encountered

#### Activity 3:
* Encountered problems with finding the right initialisation out of the three given.
#### Activity 6:
* We had problems with understanding the reallocation.

### What was or still is unclear

* What is still unclear for our group is the time complexity.

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

* The holidays actually disrupted us since each one went to a different country or place so we ended up doing everything last minute.
* For the next time, we should start earlier and work on everything together and not divide all of the tasks the same way we have been doing.
* Better communication between team members while working on the tasks.