---
# System prepended metadata

title: Week 6 - Sets

---

# 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

```c
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

```c
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

```c
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

```c
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

```c
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

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