# Week 5 - Sets

## Team

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

## Activities

### Activity 1: Find out: set membership

A few examples of membership testing could be:
* A conductor checking who has a ticket on a bus
* A bouncer checking if a person is over 18
* Checking which students have passed an exam
* Looking for your favorite beer in a shop
* Checking if your laptop is still under warranty

### Activity 2: Comparing floating point numbers

The result we get here suprisingly is false. We get this result, because floating point numbers can't be represented exactly and rounding occurs which makes the two numbers differ a bit.

_Bool equals_dbl(double d1, double d2){
    return fabs(d1-d2) < 0.0001;
}

### Activity 3: Comparing compound data types

_Bool equals_prs(const void* obj1, const void* obj2){
    const Person* p1 = (const Person*)obj1;
    const Person* p2 = (const Person*)obj2;
    return (strcmp(p1->name, p2->name) == 0) && p1->yearOfBirth==p2->yearOfBirth;

### Activity 4: Function prototypes

Here are the prototypes of the add, remove and contain functions:

_Bool contains(Set *ps, double d);

void add(Set *ps, double d);

void remove_d(Set *ps, double d);

### Activity 5: Function implementations

Here is the implementation of the add, remove and contain functions as well as the function to resize the set if it exeeds DEFAULT_CAP.

Set* resize(Set *ps){
    double* temp = malloc((ps->capacity + 1) * sizeof (double));
    memcpy(temp, ps->data, (ps->capacity  * sizeof (double)));

    memcpy(ps->data, temp, (ps->capacity + 1) * sizeof (double));
    ps->capacity++;

    free(temp);

    return ps;
}

_Bool contains(Set *ps, double d){
    for (int i=0;i<ps->size;i++){
        if (fabs(ps->data[i]-d) < 0.0001) {
            return 1;
        }
    }
    return 0;
}
void add(Set *ps, double d){
    if (contains(ps, d)){
        printf("Sorry, the item is already in the set!\n");
        return;
    }
    else if (ps->capacity == ps->size){
        resize(ps);
    }
        ps->data[ps->size] = d;
        ps->size++;
}
void remove_d(Set *ps, double d){
    for (int i=0;i<ps->size;i++){
        if(fabs(ps->data[i]-d) < 0.0001){
            for (int j = i+1; j <ps->size ; ++j) {
                ps->data[i] = ps->data[j];
            }
            ps->size--;
            return;
        }
    }
    printf("%.3f isn't in the set\n", d);
}

### Activity 6: Time complexity of remove and add

We can crearly see that the *add* function has a time complexity of $O(n)$ because of the for loop used in the contain function, that iterates through the set. The *remove* function also has a time complexity of $O(n)$ despite the 2 for loops, because it doesn't iterate through the set 2 times.

### Activity 7: Binary search

bool contains(Set* set, double needle){
int lo = 0, hi = set->size - 1;
int a;

     while (lo <= hi)
     {
            
        int mid = lo + (hi - lo) / 2;

        if (set->data[mid] < needle)
            {
            lo = mid + 1;
            a = lo;
            }
        else if (set->data[mid] > needle)
            {
            hi = mid - 1;
            a = hi;
            }
        else if (set->data[mid] == needle)
        {
            return a;
        }
    }
    return a;
 }

### Activity 8: Implementing indexOf

int indexOf(Set* set, double needle)
 {
     if (set->size == 0)
        return 0;
    if (set->size == 1)
        return (set->data[0] > needle)?
    int lo = 0, hi = set->size - 1;
    
    int a;
    
     while (lo <= hi)
     {
            
        int mid = lo + (hi - lo) / 2;

        if (set->data[mid] < needle)
            {
            lo = mid + 1;
            a = lo;
            }
        else if (set->data[mid] > needle)
            {
            hi = mid - 1;
            a = hi;
            }
        else if (set->data[mid] == needle)
        {
            return a;
        }
    }
    return a;
 }

### Activity 9: Functions add and remove for the sorted array

void add(Set* set, double needle)
{
    for(int i=set->size; i>=set->index; i--)
    {
        set->data[i] = set->data[i-1];
    }
    set->data[set->index-1] = needle;
    set->size++;
}

### Activity 10: Time complexity of the binary search implementation
The time complexity cases for add, remove and average are all the same for the three functions.

Worst: O(log n)
Best: O(n)
Average: O(log n)

The iteration in Binary Search terminates after n iterations. At each iteration, the array is divided by half. So the length of array at any iteration is n. After n divisions, the length of array becomes 1. Hence, the time complexity of Binary Search is O(log n).

https://www.geeksforgeeks.org/complexity-analysis-of-binary-search/

## Look back

### What we've learnt

This week our team dealt with sets. We improved our understanding of the time complexity of sorted and unsorted sequences, and we also learned basic set operators such as insert, delete, and so on.

### What were the surprises

Most team members were surprised by the change in time complexity approach because the formula and the main idea changed compared to linear structures.

### What problems we've encountered

One of our team's main problems, which we encountered, was applying the code in practice or one or another part of the algorithm/code. For example, some team members found the implementation of the index difficult to use.

### What was or still is unclear

Summing up the last week and reflecting on past actions, it is possible to say that our team managed to deal with all the activities. Therefore we do not have any significant points of not understanding any part of the material.

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

Throughout the past week, our group has shown itself to be quite responsible. All tasks and roles were assigned on time, and communication was successfully organized. There were no negative moments, but if talking about what can be improved, the best point is always to remember all sorts of risks. For example, it is essential to consider that the code may not work the first time, so it requires you to start working on tasks as early as possible. Anyway, the group did a good job last week.