# Week 1 Array

## Team

Team name: Group 2
Date: 8-2-2021

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. | Cas Serrarens |
| **Spokesperson** communicates group’s questions and problems to the teacher and talks to other teams; presents the group’s findings. | Sam Spence |
| **Reflector** observes and assesses the interactions and performance among team members. Provides positive feedback and intervenes with suggestions to improve groups’ processes. | Onurkan Kanli |
| **Recorder** guides consensus building in the group by recording answers to questions. Collects important information and data. | Wybren van den Akker |

## Activities

### Activity 1: Fixed-sized arrays

**Advantages**
Fixed-sized arrays are great for buffers. If input data from a user (for example) is larger than the buffer, any excess data is not stored. This is a lot safer than just storing any input as:
1. You know the exact size of the array. (Which is guaranteed to house the exact number of elements you need)
2. You will be able to guarantee that your memory wont overflow if users add more data.

All the elements in an array are neatly structured together so its easy for the processor to request it without having to look up all the individual elements.

**Disadvantages**
However if you do want to store more information than the initialized array size, you wont be able to store it. Fixed-size arrays are not resizeable.

### Activity 2: Random access

Random access is not neccesary when you only want to read the array in one direction (i.e. first to last element, or reversed). In this case we are just moving from element 0 to 1, to 2, to 3, etc which means we dont need to randomly access our elements. A better data structure in this case would be a Queue or a Stack.

### Activity 3: The sizeof operator

In C, the size of a pointer is 2 bytes. The size does not depend on its type as it will always be pointing to an address in memory, this address' size does not increase when the variable type's size does.

### Activity 4: The sizeof operator and arrays

The size of an array depends on the amount of elements and the size of the data type. For example, this array: `int array[10]` has either 40 or 80 bytes (depending on if the operating system is 32-bits or 64-bits.) while this array `char array[10]` only has 10 bytes.

### Activity 5: Variables in function scope

This function won't work properly. As the method finishes initializing the structure, the temporary variable/array `int values[capacity]` will be discarded by the garbage collector. This is because the variable was declared within the method's scope.

This becomes a problem when you try to add anything to the now "initialized" array, because we assigned the `int *values` a *pointer* to the now deleted variable/array.
Instead you will have to dynamically allocate a block of memory with `malloc()`.

### Activity 6: Stack vs. heap

Stack memory's name is derived from where it is allocated: A method's callstack. Stack memory is automatically allocated/deallocated whenever a method is called and a programmer does not need to worry about deallocating it themselves. The stack is only supposed to be used for short term - temporary values.
It is a *lot* faster than the heap.

If a user allocates too much memory on the stack there is a good chance they will trigger a `StackOverflow` error which will crash your program (This is where the name for the website comes from)

Heap memory's name comes from it litterally being a "heap" or pile of memory available to the programmer. This memory is not used by declaring variables within methods (as these are allocated to the Stack). Instead, you need to allocate blocks of memory yourself using methods such as `malloc()`. It is also the programmers responsibility to then deallocate this memory when it is not needed anymore. If you don't do this you will get memory leaks, which can crash your program if allowed to persist for prolonged periods of time. (Your program will quite literally run out of memory.)

The largest difference between stack and heap memory is the size. Stack memory can be seen as a `Last in - First out` Array. (more accurately a Stack datastructure) This stack array is a lot smaller than the heap.

### Activity 7: Using malloc

And that's how you insert code blocks:

unsigned long* uLong = malloc(sizeof(unsigned long));
float* floats = malloc(sizeof(float) * 256);

int* AllocateMemory(int count)
{
    return malloc(sizeof(int) * count);
}

### Activity 8: Limits of malloc

`malloc()` Is only limited by two things:
1. The amount of memory available (depends on your system)
2. The maximum possible size of an object (size_t) which depends on if your architecture is 32 or 64-bit. (The max value is 2^[your architecture bits])

In our case, the maximum possible allocation is 18446744073709551615 bytes, or 16 Exabytes (2^64)-1

### Activity 9: Creating an array with dynamic capacity

void array_init(Array *pArray, int capacity)
{    
    pArray->capacity = capacity;
    pArray->values = malloc(sizeof(int) * capacity);
    pArray->count = 0;
}

### Activity 10: Dangerous frees

Freeing a pointer that was not obtained by `malloc()`, for example `int* ptr = (int*)54;`, will return this error code: `(0xC0000005)`. This is an Access Violation.
What happens is that you're trying to free memory allocated on the *Stack* while `free()` should be used for memory allocated on the *Heap*.

Freeing a NULL pointer however will not result in any action, so it is perfectly safe to do so. (It is also good practice not to check for NULL when calling free because of this.)

### Activity 11: Infinite memory?

Not freeing your memory will result into what's called a Memory Leak. Not freeing your memory will mean it persists on the stack until the program closes (or crashes).
If you keep allocating memory but not freeing it (leaking memory) your program will eventually be killed by your OS and essentially crash.

### Activity 12: Resizing an Array

int clamp(int min, int max, int num)
{
    if (num < min)
    {
        num = min;
    }
    else if (num > max)
    {
        num = max;
    }
    return num;
}

void resize(Array *pArray, int newCapacity)
{
    pArray->capacity = newCapacity;

    pArray->values = realloc(pArray->values, sizeof(int) * newCapacity);
    pArray->count = clamp(0, newCapacity, pArray->count);
}

### Activity 13: Array insertion

Get the element value which needs to be inserted.
Get the position value.
Check whether the position value is valid or not.
If it is valid, Shift all the elements from the last index to position index by 1 position to the right. Insert the new element in arr[position]

Whenever new element is inserted to the array new element is going to be stored in +1 to the current position. If we want to remove already added element to the array it has to -1 to the current position. Worst case number of steps are if the element which needs to be deleted is present in arr[0], we need to shift all the elements from index 1 to size - 1 by position to the left. So it will take N - 1 iteration. For example, if the array has 100 elements the for loop will work for 99 times.

### Activity 14: Basic list operations

void double_size(Array *pArray) {
    resize(pArray, pArray->capacity * 2);
}

// append an element to the end of an array
void array_append(Array *pArray, int element) {
    if(pArray->count == pArray->capacity)
        double_size(pArray);// doubling is less memory efficient, but more performance efficient
    pArray->values[pArray->count] = element;
    pArray->count++;
}

// remove an element from the array at index
void array_remove(Array *pArray, int index) {
    //loop over each element after `index` copying it to the previous index
    // at the end of the array 'de-allocate' the last element
    for(int i = index; i < pArray->count; i++) {
        pArray->values[i] = pArray->values[i+1];
    }
    pArray->count--;
    if (pArray->count <= pArray->capacity / 2)
    {
        resize(pArray, pArray->capacity / 2);
    }
}

// remove all elements
void array_clear(Array *pArray) {
    pArray->count = 0;
}

// insert an element into the array, before index
void array_insert(Array *pArray, int index, int value) {
    if(pArray->count++ >= pArray->capacity) double_size(pArray);
    for(int i = pArray->count-1; i >= index; i--) {
        pArray->values[i+1] = pArray->values[i];
    }
    //pArray->count++;
    pArray->values[index] = value;
}

// swap the two elements located at indices index_a and index_b
void array_swap(Array *pArray, int index_a, int index_b) {
    int c = pArray->values[index_a];
    pArray->values[index_a] = pArray->values[index_b];
    pArray->values[index_b] = c;
}

### Activity 15: Test your code

[0] (capacity: 4)
[0, -1] (capacity: 4)
[0, -1, -2] (capacity: 4)
[0, -1, -2, -3] (capacity: 4)
[0, -1, -2, -3, -4] (capacity: 8)
[0, -1, 42, -2, -3, -4] (capacity: 8)
[0, -1, 42, -3, -4] (capacity: 8)
[0, -3, 42, -1, -4] (capacity: 8)

Results are as expected.

### Activity 16: Solve the partitioning problem

While attempting to benchmark our solution we ran into a slight problem. I don't have access to the `sys/time.h` library. I found that it is only supported on GNU family compilers and is technically a Linux based library. perhaps use `clock_gettime()`?

This is our solution for partitioning:

//rearranges the contents of the array in such a way that all negative numbers precede all positive
//numbers. The number zero (0) is considered to be a positive number in this case.
void partition(Array *pArray) {
    //printf("partitioning\n");
    //take all negative numbers out
    Array negative;
    array_init(&negative, pArray->count);
    //take all positive numbers out
    Array positive;
    array_init(&positive, pArray->count);
    for(int i = 0; i < pArray->count; i++) {
        (pArray->values[i] >= 0) ? array_append(&positive, pArray->values[i]) : array_append(&negative, pArray->values[i]);
    }
    //combine into new array in order
    int count = pArray->count;
    array_clear(pArray);
    for(int i = 0; i < count; i++) {
        (i < negative.count) ? array_append(pArray, negative.values[i]) : array_append(pArray, positive.values[i-negative.count]);
    }
}

|Array length |Runs |Avg.time (ms) |Relative time
|---------------------|-------|----------------|-------------
|1000000 |100 | 17.44 | 1.00
|2000000 |100 | 34.45 | 1.98
|3000000 |100 | 51.82 | 2.97
|5000000 |100 | 92.26 | 5.29

The run time scales linearally with the length of the array.

## Look back

### What we've learnt

(Cas): What I've learned is that there is a lot more to arrays and memory than I knew. I've learned that you have to look closely at memory when writing a program. When allocating memory, it is important to know if that memory is cleared after you're not using it anymore. I've also learned a lot more about arrays. I've learned that it is possible to change the capacity of an array according to the elements that are in the array. I think that's what called a "list".

(Onurkan) I’ve learnt that arrays and memory are much more detailed. I’ve learnt that stack is used for static memory allocation and Heap for dynamic memory allocation. I’ve learnt about malloc function and malloc function is a function which is used to allocate a block of memory dynamically. I've learnt that not freeing your memory may cause your program to crash.

### What were the surprises

(Cas): I was surprised that there is a way to change the size of an array according to amount of elements that the array contains and that you can change the amount of memory that has to be allocated in order to make the array work.

(Onurkan) I was very suprised that programmers dont have to free stack memory because stack is not permanently so memory block is going to be removed automaticly from the memory. I didnt know that it is possible to change the size of an array so i was very suprised with that.

(Wybren) I was very surprised when I learned the max allocation size of the `malloc()` call. I hadn't even thought of a maximum but when I learned it was 16 Exabytes (2^64)-1 I was kind of shocked. (Also realized theres absolutely no need to worry about max allocation size haha)

(Sam) I was surprised that memory reallocation was possible without having to manually copy the data over.

### What problems we've encountered

(Cas): The problem that i've encountered that, aside from my group members, I still have to learn a lot about how to code and how to start working on something.

(Onurkan) I had to do research to understand the tasks and to follow the activities. I had problem while using malloc function so I had to understand how to work with malloc function properly.

(Wybren): The provided verify.c file didnt compile for us which was a shame. I would have liked to test our implementations.

### What was or still is unclear

(Cas): It was unclear to me how to properly use the ``malloc()`` function and how to use the pointers in this function. My groupmembers did a really good job of explaning it to me. Now I know a lot more about this subject.

(Onurkan) For me clamp method was not clear. But hopefully my team mates was very kind so that they helped me to understand that clamp method is used for making sure that count value is within range of our new maximum capacity.

### How did the group perform?

The work in our group was very easy going. 2 of our group members are very good programmers already and were able to inform the rest of the group about what they were doing. Role assignment was done very quick and working together was going great.

The problems we encountered was that the other 2 group members were having trouble keeping up with the pace the other 2 group members had when doing the assignments.

Role assignment was quick and easy. Working on the assignments and the communication was good. We finished the assignments in time and before the weekend. This was also decided when we started working. We wanted to be done before the weekend.

In the upcoming assignments, it is better to start working on it sooner. Also, the assignments could be divided among the group members. This time we did almost everything together.