# Week 2 - Dynamic Arrays

## Team

Team name: Error
Date: 25-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. |Thanh Tran 516467|
| **Spokesperson** communicates group’s questions and problems to the teacher and talks to other teams; presents the group’s findings. |Hoang Minh Le 511907 |
| **Reflector** observes and assesses the interactions and performance among team members. Provides positive feedback and intervenes with suggestions to improve groups’ processes. |Hoa Than 487272 |
| **Recorder** guides consensus building in the group by recording answers to questions. Collects important information and data. | Kaloyan Zhekov 511216 |

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

#define COUNT (50)
void fill_fibonacci(unsigned long long * storage, int count) {
    //*storage = 0;
    storage[0] = 0;
    //*(storage + 1) = 1;
    storage[1]= 1;

    for (int i = 2; i < count; i++) {
        //*(storage + i) = *(storage + i - 1) + *(storage + i - 2);
        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;

Capacity : This is the capacity of the array
Count: This is to count the number of current element, if the number of element reach maximum of the capacity and still need to add more element, the array need to reallocate to get the desired memory.
*data: this is the pointer to the data array

### 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 1 is incorrect because it doesn’t allocate a memory block for the data.
Version 2 is incorrect because there is still an option that the initial capacity is 0. It does not mean out of memory, just simply there is no element can be stored in the array

### Activity 4: Cleaning up

// program 2
array_t *array=(array_t *)malloc(sizeof(array_t));
    array_init(array,10);
    /*fill the array*/
    for(int i=0;i<10;i++){
        array->count=i;
        for(int j=0;j<10;j++){
            array->data[j]=j;
        }
    }
    //finally,clean up
    array_destroy(array);
    free(array);

The 2nd program is correct. Because in the first program, the free() function cannot find the address of array in heap to deallocate
### Activity 5: Resizing an array

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;//Factor growth is 1.5
    }
    //reallocate memory, update capacity of array,etc
    p_array=realloc(p_array->data,capacity);
}

### Activity 6: Appending values

void array_append(array_t *arr,float value){
    //Increase the capacity of array
    array_reserve(arr,(arr->capacity));
    (arr->count)++;//increase number of element in float array
    array->data[count]=value;//append new element
}

### Activity 7: Inserting values

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

### Activity 8: Removing by index

void array_remove(struct array *arr, int index) {
    int *temp = malloc((arr->capacity - 1) * sizeof(int *));// allocate an array with a size 1 less than the current one
    memcpy(temp, arr, index - 1); // copy everything BEFORE the index
    memcpy(temp + (index * sizeof(int *)), temp + ((index + 1) * sizeof(int *)), arr->capacity - index); // copy everything AFTER the index
    free(arr); 
    arr->capacity = (size_t) temp;
}

### Activity 9: Finding a value

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

### Activity 10: Constant time complexity
The constant time complexity or constant worst-case time complexity is the time that the computer needs to calculate a number (in bits) of actions/codes in a program. It may be a simple number such as 1 or 2 or it could be a logarithmic or factorial number.

I think that the worst-case time complexity has the function remove, because it needs to find the index and the value stored in this index and then to remove it without damaging the rest of the array and shift back the indices to fill the removed index and value. These are comparatively many actions.

The syntax of the constant time complexity in Big O notation is O(n) where n is a number and could be replace by different functions of n such as log n or nx, or n

### Activity 11: Worst-case time complexity

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

### Activity 12: Complexity of *append*

Record your answer here
Worst-case time
The worst-case time complexity for appending an element to an array of length n, using this algorithm, is Θ(n).
If the array is full, the algorithm allocates a new array of length 2n, and then copies the elements from the old array into the new one.

Amortized time
An amortized time analysis gives a much better understanding of the algorithm.

Consider a sequence of n append operations, where we start with an array of length 1. A careful analysis shows that the total time of these operations is only Θ(n).

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

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

typedef struct array array;
typedef struct array
{
    size_t capacity;
    size_t count;
    float *data;
} array_t;
void input_grades(array * grades);
float average_grades(const array * grades);
int num_passed(const array * grades);

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

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

int main() {
    array_t grades;
    array_init(&grades, 4);
    input_grades(&grades);
    float average = average_grades(&grades);
    int passed = num_passed(&grades);
    printf("Average grade: %.2f\n", average);
    printf("%d out of %lu students passed\n", passed, grades.count);
    array_destroy(&grades);

}

void input_grades(array * grades){
    for(int i=0;i<grades->capacity;i++) {
        grades->count = i+1;//total students
        //random float numbers from 0.0 -> 10.0
        grades->data[i] = (float)rand()/(float)(RAND_MAX/10.0);
    }
}

float average_grades(const array * grades){
    float result;
    for(int i=0;i<=grades->capacity;i++){
        //sum of grades
        result = result + grades->data[i];
    }
    //average grades =
    return result/(grades->count);
}
int num_passed(const array * grades) {
    int passed = 0;
    for(int i=0;i<=grades->capacity;i++){
        //passed condition
        if(grades->data[i] >= 5.5){
            passed++;
        }
    }
    return passed;
}

## Looking back

### What we've learnt

•Be able to create and use a dynamically sized array in C.
•Understand the concept of random access.
• Understand the concept of time complexity.
• Know what the time complexities for basic array operations are.

### What were the surprises

Nothing

### What problems we've encountered

Nothing

### What was or still is unclear

Everything is clear

### How did the group perform?
The group worked perfectly

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