# Week 1 Array

## Team

Team name: Group 3
Date: 12/02/2021

## Members
Yordan Ivanov
Len Bauer
Oduche Ijeoma JF
Pedro Sousa Garcia

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

## Activities

### Activity 1: Fixed-sized arrays

Advantage:
* You know how much memory to allocate to variables.
* You are able to limit user input into memory.
* More memory and CPU efficient

Disadvantage:
* You can't use them for user input unless you are aware of the size it will need to be.
* Once declared the size of the array cannot be modified. The memory which is allocated to it cannot be increased or decreased.
* Allocating more memory than the requirement leads to wastage of memory space and less allocation of memory also leads to a problem.

Use Case:
* Limits user input to 280 characters (Twitter)
* A program that uses the alphabet or anything with a fixed value
* Storing deck of cards

### Activity 2: Random access
Use case:
* Random Access would not be neccesarry when working with a tape drive, where the device must move the tape's ribbon forward or backward to reach the desired information.
* Music playback where you want the order
* A clock

### Activity 3: The sizeof operator
How many bytes are used to store a memory address?
* 8 bytes if 64 bit computer
* 4 bytes if 32 bit computer

Does the size of the pointer depend on the type?
* Size of pointer does not depend on type it depends on address

Why?
* Depending on your cpu architecture and operating system the size of the pointer adders can be calculated by taking the size of the computer architecture.

#include <stdio.h>

int main(void)
{
    printf("The size of an int pointer is %ld bytes!\n", sizeof(char *));
    printf("The size of a char pointer is %ld bytes!\n", sizeof(int *));
    printf("The size of a short pointer is %ld bytes!\n", sizeof(short *));
    printf("The size of a long pointer is %ld bytes!\n", sizeof(long *));
    printf("The size of a float pointer is %ld bytes!\n", sizeof(float *));
    printf("The size of a double pointer is %ld bytes!\n", sizeof(double *));
    printf("The size of a void pointer is %ld bytes!\n", sizeof(void *));
    return (0);
}

The size of an int pointer is 8 bytes!
The size of a char pointer is 8 bytes!
The size of a short pointer is 8 bytes!
The size of a long pointer is 8 bytes!
The size of a float pointer is 8 bytes!
The size of a double pointer is 8 bytes!
The size of a void pointer is 8 bytes!

Process finished with exit code 0

### Activity 4: The sizeof operator and arrays

* 40 bytes

### Activity 5: Variables in function scope

* Yes because you are pointing a pointer to the referance of an array.

### Activity 6: Stack vs. heap

* Stack is a linear data structure, whereas Heap is a hierarchical data structure. Stack can only access local variables, while Heap allows you to access variables globally.
* The stack is faster because the access pattern makes it trivial to allocate and deallocate memory from it.

### Activity 7: Using malloc

Using the malloc function to:

//allocate memory to store one unsigned long number,
unsigned long *number = malloc(sizeof(unsigned long));


//allocate memory to store 256 float numbers,
float *number;
number= malloc(256 * sizeof(float));


//function that takes a count as its argument and allocates enough memory,
int* allocateM(int count){
    int* pCount ;
    pCount= malloc(count* sizeof(int)); 
    return(*pCount);

int main()
{
   int input;
   printf("Please enter a value: ");
   scanf("%d", &input);
   printf("Returned Pointer: %p", allocateM(input));
    return 0;
}

### Activity 8: Limits of malloc
* You can allocate as much memory as you want. It is system dependent.

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

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

### Activity 10: Dangerous frees
**Without malloc**: Tries to free all memory and can exibit indefinite behavior causing a system crash.

**NULL**: If ptr is NULL, no operation is performed. On older version of C it tries to free empty memory and could cause system crash as well.

### Activity 11: Infinite memory?
Generally it is just good practice as most opperating systems reclaim memory after programm exit. However it could cause the system to run out of memory and crash.Failure to deallocate memory using free leads to buildup of non-reusable memory, which is no longer used by the program. This wastes memory resources and can lead to allocation failures when these resources are exhausted.

### Activity 12: Resizing an Array

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

### Activity 13: Array insertion
**Steps**:
* Rezise array by how many values are inserted if the max capacity has been reached.
* Shift array from where the value is inserted.
* assign a vale to the selected index position in the array

worst case depends on how many elements are being inserted.

### Activity 14: Basic list operations

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

// remove an element from the array at index
 void array_remove(Array *pArray, int index)
{
    int i;
    if(index >= 0 || index <pArray->count){
        for(i=index; i<(pArray->count)-1; i++){
            pArray->values[i]= pArray->values[i + 1];
        }
    }
    pArray->count--;
}


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

    int index;
    for(index=1;index<pArray->count;index++){
        if(pArray->count!=1){
            array_remove(pArray,index);
        }
        else{
            pArray->values[index]=0;
        }
        pArray->count=0;
    }
}

// insert an element into the array, before index
 void array_insert(Array *pArray, int index, int value)
{
    int i;
    int newCapacity;
    if (pArray->count==pArray->capacity){
        newCapacity=2* pArray->capacity;
        resize(pArray,newCapacity);
        pArray->count++;
    }
    else{
        pArray->count++;
    }
    for (i = pArray->count-1; i >index ; i--){
        pArray->values[i] = pArray->values[i - 1];
    }
    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 temp;
    temp=pArray->values[index_a];
    pArray->values[index_a]=pArray->values[index_b];
    pArray->values[index_b]=temp;
}

### Activity 15: Test your code

#include <stdio.h>
#include <stdlib.h>
typedef struct
{
    int capacity;   // max. number of elements that can be stored
    int count;      // actual number of elements stored
    int* values;    // pointer to stored elements
} Array;

void array_print(const Array * array);
void resize(Array *pArray, int newCapacity);
void array_init(Array *pArray, int capacity);
void array_append(Array *pArray, int element);
void array_remove(Array *pArray, int index);
void array_clear(Array *pArray);
void array_insert(Array *pArray, int index, int value);
void array_swap(Array *pArray, int index_a, int index_b);
void memory_free ( Array *pArray);

int main()
{
    Array array;
    array_init(&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]
    memory_free(&array);
    return 0;
}

// initializes an array with the given capacity
void array_init(Array *pArray, int capacity)
{
    pArray->values =malloc(sizeof(int)*capacity);
    pArray->count = 0;
    pArray->capacity = capacity;
}

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

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

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

// remove an element from the array at index
void array_remove(Array *pArray, int index)
{
    int i;
    if(index >= 0 || index <pArray->count){
        for(i=index; i<pArray->count-1; i++){
            pArray->values[i]= pArray->values[i + 1];
        }
    }
    pArray->count--;
}

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

    int index;
    for(index=0;index<pArray->count;index++){
        if(pArray->count!=1){
            array_remove(pArray,index);
        }
        else{
            pArray->values[index]=0;
        }
        pArray->count=0;
    }
}

// insert an element into the array, before index
void array_insert(Array *pArray, int index, int value)
{
    int i;
    int newCapacity;
    if (pArray->count==pArray->capacity)
    {
        newCapacity=2* pArray->capacity;
        resize(pArray,newCapacity);
        pArray->count++;
    }
    else
    {
        pArray->count++;
    }
    for (i = pArray->count-1; i >index ; i--)
    {
        pArray->values[i] = pArray->values[i - 1];
    }
    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 temp;
    temp=pArray->values[index_a];
    pArray->values[index_a]=pArray->values[index_b];
    pArray->values[index_b]=temp;
}

void memory_free ( Array *pArray) {
    free (pArray->values);
}

Output:
[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)

### Activity 16: Solve the partitioning problem

| Array length | Runs | Avg.time (ms) | Relative time|
| --- | -------- | -------- | -------- |
|1000000 |100 |9.22 |1.00|
|2000000 |100 |19.34 |2.10|
|3000000 |100 |28.39 |3.08|
|5000000 |100 |48.49 |5.26|

**How does your algorithm scale as the array length increases?**

* The time to compute increases proportionally with the length of the array as can be seen by the average and relative time. An array of one million has a relative time of 1.00 seconds, whereas an array of five million has a relative time of 5.26 seconds.

## Look back

### What we've learnt

Group 3 has learned the differences between a static and dynamic containers and what is a linear data structure.

Static container
* The size is fixed.

Dynamic container:
* Capable of having arbitrary number of elements which can be changed during runtime.

Linear data structure:
* A data structure is linear if it organizes its elements into a sequence. A linear data structure has a first and last element.

### What were the surprises

How the system being used affects the sizeof operator with 8 bytes for a 64 bit computer and 4 bites for a 32 bit computer.

### What problems we've encountered

Getting all group members together to work on the assignment after fridays class.

### What was or still is unclear

How to use malloc and free to manage dynamic memory in c.

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

Group collaboration on Friday the 12th was good. Communication amongst group members could be improved by messaging more on Microsoft teams. When the group worked together healthy discussions occurred with different group members telling the group what they thought to be the correct answer. For next time when a group member is unable to join a meeting he/she should attempt to schedule another meeting with the group or ask what work can he/she do to assist the group.