---
# 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.                                             |  Rimma    |
| **Spokesperson** communicates group’s questions and problems to the teacher and talks to other teams; presents the group’s findings.                                              |   Nafiz   |
| **Reflector** observes and assesses the interactions and performance among team members. Provides positive feedback and intervenes with suggestions to improve groups’ processes. |  Yazan    |
| **Recorder** guides consensus building in the group by recording answers to questions. Collects important information and data.                                                   |   Husam   |

## 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
- even number belongs to set of numbers but doesnt belong to the set of odd numbers
- international student belongs to set of university students, but doesnt belong to set of dutch class students
- macbook belongs to the set of computers but doesnt belong to the set of cimputers that run on windows
- veggies belong to the set of vegetables but they might not belong to the set of specific salad recipe
- student belongs to LED department but doesnt belong specifically to ACS class set

### Activity 2: Comparing floating point numbers
In the case of floating-point numbers, the relational operator (==) does not produce correct output, this is due to the internal precision errors in rounding up floating-point numbers.
```c
int equals_dbl(double a, double b){
    if (fabs(a - b) < 0.00001)
        return 1; // true
    else
        return 0;//false
}

int main() {
    double a=41.0+0.5+0.2+0.2+0.1;
    double b=43.0-0.5-0.2-0.2-0.1;
    printf("%d\n", equals_dbl(a,b));
    return 0;
}
```

### Activity 3: Comparing compound data types

```c
int equals_prs(const person_t* obj1, const person_t* obj2){
    if((obj1->name==obj2->name) &&(obj1->year_of_birth==obj2->year_of_birth))
        return 1;
    return 0;
}
```

### Activity 4: Function prototypes

```c
void add(set_t* set, double a){
    set->data[set->size++]=a;
}

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

void remove(set_t *set, double x){
    for(int i=0; i<set->size; i++){
        if (set->data[i]==x){
            set->data[i]=0;
            set->size--;
        }
    }
}
```

### Activity 5: Dynamic sizing
```c
void ensure_cap(set_t * set) { // version 1
    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;
    }
}
```
### Activity 6: Function implementations
```c
void add(set_t* set, double a){
    set->data[set->size++]=a;
}

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

void remove(set_t *set, double x){
    for(int i=0; i<set->size; i++){
        if (set->data[i]==x){
            set->data[i]=0;
            set->size--;
        }
    }
}
```

### Activity 7: Time complexity of remove and add
| Operation | Time complexity |
|-----------| --------------- |
| Contains  |        o(n)       |
| Add       |        o(1)         |
| Remove    |          o(n)       |

### Activity 8: Binary search
Value to find: 46:

| Binary search step | lo  | hi  | mid |
|--------------------|-----|-----|-----|
| 1                  | 0   | 16  | 8  |
| 2                  | 8    |   16  |   11  |
| 3                  |   11  |  16  |    13 |


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  |
no 4 in a array


### Activity 9: Binary search - Time complexity

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



### Activity 10: Implementing index_of
```c
int index_of(int arr[], int l, int r, int x)
{
    if (r >= l) {
        int mid = l + (r - l) / 2;
        if (arr[mid] == x)
            return mid;
        if (arr[mid] > x)
            return binarySearch(arr, l, mid - 1, x);
        return binarySearch(arr, mid + 1, r, x);
    }
    return -1;
}
```


### Activity 11: Modifying the sorted array
```c
void add(set_t* set, double a){
    set->data[set->size++]=a;
} 

void remove(set_t *set, double x){
    for(int i=0; i<set->size; i++){
        if (set->data[i]==x){
            set->data[i]=0;
            set->size--;
        }
    }
}

bool set_contains(set_t* set, double needle){
    size_t index = index_of(set, needle);
    if (index == set->size){
        return false;
    }
    return equals_dbl(set->data[index], needle);
}
```

### Activity 12: Time complexity of the sorted set
| Operation | Time complexity |
|-----------| --------------- |
| Add       |         O(log n)       |
| Remove    |         O(n)        |
| Contains  |         O(log n)        |



## Looking back

### What we've learnt
- how to use binary search
- how to implement sorted sets

### What were the surprises
differences btw time complexities of unsorted and sorted sets

### What problems we've encountered

implementation of required functions was hard

### What was or still is unclear

### How did the group perform?
- Our team worked very well together 
- Knowing each other’s strengths and weaknesses improved productivity 
- The team had productive discussions regarding each topic



