# 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
Google Drive
Gist
Clipboard
Sign in with Wallet
