# 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

Record your answer here

### Activity 2: Comparing floating point numbers

bool equals_dbl(double a, double b) {
        if(a > b){
            if((a-b) < 0.00000001f){
                return true;
            } else return false;
        }else{
            if((b-a) < 0.00000001f){
                return true;
            } else return false;
        }
    }

### Activity 3: Comparing compound data types

bool equals_prs(const person_t * obj1, const person_t * obj2) {
    if(!strcmp(obj1->name, obj2->name)){
        if(obj1->year_of_birth == obj2->year_of_birth){
            return true;
        }else{
            return false;
        }
    }else{
        return false;
    }
}

### Activity 4: Function prototypes

void set_add(set_t * set, double val);
void set_remove(set_t * set, double val);
bool set_contains(const set_t * set, double val);

### Activity 5: Dynamic sizing

void ensure_cap(set_t * set) {
    if (set->size < set->capacity) return;
    size_t cap = (set->capacity + 1) * 3 / 2;
    double * ptr = realloc(set->data, cap * sizeof(double));
    if (ptr != NULL) {
        set->data = ptr;
        set->capacity = cap;
    }

Record your answer here

### Activity 6: Function implementations
void set_add(set_t * set, double val){
if(!set_contains(set,val)) {
ensure_cap(set);
size_t index = index_of(set, val);
for (size_t i = index; i < set->size; i++) {
set->data[i + 1] = set->data[i];
}
set->data[index] = val;
set->size++;
}
};
void set_remove(set_t * set, double val){
if(set_contains(set,val)){
size_t index = index_of(set,val);
set->data[index] = 0;
for(size_t i = index; i < set->size; i++){
set->data[index] = set->data[i+1];
}
set->size--;
}
};
bool set_contains(const set_t * set, double val){
size_t index = index_of(set,val);
if(equals_dbl(set->data[index],val)) {
return true;
}
return false;
};

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

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

Record your answer here

### Activity 8: Binary search

Value to find: 46:

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

Value to find: 4:

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

### Activity 9: Binary search - Time complexity

| Array size | Lookups |
|------------|---------|
| 16 | 5 |
| 32 | |
| 64 | |
| 128 | |
| 256 | |

Record your answer here

### Activity 10: Implementing index_of

size_t index_of(const set_t * set, double value){
    size_t lo = 0, hi = set->size;
    while (lo < hi) {
        size_t mid = lo + (hi - lo) / 2;
        if (equals_dbl(set->data[mid], value)) {
            return mid;
        }
        else if (set->data[mid] < value) {
            lo = mid + 1;
        }
        else {
            hi = mid;
        }
    }
    return hi;
};

Record your answer here

### Activity 11: Modifying the sorted array

/// set_add:
/// set_remove:
/// set_contains:

Record your answer here

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

| Operation | Time complexity |
|-----------| --------------- |
| Add | |
| Remove | |
| Contains | |

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/).