# Week 6 - Sets

## Team

Team name:
Date:

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. | |
| **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
Make sure to have the activities signed off regularly to ensure progress is tracked.

Download the provided project and open it in CLion.

### Activity 1: Find out: set membership

Leeftijdscategorie met voetbal; controle op leeftijd.
achttien+ feest; controle op leeftijd.
Inschrijven opleiding; controle op behaald niveau

### Activity 2: Comparing floating point numbers

bool equals_dbl(double a, double b) {
    return fabs(a - b) < 0.000000000001;
}

### Activity 3: Comparing compound data types

bool equals_prs(const person_t *obj1, const person_t *obj2) {
    return  strcmp(obj1->name, obj2->name) == 0 == 1 && obj1->year_of_birth == obj2->year_of_birth;
}

### Activity 4: Function prototypes

void set_add(set_t *set, double value);
void set_remove(double value, set_t *set);
bool set_contains(set_t *set, double valueue);

### Activity 5: Dynamic sizing

void ensure_cap(set_t * set) {
    ...
}

De tweede is juist omdat deze ook het ander geheugen vrij geeft.

### Activity 6: Function implementations

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

void set_remove( set_t *set, double value) {
    for (int i = 0; i < set->size; ++i) {
        if (equals_dbl(set->data[i], value)) {
            if (i == set->size) set->size--;
            else {
                for (int j = i; j < set->size; ++j) {
                    set->data[i] = set->data[i + 1];
                }
                set->size--;
            }
        }
    }
}

bool set_contains(set_t *set, double valueue) {
    for (int i = 0; i < set->size; ++i) {
        if (set->data[i] == valueue) return true;
    }
    return false;
}

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

| Operation | Time complexity |
|-----------| --------------- |
| Contains | O(n) |
| Add | O(n) |
| Remove | O(n) |

Record your answer here

### Activity 8: Binary search

Value to find: 46:

| Binary search step | lo | hi | mid |
|--------------------|-----|-----|-----|
| 1 | 0 | 16 | 8 |
| 2 | 9 | 16 | 12 |
| 3 | 13 | 16 | 14 |
| 4 | 13 | 14 | 13 |
| 5 | | | |

Value to find: 4:

| Binary search step | lo | hi | mid |
|--------------------|-----|-----|-----|
| 1 | 0 | 16 | 8 |
| 2 | 0 | 8 | 4 |
| 3 | 0 | 4 | 2 |
| 4 | 0 | 2 | 1 |
| 5 | 0 | 1 | 0 |

### Activity 9: Binary search - Time complexity

| Array size | Lookups |
|------------|---------|
| 16 | 5 |
| 32 | 6 |
| 64 | 7 |
| 128 | 8 |
| 256 | 9 |

Record your answer here

### Activity 10: Implementing index_of

size_t index_of(const set_t* set, double needle){
    for (int i = 0; i < set->size; ++i) {
        if (set->data[i] == needle) return i;
        else if (set->data[i] > needle) {
            return i;
        }
    }
    return set->size;
}

Record your answer here

### Activity 11: Modifying the sorted array

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


void set_remove( set_t *set, double value) {
    for (int i = 0; i < set->size; ++i) {
        if (equals_dbl(set->data[i], value)) {
            if (i == set->size) set->size--;
            else {
                for (int j = i; j < set->size; ++j) {
                    set->data[i] = set->data[i + 1];
                }
                set->size--;
            }
        }
    }
}


bool set_contains(set_t *set, double value) {
    for (int i = 0; i < set->size; ++i) {
        if (set->data[i] == value) return true;
    }
    return false;
}

Record your answer here

### Activity 12: Time complexity of the sorted set

| Operation | Time complexity |
|-----------| --------------- |
| Add |O(n) |
| Remove |O(n) |
| Contains |O(n) |

Record your answer here

## Generic set (optional)

### Activity 13: Functions index_of and contains

Record your answer here

### Activity 14: Functions add and remove

Record your answer here

## Looking back

### What we've learnt

Formulate at least one lesson learned.

### What were the surprises

Fill in...

### What problems we've encountered

Fill in...

### What was or still is unclear

Fill in...

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

> Written with [StackEdit](https://stackedit.io/).