# Week 6 - Sets
## Team
Team name:Error
Date:27.03.2022
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. | Thanh Tran 516467 |
| **Spokesperson** communicates group’s questions and problems to the teacher and talks to other teams; presents the group’s findings. | Kaloyan Zhekov 511216 |
| **Reflector** observes and assesses the interactions and performance among team members. Provides positive feedback and intervenes with suggestions to improve groups’ processes. |Hoang Minh Le 511907 |
| **Recorder** guides consensus building in the group by recording answers to questions. Collects important information and data. | Hoa Than 487272 |
## 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
Examples of membership testing
1. A fitness center have a special service and class just for VIP members. The gym want to check whether the card holder can join the class and use this special service by checking if the membership card type is belong to VIP group.
2. A phone manufacturer have a promotion to change battery for all phone model from 2020 until now. This company want to check whether the phone is able to have the benefit by checking the applied model for this promotion.
3. An online shop issues some discount voucher code for specific products. When the customer would like to buy with voucher, the shop want check whether the product belongs to the list of discount product.
4. People go to cinema with a movie ticket. A ticket checker want to check whether this ticket holder belongs to the customer list for this session or not.
5. A bar club is just available for people over 18. The guard need to check whether the customer is eligible for joining the club by checking their ID if they’re above 18 or not
### Activity 2: Comparing floating point numbers
Floating point types like float, double or long double couldn’t show some numbers precisely due to the finite precision and it represent the values in a binary format. Hence, it cannot be compared directly. Instead of that, we can find the epsilon between two numbers
```c
bool equals_dbl(double d1, double d2){
double epsilon = 0.0000001f;
if(fabs(d1-d2) < epsilon){
return true;
} return false;
}
int main() {
const double a = 41.0 + 0.5 + 0.2 + 0.2 + 0.1;
const double b = 43.0 - 0.5 - 0.2 - 0.2 - 0.1;
const double pi_1 = 3.14159265; const double pi_2 = 355.0/113.0;
equals_dbl(a,b);
if(equals_dbl(a,b) == 1){
printf ("a and b are %s \n","equal");
} else
printf ("a and b are %s\n","not equal");
equals_dbl(pi_1,pi_2);
if(equals_dbl(pi_1,pi_2) == 1){
printf ("pi_1 and pi_2 are %s \n","equal");
}else
printf ("pi_1 and pi_2 are %s\n","not equal");
}
```
### Activity 3: Comparing compound data types
```c
typedef struct person {
const char* name;
const int year_of_birth;
}person_t;
bool equals_prs(const person_t* obj, const person_t* obj2){
int result = strcmp(obj->name, obj2->name);
if (result == 0 && obj->year_of_birth == obj2-> year_of_birth ){
return true;
} return false;
}
int main() {
person_t alice = {.name="Alice", .year_of_birth=2001};
person_t bob = {.name = "Bob", .year_of_birth=2001};
person_t alice2 = {.name="Alice", .year_of_birth=2001};
person_t future_bob = {.name = "Bob", .year_of_birth=2035}; assert(!equals_prs(&alice, &alice2));
assert(!equals_prs(&alice, &bob));
assert(!equals_prs(&alice2, &future_bob));
}
```
### Activity 4: Function prototypes
```c
typedef struct set{
double* data;
size_t size;
size_t capacity;
}set_t;
bool contains (set_t *set, double add_data) {
for (int i = 0; i < (int) set->capacity; i++)
{
if (set->data[i] == add_data) {
return true;
}
} return false;
}
void add_data(set_t *set, double add_data) {
set->data[set->capacity] = add_data; set->size++;
}
void remove_data(set_t *set, double remove_data) {
bool contains = false;
for (int i = 0; i < (int) set->capacity; i++) {
if (set->data[i] == remove_data) {
contains = true;
} if (contains) {
set->data[i] = set->data[i + 1]; set->size--;
}
}
}
```
### Activity 5: Dynamic sizing
The 1st version is the correct one. The reason is that the realloc in C already creates a new memory remaining old data, if the user free that pointer, those data will be lost.
```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;
}
}
```
### Activity 6: Function implementations
Contain
```c
bool set_contains(set_t*head, double value){
size_t i=0;
bool flag=false;
while(i<head->size){
if(head->data[i]==value){
flag=true;
break;
}
i++;
}
return flag;
}
```
Set_add
```c
void set_add(set_t*head,double data){
size_t min_size=(head)->size+1;
if(head->capacity==0)
head->capacity++;
while(min_size>=(head)->capacity){
((head)->capacity)*=1.5;
}
(head)->data=realloc((head)->data,((head)->capacity)*sizeof(double));
if((head)->data!=NULL){
if(!set_contains(head,data)){
(head)->data[min_size-1]=data;
(head)->size=min_size;
}
}
}
```
Set_remove
```c
void set_remove(set_t*head,double value){
if(!set_contains(head,value)){
printf("\nSorry");
}
else{
size_t i=0;
bool flag=false;
while(i<(head)->size){
if(((head)->data[i])==value){
break;
}
i++;
}
while(i<(head)->size){
(head)->data[i]=(head)->data[i+1];
i++;
}
}
}
```
### Activity 7: Time complexity of remove and add
| Operation | Time complexity |
|-----------| --------------- |
| Contains | O(n) |
| Add | O(1) |
| Remove | O(1) |
### Activity 8: Binary search
Value to find: 46:
| Binary search step | lo | hi | mid |
|--------------------|-----|-----|-----|
| 1 | 0 | 16 | 8 |
| 2 | 9 | 16 |12 |
| 3 | 13 | 16 |14 |
| 4 | | 14 |13 |
| 5 | | 14 |13 |
Value to find: 4:
| Binary search step | lo | hi | mid |
|--------------------|-----|-----|-----|
| 1 | 0 | 16 | 8 |
| 2 | 9 |8 |4 |
| 3 |0 |16 |14 |
| 4 |0 |2 |1 |
| 5 |0 |1 |0 |
### 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
size_t indexOf(const set_t *set, double needle) {
size_t lo = 0, hi = set->size;
size_t index;
while (lo < hi) {
size_t mid = lo + (hi - lo) / 2;
if (equals_dbl(set->data[mid], needle)) {
return mid;
} else if (set->data[mid] < needle) {
lo = mid + 1;
} else if (set->data[mid] > needle) {
hi = mid;
}
index = mid + 1;
} return index;
}
```
### Activity 11: Modifying the sorted array
```c
Void set_add(set_t *set, double data) {
size_t insert_index = indexOf(set, data);
if (insert_index > set->size) {
set->data[insert_index] = data; set->size++;
} else if (insert_index <= set->size) {
set->size++;
for (size_t i = set->size - 1; i < insert_index; i--) {
set->data[i] = set->data[i - 1];
}
set->data[insert_index - 1] = data;
}
size_t new_capacity = set->capacity * 1.618;
set->capacity = (size_t) realloc(set->data, (new_capacity) * sizeof(double));
}
void set_remove(set_t *set, double data) {
size_t remove_index = indexOf(set, data);
for (size_t i = remove_index; i < set->size - 1; i++)
set->data[i] = set->data[i + 1]; set->size--;
}
```
### Activity 12: Time complexity of the sorted set
| Operation | Time complexity |
|-----------| --------------- |
| Add | O(log2(n)) |
| Remove | O(log2(n)) |
| Contains | O(log2(n)) |
## 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
implement a lookup operation in C using an array (sorted and unsorted) for storage
learn the basic set operations: insert, delete, lookup (contains)
Formulate at least one lesson learned.
### What were the surprises
Nothing
### What problems we've encountered
No problems were encountered this week.
### What was or still is unclear
Everthing is clear and learned.
### How did the group perform?
The group performed very well and collaboratevly. We did our exercises in time and in a way that every group member to understand them.
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/).
Sign in with Wallet
Connect another wallet