# Week 2 - Dynamic Arrays

## Team

Team Name: Peach Technologies
Date: Wednesday 16 February 2022
|----------------------------------------------------------------------------|
Members:
Nafizul Habib Redwan
Siebe de Bruijn
Naomi Verschuur
Yazan Tayeh
|----------------------------------------------------------------------------|
Roles:
Facilitator: Nafizul Habib Redwan
Reflector: Yazan Tayeh
Spokesperson: Naomi Verschuur
Recorder: Siebe de Bruijn
|----------------------------------------------------------------------------|
| **Facilitator** keeps track of time, assigns tasks and makes sure all the group members are heard and that decisions are agreed upon. | |
| **Spokesperson** communicates group’s questions and problems to the teacher and talks to other teams; presents the group’s findings. | |
| **Reflector** observes and assesses the interactions and performance among team members. Provides positive feedback and intervenes with suggestions to improve groups’ processes. | |
| **Recorder** guides consensus building in the group by recording answers to questions. Collects important information and data. | |

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

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

typedef struct array
 {
 size_t capacity;
 size_t count;
 float *data;
 } array_t;
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 - min_capacity) < sizeof (float))
    {
        capacity = ( long long ) malloc(sizeof (float ));
    }
    }
int main() {
    printf("Hello, World!\n");
    return 0;
}

### Activity 2: Array definition
@NaomiVerschuur

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

Record your answer here:
The three fields in the array structure are capacity, count, and data.
In your log, describe what each of these fields is used for.
- Capacity --> The total number of elements that the array can contain without allocating new storage.
- Count --> is used to return the number of elements in an array.
- Data --> is a data structure consisting of a collection of elements, each identified by at least one array index or key. It is stored so that the position of each element can be computed from its index.

What is the maximum number of elements that can be stored in the array?
- 10000000

### Activity 3: Correct initialization
@yazantayeh

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

The third function definition is the correct one.
The reason why the 1st one is wrong, is because it doesn't use Malloc() to allocate memory for the capacity.
The reason why the 2nd one is wrong, is because it doesn't check if the capacity is a 0 and passes it to malloc() function

### Activity 4: Cleaning up
@sdbruijn

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 first program is wrong as it is trying to create arrayStruct on the same stack and then free it as if it was on the heap.

### Activity 5: Resizing an array
@Nafiz

Record your answer here#include <stdio.h>
#include <stdlib.h>

typedef struct array
 {
 size_t capacity;
 size_t count;
 float *data;
 } array_t;
void array_reserve(struct array *p_array, size_t min_capacity) {
     size_t capacity = p_array->capacity;
     while (capacity < min_capacity) {
         capacity = (capacity + 1) * 2;
         }
    if((capacity - min_capacity) < sizeof (float))
    {
        capacity = ( long long ) malloc(sizeof (float ));
    }
    }
int main() {
    printf("Hello, World!\n");
    return 0;
}

### Activity 6: Appending values
@NaomiVerschuur

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

typedef struct array
 {
 size_t capacity;
 size_t count;
 float *data;
 } array_t;
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 - min_capacity) < sizeof (float))
    {
        capacity = ( long long ) malloc(sizeof (float ));
    }
    }
void array_append(struct array * arr, float value)
{
    array_reserve(arr,10);
    arr->data = &value;
    
}
int main() {
    printf("Hello, World!\n");
    return 0;
};

Record your answer here:
Implement the append operation, using the prototype listed below. Make sure to call the array_reserve function in order to ensure that the capacity is sufficient to hold one extra element.

### Activity 7: Inserting values
@yazantayeh

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

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

### Activity 8: Removing by index
@sdbruijn

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

### Activity 9: Finding a value
@Nafiz

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

Record your answer here

### Activity 10: Constant time complexity
@yazantayeh

Constant time complexity is the time taken to perform an algorithm.
The worst-case time complexity is the "find" algorithm as it doesn't have a specific index that can be accessed.

### Activity 11: Worst-case time complexity
@NaomiVerschuur
Record your answer here:
How does the work that the operations must do in these worst case scenarios scale with the size (i.e., n - the number of elements contained in the array) of the array?

| Operation | Worst-case time complexity |
| --------------- | -------------------------- |
| Insert |Θ(n^2); The worst-case is when the array is full and needs to be expanded when inserting elements. At this time, you need to create an additional array and traverse the original array.|
| Remove |Θ(n); The item that needs to be deleted from the list can be anywhere in the list, there for a linear scan is necessary in order to find the item before it can be removed. Once the item is found it needs to be deleted, then all the remaining elements need to be shifted towards the left.|
| Find |Θ(n); The worst-case time complexity for find would be when there is only one thing that needs to be found withint the array. This causes the function to keep splitting the array in half, searching both halves to count how many copies are there of what is beaing searched. This ensures that every array is being looked at at least once.|
| Lookup / access |Θ(n); The worst- case is when the element is at last position or not in the array, therefore we have to traverse the whole array giving *n* of repetitions over loop.|

### Activity 12: Complexity of *append*
@sdbruijn

Record your answer here

### Activity 13: Storing grades in a dynamically growing array
@Nafiz
Record your answer here

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