Algorhithms and Data Structures Week 1
# Week 1 Array

## Team

Team name:
Date: 12-02-2021

Members:
- Hlib H
- Kamicha G
- Zahir J
- Marco S

| Role | Name |
|-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|------|
| **Facilitator** keeps track of time, assigns tasks and makes sure all the group members are heard and that decisions are agreed upon. | Zahir J|
| **Spokesperson** communicates group’s questions and problems to the teacher and talks to other teams; presents the group’s findings. |Marco S|
| **Reflector** observes and assesses the interactions and performance among team members. Provides positive feedback and intervenes with suggestions to improve groups’ processes. | Hlib H|
| **Recorder** guides consensus building in the group by recording answers to questions. Collects important information and data. | Kamicha G|

## Activities

### Activity 1: Fixed-sized arrays

#### Advantages
- If you have an array with a fixed size than the program knows which memory it needs to allocate for this array.
- The search process can be applied to an array easily.

#### Disadvantages
- We must know in advance that how many elements are to be stored in array.
- If the size of the array changes, you would have to go into the source code to change all of the instances of it being used.

### Activity 2: Random access

- Random access is not necessary, when you are working with the array with only 1 element, because if you have only 1 element it doesn't matter, will you use sequential or random access it will be the same amount of time.

### Activity 3: The sizeof operator

- There are either 4 bytes or 8 bytes stored in a memory address. It depends on the architecture that your computer has.
- For 64 bit architecture it is 8 bytes and for 32 bit architecture it is 4 bytes.
- The size of the pointer doesn't depend on the type of the variable, because it has no connection with the type, because you are accessing the memory. The maximum memory address is different only if there are different computer architectures. For example, as we earlier said the size of the pointer in the 64 bit architecture is 8 bytes, and in the 32 bit - 4 bytes. It is because the maximum memory address in 64 bit architecture is more than 2^16 - 1. However, in 32 bit architecture the maximum memory address is less than 2^16 - 1, so it could be stored in 4 bytes.

### Activity 4: The sizeof operator and arrays

- The size of the array is 40 bytes in a 32 bit architecture.
- The size of the array is 80 bytes in a 64 bit architecture.

### Activity 5: Variables in function scope

Yes, this function works properly, because we assign an array to the pointer, so actually, we assign to the pointer the memory address of the array, so everything is ok

### Activity 6: Stack vs.Heap
Heap is a hierarchical data structure whereas Stack is a linear data structure. Stack memory is never fragmented, although Heap memory is fragmented when memory blocks are first allocated and then freed.Stack only accesses local variables, while Heap allows you to globally access variables.

### Activity 7: Using malloc

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

int* allocateMemory(int count) ;
int main()
{
    int * unsigned_long = malloc(sizeof(unsigned long)) ;
    int * float256 = malloc(256*sizeof(float)) ;
    int * int20 = allocateMemory(20) ;
    
    return 0 ;
}

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

### Activity 8: Limits of malloc
A single call to malloc can allocate 2 GB max in a single allocation. The maximum amount of space that can be allocated by multiple malloc calls is dependant on the operating system, RAM and disk space the user is using.

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

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

### Activity 10: Dangerous frees

int* ptr = (int*)123456789;
free(ptr);

int* null_ptr = NULL;
free(null_ptr);

this part of code returns 0 and gives neither warnings nor errors. I think that when we will try to do something with the value, stored at this memory address, we will have an error, which will return us something else, not 0, because we freed this memory address, so there is nothing now.

### Activity 11: Infinite memory?
By not freeing up dynamic memory that is no longer needed, the machine will take much longer to compute basic tasks. This is caused due to the frequent disk access and excess of virtual and physical memory. This action is called "thrashing" and action that would normally take a few microseconds would take up to tens of milliseconds.

### Activity 12: Resizing an Array

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

### Activity 13: Array insertion
- Increase the capacity of the array
- Iterate one index to the array
- Swapping of the elements to the their correct order.
- The worst case: [1 + capacity - index] steps

### Activity 14: Basic list operations

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

void array_append(Array *pArray, int element)
{
    if (pArray->capacity == pArray->count)
    {
        resize(pArray, pArray->capacity + 1) ;
    }
    *(pArray->values + pArray->count) = element ;
    pArray->count += 1 ;
}

void array_remove(Array *pArray, int index)
{
    int iterator ;
    for (iterator = index; iterator < pArray->count; iterator++)
    {
        array_swap(pArray, iterator, iterator + 1) ;
    }
    pArray->count-= 1 ;
    free(pArray->values + pArray->count) ;
}

void array_insert(Array *pArray, int index, int value)
{
    array_append(pArray, value) ;
    int iterator ;
    for (iterator = index; iterator < pArray->count; iterator ++)
    {
        array_swap(pArray, iterator, pArray->count - 1) ;
    }
}

void array_clear(Array *pArray)
{
    int capacity = pArray->capacity;
    int i;
    for (i = 0; i < pArray->count; i++)
    {
        free(pArray->values + i) ;
    }
    array_init(pArray, capacity) ;
}

void array_swap(Array *pArray, int index_a, int index_b)
{
    int buffer ;
    buffer = *(pArray->values + index_a) ;
    *(pArray->values + index_a) = *(pArray->values + index_b) ;
    *(pArray->values + index_b) = buffer ;
}

### Activity 15: Test your code

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

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

void array_init(Array *pArray, int capacity) ;
int* allocateMemory(int count) ;
void resize(Array *pArray, int newCapacity) ;
void array_append(Array *pArray, int element) ;
void array_clear(Array *pArray) ;
void array_remove(Array *pArray, int index) ;
void array_insert(Array *pArray, int index, int value) ;
void array_swap(Array *pArray, int index_a, int index_b) ;
void array_print(const Array * array) ;
void partition(Array *pArray) ;
int randomNumber(int min, int max) ;

int main()
{
    srand(42);
    Array array ;
    int size ;
    printf("Enter the size of the array:") ;
    scanf("%d", &size) ;
    array_init(&array, size) ;
    int index ;
    int i;
    for (i = 0; i < size; i++)
        array_append(&array, randomNumber(-100, 100));
    partition(&array) ;
    array_print(&array) ;
    return 0;
}

int randomNumber(int min, int max)
{
    return min + rand() / (RAND_MAX / (max - min + 1) + 1);
}

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

void array_append(Array *pArray, int element)
{
    if (pArray->capacity == pArray->count)
    {
        resize(pArray, pArray->capacity + 1) ;
    }
    *(pArray->values + pArray->count) = element ;
    pArray->count += 1 ;
}

void array_remove(Array *pArray, int index)
{
    int iterator ;
    for (iterator = index; iterator < pArray->count; iterator++)
    {
        array_swap(pArray, iterator, iterator + 1) ;
    }
    pArray->count-= 1 ;
    free(pArray->values + pArray->count) ;
}

void array_insert(Array *pArray, int index, int value)
{
    array_append(pArray, value) ;
    int iterator ;
    for (iterator = index; iterator < pArray->count; iterator ++)
    {
        array_swap(pArray, iterator, pArray->count - 1) ;
    }
}

void array_clear(Array *pArray)
{
    int capacity = pArray->capacity;
    int i;
    for (i = 0; i < pArray->count; i++)
    {
        free(pArray->values + i) ;
    }
    array_init(pArray, capacity) ;
}

void array_swap(Array *pArray, int index_a, int index_b)
{
    int buffer ;
    buffer = *(pArray->values + index_a) ;
    *(pArray->values + index_a) = *(pArray->values + index_b) ;
    *(pArray->values + index_b) = buffer ;
}

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

    printf("] (capacity: %d)\n", array->capacity);
}
void partition(Array *pArray)
{
    int current_index = 0;
    int max_index = pArray->count - 1;
    while (current_index <= max_index)
    {
        if (*(pArray->values + current_index) < 0)
        {
            int value = *(pArray->values + current_index) ;
            array_remove(pArray, current_index) ;
            array_insert(pArray, 0, value) ;
            current_index+= 1 ;
        }
        else
        {
            int value = *(pArray->values + current_index) ;
            array_remove(pArray, current_index) ;
            array_append(pArray, value) ;
            max_index-= 1 ;
        }
    }

}

### Activity 16: Solve the partitioning problem
The project group have done the algorithm that solves this problem, but when the code was put in the verify.c, it stopped working because of a mistake, possibly ,the problem could be in wrong array_clear function implemantation. The team will try to fix this, but if the code won't be fixed, here will be the code, which reads a size from the console and outputs array with the given size and random elements from -100 to 100 and after that the programm outputs the array with all the negative numbers on the left and all the positive numbers on the right.

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

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

void array_init(Array *pArray, int capacity) ;
int* allocateMemory(int count) ;
void resize(Array *pArray, int newCapacity) ;
void array_append(Array *pArray, int element) ;
void array_clear(Array *pArray) ;
void array_remove(Array *pArray, int index) ;
void array_insert(Array *pArray, int index, int value) ;
void array_swap(Array *pArray, int index_a, int index_b) ;
void array_print(const Array * array) ;
void partition(Array *pArray) ;
int randomNumber(int min, int max) ;

int main()
{
    srand(42);
    Array array ;
    int size ;
    printf("Enter the size of the array:") ;
    scanf("%d", &size) ;
    array_init(&array, size) ;
    int index ;
    int i;
    for (i = 0; i < size; i++)
        array_append(&array, randomNumber(-100, 100));
    array_print(&array) ;
    partition(&array) ;
    array_print(&array) ;
    return 0;
}

int randomNumber(int min, int max)
{
    return min + rand() / (RAND_MAX / (max - min + 1) + 1);
}

int* allocateMemory(int count)
{
    return malloc(count*sizeof(int)) ;
}
void array_init(Array *pArray, int capacity)
{
    pArray->capacity = capacity;
    pArray->values = allocateMemory(pArray->capacity);
    pArray->count = 0;
}
void array_clear(Array *pArray)
{
    free(pArray->values) ;
    array_init(pArray, pArray->capacity) ;
}
void resize(Array *pArray, int newCapacity)
{
    pArray->capacity = newCapacity;
    pArray->values = realloc(pArray->values, (pArray->capacity)*sizeof(int)) ;
}
void array_append(Array *pArray, int element)
{
    if (pArray->capacity == pArray->count)
    {
        resize(pArray, pArray->capacity + 1) ;
    }
    *(pArray->values + pArray->count) = element ;
    pArray->count += 1 ;
}
void array_remove(Array *pArray, int index)
{
    int iterator ;
    for (iterator = index; iterator < pArray->capacity; iterator++)
    {
        array_swap(pArray, iterator, iterator + 1) ;
    }
    pArray->capacity-= 1 ;
    free(pArray->values + pArray->capacity) ;
    pArray->count -= 1 ;
}

void array_insert(Array *pArray, int index, int value)
{
    array_append(pArray, value) ;
    int iterator ;
    for (iterator = index; iterator < pArray->capacity; iterator ++)
    {
        array_swap(pArray, iterator, pArray->capacity - 1) ;
    }
}
void array_swap(Array *pArray, int index_a, int index_b)
{
    int buffer ;
    buffer = *(pArray->values + index_a) ;
    *(pArray->values + index_a) = *(pArray->values + index_b) ;
    *(pArray->values + index_b) = buffer ;
}

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

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

void partition(Array *pArray)
{
    int current_index = 0;
    int max_index = pArray->capacity - 1;
    while (current_index <= max_index)
    {
        if (*(pArray->values + current_index) < 0)
        {
            int value = *(pArray->values + current_index) ;
            array_remove(pArray, current_index) ;
            array_insert(pArray, 0, value) ;
            current_index++ ;
        }
        else
        {
            int value = *(pArray->values + current_index) ;
            array_remove(pArray, current_index) ;
            array_append(pArray, value) ;
            max_index-- ;
        }
    }

}

## Look back

### What we've learnt

- During this week, we have learnt the basics of how to use heap dynamic memory allocation and what it is used for.
- We have learnt the sizeof arrays and pointers.
- We have learnt what a algorithm is supposed to do.

### What were the surprises

- The malloc fuction was surprising since we weren't sure what needed to be output with the function and for some of us it was the first time working with it.

### What problems we've encountered

- One of the problems we encountered was that when checking the size of the arrays is activity 3 or 4 we mistakingly checked the size of the pointers.
- At the basic list activities the description and the point of the function started getting more unclear as in what was supposed to do.

### What was or still is unclear

- Activity 12 to 14 , so array resizing and the basic list operation are still a bit unclear. We made function for them naturally and understand how they are supposed to work but we're still a bit uncertain if they work correctly as intended.
- Activity 16 is still unclear for now. While we also made a function for this one, we aren't sure on how to test it with the entire program as a whole, so we don't know if the function works or not.
- Activity 5 may also be a little bit unclear as in what we were exactly supposed to look for.

### How did the group perform?
- As a group we performed at our full potential. We worked together to achieve a common goal.
- The collaboration wasn't always perfect but it was good enough to do most of the activity.
- We would say that the online format was the number 1 reason for hick ups when it came to working on these activities.
- Communication is something that we hopefully try to improve the most for next time.

//How was the collaboration? What were the reasons for hick-ups? What worked well? What can be improved next time?