---
# System prepended metadata

title: Week 5 - Sets

---

# Week 5 - Sets 

## Team

Team name: Group 2
Date: 15 March 2021

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

## Activities

### Activity 1: Find out: set membership

1. When entering a gym, present a membership card to get in.
2. When I buy PC with different system
3. When entering a school a correct class with correct 
4. When you go to the shopping centre and there are diff shops. 
5. When you buy a house in a complex urban area. 

### Activity 2: Comparing floating point numbers

The result is not correct for floating number (although a and b are equal to 42.0). This is due to the internal precision errors in rounding up floating-point numbers.
The function below is one of the better and more precise way to compare floating numbers.
```c:
#include <float.h>
#include <math.h>

_Bool equals_dbl(double d1, double d2)
{
    return fabs(d1 - d2) <= FLT_EPSILON;
}

```

### Activity 3: Comparing compound data types
```c:
const Person* p1 = (const Person*)obj1;
const Person* p2 = (const Person*)obj2;
int a = 0;
if(p1->yearOfBirth == p2->yearOfBirth)
{
    printf("Years are the same");
    a = 1;
}
int result;
result = strcmp(p1->name, p2->name);
printf("%d", result);
if (result == 1 && a == 1)
{
    return 1;
}
else
{
    return 0;
}

```

### Activity 4: Function prototypes

```c:
bool contain(double needle, Set *set){
}

void add(double needle,Set *set) {
}

void remove(double needle, Set *set){
}
```


### Activity 5: Function implementations

```c:

bool contain(double needle, Set *set){
for(int i = 0; i<set->size; i++)
    {
    if(set->data[i] == needle)
        {
            return true;
        }
    else
        {
        return false;
        }
    }

}


void add(double needle,Set *set) {
int a;
a = contain(needle, set->data);
    if ( a==0)
    {
        set->data[set->size] = needle;
    }
}

void Remove(double needle,Set *set)
{
    for(int i = 0; i<set->size; i++)
    {
        if(set->data[i] == needle)
        {
            for(int index=i-1; index<set->size -1; index++)
            {
                set->data[index] = set->data[index + 1];
            }
            break;
        }
    }
}

typedef struct
{
    double* data;
    int size; // number of items in this set
    int capacity; // size of the `data` array
}Set;
```

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

Inserting: O(1), if done at the head or tail, O(n) if anywhere else since we have to reach that position by traveseing the linkedlist linearly. Deleting: O(1), if done at the head or tail, O(n) if anywhere else since we have to reach that position by traveseing the linkedlist linearly.

### Activity 7: Binary search

the time complexity of Binary Search is k = log2(n)

```c:
bool contains(Set* set, double needle){
    int lo = 0, hi = set->size - 1;
    while (lo <= hi){
        int mid = lo + (hi - lo) / 2;

        if (set->data[mid] < needle){
            lo = mid + 1;
            
        }
        else if (set->data[mid] > needle){
            hi = mid - 1;
        }
        if (set->data[mid] == needle)
        {
            return hi;
        }
    }
    return hi-1;
    
}
```


### Activity 8: Implementing indexOf
```c:

int indexOf(Set* set, double needle) {
    int lo = 0;
    int hi = set->size - 1;

    if (set->size == 0)
        return 0;
    if (set->size == 1)
        return (set->data[0] > needle);

    while (lo <= hi){

        int mid = lo + (hi - lo) / 2;
      //  printf(" so the value of array is %f \n", set->data[mid]);
        if (set->data[mid] < needle){
            lo = mid + 1;
           // printf(" so the value I am going back with index is %d \n", lo);
        }

        else if (set->data[mid] > needle){
            hi = mid - 1;
          //  printf(" so the value I am going back with index is %d \n", hi);
        }

        if (set->data[mid] == needle)
        {
            return hi;
        }
        printf("_____>>>> %d <<<<______ \n", mid);
    }

  //  printf(" so the value I am going back with array is %f \n", set->data[hi]);
  //  printf(" so the value I am going back with needle is %f \n", needle);
}


 bool contains(Set* set, double needle){
     int index = indexOf(set, needle);
     if (index == set->size){
        return false;
    }
    return set->data[index] == needle;
}


```

### Activity 9: Functions add and remove for the sorted array
```c:
void add(Set* set, double needle)
{
    for(int i=set->size; i>=set->index; i--)
    {
        set->data[i] = set->data[i-1];
    }
    set->data[set->index-1] = needle;
    set->size++;
}
```

### Activity 10: Time complexity of the binary search implementation

best : O(1) when insert in the head or tail of the array
worst: O(N) when the program has to traverse through all the array and find place to insert 
average: time complexity is between 2 case, which means O(1)+O(N) / 2 

## Look back


### What we've learnt


Membership, comparing 2 float numbers precisely, time complexity of Nonlinear structure type - Sets 


### What were the surprises
Igor: hwo to compare 2 float numbers way better.
Khan: Found a really good way to compare precisely with 2 float numbers

### What problems we've encountered
Igor: How to read the assignment
Khan: How to completely understand what the assignments are asking


### What was or still is unclear
Igor: Nothing
Khan: time complexity formulas

### How did the group perform?

Igor: good, We met 2 times already, where we all comunicated and we explained euch other when someone did not understand. 
Khan Everything is good