# Week 2 - Dynamic Arrays
## Team
Team name: Beast from the East
Date:
Members : Nikola Zahariev, Casian Ionescu, Attila Poldan, Alexandra Melei
| Role | Name |
|-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|------|
| **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
````c=
#include <stdio.h>
#define COUNT (50)
void fill_fibonacci(unsigned long long * storage, int count)
{
storage[0] = 0;
storage[2] = 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
Since this is the first part of building this week's assignment, the code will be stored in task2.
```c=
typedef struct array
{
size_t capacity;
size_t count;
float *data;
} array_t;
```
Capacity: This is the number given to the struct for a maximum ammount of elemnets that it is able to store.
Count: Kepps track of which element is in which position in the array.
Data: This is the data stored in a given cell in the array.
### Activity 3: Correct initialization
```c=
array_t* array_init3(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;
}
```
Record your answer here
### Activity 4: Cleaning up
```c=
int main()
{
array_t *array = (array_t *) malloc(sizeof(array_t));
array_init3(array, 10);
// .... do some work ...
// finally, clean up
array_destroy(array);
free(array);
}
```
Record your answer here
### Activity 5: Resizing an array
```c=
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 /* insert your factor here */;
p_array =(array_t *)realloc(p_array,sizeof(array_t[capacity]));
}
/* reallocate memory, update capacity of array, etc. */
}
```
There's no such thing as an "ideal growth factor." It's not just theoretically application dependent, it's definitely application dependent.
2 is a pretty common growth factor - I'm pretty sure that's what ArrayList and List<T> in .NET uses. ArrayList<T> in Java uses 1.5. In conclusion the most common growth factors are 1.5 and 2
Record your answer here
### Activity 6: Appending values
```c=
void array_append(struct array * arr, float value)
{
if(arr->count <= arr->capacity)
{
array_reserve(arr,arr->capacity);
arr->capacity++;
}
auto lastIndex =arr->count;
arr->data[lastIndex-1] = value;
arr->count++;
}
```
Record your answer here
### Activity 7: Inserting values
```c=
//Activity 7
void array_insert(struct array * arr, int index, float value)
{
if(index > arr->capacity)
{
exit(EXIT_FAILURE);
}
array_append(arr,0);
for(int i = arr->count; i>= index;--i)
{
arr->data[i] = arr->data[i-1];
}
arr->data[index] = value;
}
```
Record your answer here
### Activity 8: Removing by index
```c=
//Activity 8
void array_remove(struct array * arr, int index, float value)
{
if(index > arr->capacity)
{
exit(EXIT_FAILURE);
}
for(int i = index; i>= arr->count;i++)
{
arr->data[i] = arr->data[i+1];
}
}
```
Record your answer here
### Activity 9: Finding a value
```c=
//Activity 9
int array_find(const struct array * arr, float value)
{
int i = 0;
while(i < arr->count)
{
if(arr->data[i] == value)
{
i = arr->count;
}
i++;
}
}
```
Record your answer here
### Activity 10: Constant time complexity
Record your answer here
Constant time complexity is when a function takes the same amount of time to be completed regardless of the input size.
Notation: O(1)
Insert and remove has the worst constant time complexity. This is due to the fact, when we insert/remove on a specified index, we have to shift the whole array to complete the operation.
### 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:
Worst case scenarios for insert/remove is when we preform the operation in the begining. Because we have to move the whole array after the insertion or deletion.
The worst case scenario for find is when the array does not contain the data we are looking for. Because of this we have to run through the whole array.
The worst case for lookup is a time constant. This is due to the fact that the data we are looking for is definitely in the array.
### Activity 12: Complexity of *append*
Record your answer here
The amortized time complexity is Θ(n).
This means that the average runtime is going to be situated between two constants,k1 and k2.
Where k1 is the time it takes to append normaly without resizing the array. We can get the time by multiplying with n (number of elements). k1*n is going to be our minimal time it will take for the operation to complete.
k2 is the time it takes to resize the array. This is going to be the maximum amount of time it could take to complete the append operation. Therefore the upper limit is going to be k2*n.
### Activity 13: Storing grades in a dynamically growing array
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?
Sign in with Wallet
Connect another wallet