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

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

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

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

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

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

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

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