# Week 1 Array

## Team

Team name: Group One
Date: Monday 15^th^ February

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

## Activities

### Activity 1: Fixed-sized arrays

**Advantage:** Allocating more memory than required leads to waste of memory space, to prevent this we use fixed-sized arrays
**Disadvantage:** No flexibility

**Use case:** When a password with a max length must be stored using a char array. Will prevent errors further down the line.

### Activity 2: Random access

When you don't have to access at a certain index in the array.

### Activity 3: The sizeof operator

int *pointer;
printf ("size of %d", sizeof(pointer));

The size of a pointer does not depend on its type, the reason for this is because a "memory address" specifies the location of one byte - which is 8 bits.

### Activity 4: The sizeof operator and arrays

int array[10];
size_t size = sizeof(array) / sizeof(array[0]);
printf("The size of the array is %d", size);

When the above code is run, an output of 10 bytes is given.

### Activity 5: Variables in function scope

The function compiles without errors and/or warnings. We think the function would work as an initiator of the array but not as a way to fill the array. A separate fucntion would need to be created.

### Activity 6: Stack vs. heap

Stack is a linear data structure whereas Heap is a hierarchical data structure, stack accesses local variables only which cannot be resized while Heap allows you to access variables globally which can be resized. Stack allocation and deallocation are done by compiler instructions whereas Heap allocation and deallocation is done by the programmer. In addition, stack memory will never become fragmented whereas Heap memory can become fragmented as blocks of memory are first allocated and then freed.

### Activity 7: Using malloc

//Allocate unsigned long
unsigned long *uLongNumber = malloc(sizeof(unsigned long));

//Allocate 256 float
int iNumber = sizeof(float);
float *fNumber; 
fNumber = malloc(iNumber * 256);

//Function that returns pointer
int* allocatedMemory(int count){
    int intSize = sizeof(int);
    int *intptr;
    intptr = malloc(intSize * count);
    return intptr;
}

### Activity 8: Limits of malloc

Malloc takes a size_t, which can thus be up to SIZE_MAX. In a 32-bit system this can be 2^32^ bytes and on a 64-bit system this can be 2^64^ bytes.

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

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

### Activity 10: Dangerous frees

When compiling the code no errors or warnings are shown. But, when run, the code exits with an ugly return of -1073740940 (0xC0000374). Probably overflows. No operation is performed on a pointer with the value NULL using free.

### Activity 11: Infinite memory?

We think that once the IDE is closed all the allocated memory is reclaimed. So, it will only affect your program when running it. Longer times, slower responses, etc.

### Activity 12: Resizing an Array

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

### Activity 13: Array insertion

1. Know at which index the element is to be insterted.
2. All indexes, after the index at which the element is to be insterted, should be incremented by one.
### Activity 14: Basic list

//append an element to the end of an array
void array_append(Array *pArray, int element)
{
    pArray->capacity = pArray->capacity + 1;
    pArray->values[pArray->count + 1] = element;

    pArray->count += 1;


}

//remove an element from the array at index
void array_remove(Array *pArray, int index)
{
    free(pArray->values[index]);

    for(int i = index + 1; i <= pArray->count; i++)
    {
        pArray->values[i] -= 1;
    }
}

//remove all elements
void array_clear(Array *pArray)
{
    free(pArray);
}

//insert an element into the array, before index
void array_insert(Array *pArray, int index,int value)
{
    pArray->capacity = pArray->capacity + 1; // capacity = 10+1 since we insert element
    for (int i = pArray->capacity; i >= index; i--) // 11; 11 >= index; 11--
    {
        pArray[i] = pArray[i - 1];
    }
    pArray[index - 1] = 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 temp;
    temp = pArray->capacity[index_a];
    pArray->capacity[index_a] = pArray->capacity[index_b];
    pArray->capacity[index_b] = temp;
}

### Activity 15: Test your code

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

typedef struct Array_T
{
    int capacity;
    int count;
    int *values;
} Array;

void initArray(Array *pArray, int capacity)
{
    int values[capacity];
    pArray->capacity = capacity;
    pArray->values = values;
    pArray->count = 0;
}

//append an element to the end of an array
void array_append(Array *pArray, int element)
{
    pArray->capacity = pArray->capacity + 1;
    pArray->values[pArray->count + 1] = element;
    pArray->count += 1;
}

//remove an element from the array at index
void array_remove(Array *pArray, int index)
{
    free(pArray->values[index]);

    for(int i = index + 1; i <= pArray->count; i++)
    {
        pArray->values[i] -= 1;
    }
}

//swaping elements in array
void array_swap(int index){
    int temp;
    int array;
    for(int i=0;i < index; i+=2)
    {
        temp = array[i];
        array[i] = array[i+1];
        array[i+1]= temp;
    }

//remove all elements
void array_clear(Array *pArray)
{
    free(pArray);
}

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


void array_print(const Array *array)
{
    printf("[");
    if( array->count > 0)
    {
        printf("%d", array->values[0]);
    }
    for(int i = 1; i < array->count ; i++)
    {
        printf(", %d", array->values[i]);
    }

    printf("] (capacity: %d)\n", array->capacity);
}

int main()
{
    Array array;
    initArray(&array, 4);
    array_append(&array, 0);
    array_print(&array);//expected result:[0](capacity:4)
    array_append(&array, -1);
    array_print(&array);//expected result:[0,-1](capacity:4)
    array_append(&array, -2);
    array_print(&array);//expected result:[0,-1,-2](capacity:4)
    array_append(&array, -3);
    array_print(&array);//expected result:[0,-1,-2,-3](capacity:4)
    array_insert(&array, 4, -4);
    array_print(&array);//expected result:[0,-1,-2,-3,-4](capacity:X←-)
    array_insert(&array, 2, 42);
    array_print(&array);//expected result:[0,-1,42,-2,-3,-4]
    array_remove(&array, 3);
    array_print(&array);//expected result:[0,-1,42,-3,-4]
    array_swap(&array, 1, 3);
    array_print(&array);//expected result:[0,-3,42,-1,-4]

    return 0;
}

When running the above program there are a lot of errors. Unfortunatly we don't understand why it's giving all these errors. We've tried to get it running but we can't seem to get it to work.
### Activity 16: Solve the partitioning problem

void partition(Array *pArray)
{
    int key, j;
    for (int i = 1; i < pArray->capacity; i++) {
        key = pArray[i];

        if (key > 0)
            continue;
 
        j = i - 1;
        while (j >= 0 && pArray[j] > 0) {
            pArray->values[j + 1] = pArray->values[j];
            j = j - 1;
        }
        
        pArray->values[j + 1] = key;
}

| Array length | Runs | Avg. times (ms) | Relative time |
| ----- | ---- | --- | ------------- |
| 9 | x | x | x |
| 10 | x | x | x |
| 11 | x | x | x |
| 12 | x | x | x |

As the length of the array increases there are more and more numbers to sort through. If the array increases by one then the loop looking through the array will have to look at one extra element.

Unfortunatly we were unable to fill in the table completly because our program was not working. We did however manage to create a partioning algorithm for another array, see code below:

#include <stdio.h>

void printArray(int arr[], int n)
{
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

void rearrangePosNeg(int arr[], int n)
{
    int key, j;
    for (int i = 1; i < n; i++)
    {
        key = arr[i];

        if (key > 0)
            continue;

        j = i - 1;
        while (j >= 0 && arr[j] > 0)
        {
            arr[j + 1] = arr[j];
            j = j - 1;
        }

        arr[j + 1] = key;
    }
}

int main()
{
    int arr[] = {-12, 11, -13, -5, 6, -7, 5, -3, -6};
    int n = sizeof(arr) / sizeof(arr[0]);

    rearrangePosNeg(arr, n);
    printArray(arr, n);
    //showing size of array
    printf("%d", n);

    return 0;
}

## Look back

### What we've learnt?

Understand the basics, also the principles of memory allocation. We also understand how arrays work. We also learned how to use malloc and free functions to manage memory. All in all, even with our program not working as intended, we still believe we learnt a great deal. We discovered the difference between a static and dynamic container for elements. We found out that some arrays are seen as linear data structures and others are not.

We also learned that it's important to check if individual functions would work in conjunction with other functions before combining them as a whole.

### What were the surprises?

The overall program was larger than what we expected. Our thoughts were more along the lines of creating separate alogorithms and small functions. Instead we found that everything needed to be combined.

### What problems we've encountered?

Struggling at using the sizeof operator to find out what the size of array is (activity 4, but solved). Activity 14: As individual functions we think they will work. As a whole the functions are not working together the way we want. The program we have created in Activity 15 produced lots of errors.

Our group found the way of programming druing this week slightly inconvenient. Having to make loose functions and then combining it all into one program gave us lots of problems.

### What was or still is unclear?

In Activity 15, we don't understand why we have these certain errors. Having to backtrack to all the loose funtion to find the problems proved difficult. This affected solving activity 16 since it relies on the code from the previous activities. Thus, creating a kind of domino effect for our group, as soon as one thing didn't work everything was not going to work.

### How did the group perform?

All things considered, we think we learnt a good deal about the topic. Sometimes it was a little difficult to arrange meetings for when everyone was available. Other than that, we are pleased with the knowledge we acquired.

We should do more research about memory since each member in the group have little or no experiences on the subject.