# Week 2 - Dynamic Arrays
## Team
Team name: Gappies van andere wappies
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. |Stephan|
| **Spokesperson** communicates group’s questions and problems to the teacher and talks to other teams; presents the group’s findings. |Ingmar|
| **Reflector** observes and assesses the interactions and performance among team members. Provides positive feedback and intervenes with suggestions to improve groups’ processes. |Ingmar|
| **Recorder** guides consensus building in the group by recording answers to questions. Collects important information and data. |Stijn|
## 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 ✔️
````c
#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]);
}
}
````
### Activity 2: Array definition ✔️
```c
typedef struct array {
size_t capacity;
size_t count;
float *data;
} array_t;
```
The capacity is used to see how big the dynamic array is, the count is used to see how many elements are stored in the array, and the data is used for the information itself.
### Activity 3: Correct initialization ✔️
```C
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;
}
```
1 is incorrect, because: memory is not assigned to data
2 is incorrect, because: if the capacity == 0, you are easily able to write out of your memory bounds.
### Activity 4: Cleaning up ✔️
Program 2 is correct, and program 1 is incorrect.
Program 1 first allocates the array on the stack and then tries to frees it's memory on the heap using free. This crashes the program.
```c
array_t array; // Create memory on the stack
array_init(&array, 10);
array_destroy(&array);
free(&array); // Free memory that was not created by malloc?
```
### Activity 5: Resizing an array ✔️
https://stackoverflow.com/questions/1100311/what-is-the-ideal-growth-rate-for-a-dynamically-allocated-array
According to this question in stackoverflow, the typical/best growth rate is 1.5.
The new array reserve function:
```c
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;
}
float* new_data = realloc(p_array->data, sizeof(float) * capacity);
if(new_data != NULL) {
p_array->capacity = capacity;
p_array->data = new_data;
} else {
printf("Could not reallocate memory for array.");
}
}
```
Record your answer here
// 1.5 growth rate because it is more efficient
### Activity 6: Appending values ✔️
```c
void array_append(array_t* arr, float value) {
if(arr->count >= arr->capacity) {
// Array is full, reserve new memory for the array
array_reserve(arr, arr->capacity + 1);
}
// Set the data and increase the count
arr->data[arr->count++] = value;
}
```
### Activity 7: Inserting values ✔️
```c
void array_insert(array_t* arr, int index, float value) {
if(arr->count >= arr->capacity) {
// Array is full, reserve new memory for the array
array_reserve(arr, arr->capacity + 1);
}
for(size_t i = arr->count; i > index - 1; i--) {
arr->data[i + 1] = arr->data[i];
}
arr->data[index] = value;
arr->count++;
}
```
### Activity 8: Removing by index
```c
void array_remove(array * arr, int index);
```
for(int i=0; i <4; i++){
printf("%d\n" , arr[i]);
}
arr[index]=0;
for(int i=0; i <4 ; i++) {
arr[index] = arr[index + 1];
}
for(int i=0; i <3; i++){
printf("%d\n" , arr[i]);
}
}
Record your answer here
### Activity 9: Finding a value
```c
int array_find(const array * arr, float value);
```
Record your answer here
### Activity 10: Constant time complexity✔️
Constant time complexity notation: O(1)
Meaning: Every time a function with constant time complexity is called, the function will take approximately the same time, no matter the arguments or any other factors influencing the function.
Of the mentioned functions, append has a constant time complexity.
### Activity 11: Worst-case time complexity
| Operation | Worst-case time complexity |
| --------------- | -------------------------- |
| Insert | |
| Remove | |
| Find | |
| Lookup / access | |
Record your answer here
### Activity 12: Complexity of *append*✔️
The average/ amortized time complexity of an append operation to an array is O(1). This is significantly different from the O(N) worst-case time complexity. This is because most of the time, you will not have to copy over the array to a new location, instead just appending a value at the last element.
### Activity 13: Storing grades in a dynamically growing array
Record your answer here
## Looking back
### What we've learnt
- Dynamic arrays
- Difference stack and heap
- Time complexity
### 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/).
Sign in with Wallet
Connect another wallet