# Week 5 - Sets

https://code-with-me.jetbrains.com/jgYFXH8cBhy1clYozL4VXw#p=CL&fp=F2320E0BD580A949D185641B942CAD82A0E1C9ABF7D35751872FF36CEDFAEB10

## Team

Team name: Groep 5
Date:

Members:
Anton Vorderman
Nian Luisman
Thom Kistemaker

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

## Activities

### Activity 1: Find out: set membership

Supermarkt app:
Reisorganisie-site
Youtube search page
Steam shop
Spotify suggested playlist

### Activity 2: Comparing floating point numbers

https://www.programmersought.com/article/99311799915/
Er gaat wat fout bij het afronden waardoor double a gelijk is aan 42.000000000000007 en double b gelijk is aan 41.99999999999993

//    Heeft math.h library nodig
_Bool equals_dbl(double d1, double d2){
    if(fabs(d1-d2) < 0.000001){
        return true;
    }
    else{
        return false;
    }
}

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

    if(strcmp((const char *) &p1->name, (const char *) &p2->name) == 0 && p1->yearOfBirth == p2->yearOfBirth){
        return true;
    }
    else {
        return false;
    }
}

### Activity 4: Function prototypes

void set_add(Set *set, int value);
double set_remove(Set *set);
_Bool set_contains(Set *set, double comparison);

### Activity 5: Function implementations

void set_add(Set *set, double value){
    if(!set_contains(set, value)){
        ensure_capacity(set, set->size+1);
        set->data[set->size] = value;
        set->size++;
    }
}

void set_remove(Set *set, double value){
    for (int i = 0; i < set->size; i++){
        if(equals_dbl(set->data[i], value)){
            memmove(&set->data[i], &set->data[i+1], (set->size-i)*sizeof(double));
            set->size--;

            return;
        }
    }
}

_Bool set_contains(Set *set, double comparison){
    for (int i = 0; i < set->size; i++){
        if(equals_dbl(set->data[i], comparison)){
            return true;
        }
    }
    return false;
}

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

Add functie: O(n)
Remove functie: O(n^2)

### Activity 7: Binary search

Binary search: O(log(n))

### Activity 8: Implementing indexOf

int index_of(Set *set, double comparison){
    if(set->size == 0)
        return 0;
    if(set->size == 1)
        return (set->data[0] > comparison)? 0 : 1;

    int lo = 0, hi = set->size -1;
    if(set->data[hi] < comparison){
        return set->size;
    }
    if(set->data[lo] > comparison){
        return 0;
    }

    while(lo < hi){
        int mid = lo + (hi -lo)/2;
        if(set->data[mid] < comparison){
            lo = mid + 1;
        }else if(set->data[mid] > comparison){
            hi = mid - 1;
        }else
            return mid;
    }
}

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

void set_add(Set *set, double value){
    if(!set_contains(set, value)){
        ensure_capacity(set, set->size+1);
        int index = index_of(set, value);
        memmove(&set->data[index+1], &set->data[index], (set->size-index)*sizeof(double));
        set->data[index] = value;
        set->size++;
    }
}

void set_remove(Set *set, double value){
    int i = index_of(set, value);
    memmove(&set->data[i], &set->data[i+1], (set->size-i)*sizeof(double));
    set->size--;
}

### Activity 10: Time complexity of the binary search implementation

**Best case:**
Add: O(log(n))
Remove: O(log(n))

**Worst case:**
Add: O(log(n)+n)
Remove: O(log(n)+n)

**Average:**
Add: O((log(n)+n)/2)
Remove: O((log(n)+n)/2)

### Activity 11: Functions indexOf and contains

### Activity 12: Functions add and remove

## Look back

### What we've learnt

Memory moving bij sets.
Gebruik maken van sorted data.

### What were the surprises

memmove

### What problems we've encountered

memmove

### What was or still is unclear

niks eigenlijk, maandag 17:15 waren we klaar.

### How did the group perform?

ging wel soepel, niet zo heel veel problemen tegen gekomen. We konden elkaar goed aanvullen.