---
# System prepended metadata

title: Untitled

---

﻿# Week 2 - Dynamic Arrays

## Team

Team name: FreeFlexers
Date:03/03/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.                                             |    Alex Stan  |
| **Spokesperson** communicates group’s questions and problems to the teacher and talks to other teams; presents the group’s findings.                                              | Kuda     |
| **Reflector** observes and assesses the interactions and performance among team members. Provides positive feedback and intervenes with suggestions to improve groups’ processes. | Luigi     |
| **Recorder** guides consensus building in the group by recording answers to questions. Collects important information and data.                                                   | Adriaan     |

## 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[0 + 1] = 1;

    for (int i = 2; i < count; i++) {
        storage[i] = storage[i - 1] + storage[i - 2];
    }
}

int main() {
    unsigned long long array[COUNT];
    fill_fibonacci(array, COUNT);
    for (int i = 1; i < COUNT; i++) {
        printf("f(%d) = %llu\n", i, array[i]);
    }
}
````
findings: *(someArray) is the same as someArray[0]
 *(someArray + 1) is the same as someArray[1]



### Activity 2: Array definition
This is how you include code listings in your markdown document:
```C
typedef struct array {
    size_t capacity;
    size_t count;
    float *data;
} array_t;
```
Capacity- used to store size of array
Count- used to keep us on track and know which location we are at in the array
data- pointer to the chunk of memory of the array location

max values of size_t = 2^64 - 1.
maxvalues of float = 2^32

### 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;
    }
```
Version 3 seems to be the correct one. 
Version 1 and 2 are incorrect because there is no explicit declaration for the malloc function. A void* is needed for it to work. Syntax: void *malloc(size_t size). Malloc is a function that is used to allocate memory at run time. It accepts an argument size and it is of type size_t. Size_t is defined as unsigned int in stdlib.h so it has to be included.


### Activity 4: Cleaning up

```c
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 program 2 is the correct one because it uses malloc to allocate memory dinamically then it uses free function to deallocate the memory.


### 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;
    }
    if (capacity == p_array->capacity) return;
    
    float * ptr = (float*)realloc(p_array->data,capacity);
    if (ptr != NULL) {
        p_array->data = ptr;
        p_array->capacity = capacity;
    }
}
```
### Activity 6: Appending values

```c
void array_append(struct array * arr, float value){
    array_reserve(arr, arr->count + 1);
    
    arr->data[arr->count] = value;
    arr->count++;
}
```

### Activity 7: Inserting values

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

```


### Activity 8: Removing by index

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

Record your answer here

### Activity 9: Finding a value

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

Record your answer here

### Activity 10: Constant time complexity
an algorithm has CTC If it takes the same time regardless of the number of inputs.  O(1)

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

### Activity 12: Complexity of *append*

Amortized time is the way to express the time complexity when an algorithm has the very bad time complexity only once in a while besides the time complexity that happens most of time. With Ammortized time, bad compleexity takes once in a while whilst the worst case time complexity means the maximum amount of time required for inputs of a given size.

Worst case time complexity of append: O(N)
Amortized complexity: 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 *grades);

array_t* array_init(array_t *grades, int size ){

    if (grades != NULL) {
         if (size != 0){
            grades->data = (int*) calloc(size, size * 4);
             grades->count = size;
             grades->capacity = grades->data != NULL ? size * 4 : 0;
              }
         else{
           grades->data = NULL;
            grades->count = 0;
            grades->capacity = 0;
             }
         }
     return grades;
    }
void input_grades(array_t * grades){
    grades->data[0] = 1;
    grades->data[1] = 20;
    grades->data[2] = 30;
    grades->data[3] = 10;
}
float average(const array_t * grades){
    int sum = 0;
    for (int i = 0; i < grades->count; ++i) {
        sum += grades->data[i];
    }
    float average = sum / grades->count;
    return average;
}

int num_passed(const array_t * grades){
    int count = 0;
    for (int i = 0; i < grades->count; i++){
        if(grades->data[i] >= 5.5){
            count++;
        }
    }
    return count;
}
void array_destroy(array_t *grades){
    if (grades != NULL){
        free(grades->data);
        array_init(grades, 0);
        }
    }

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


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