# Week 6 - Sets
## Team
Team name: Beast from the East
Date: 26/04/2022
Members: Nikola Zahariev, Casian Ionescu, Attila Poldan
| Role | Name |
|-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|------|
| **Facilitator** keeps track of time, assigns tasks and makes sure all the group members are heard and that decisions are agreed upon. | |
| **Spokesperson** communicates group’s questions and problems to the teacher and talks to other teams; presents the group’s findings. | |
| **Reflector** observes and assesses the interactions and performance among team members. Provides positive feedback and intervenes with suggestions to improve groups’ processes. | |
| **Recorder** guides consensus building in the group by recording answers to questions. Collects important information and data. | |
## 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
Record your answer here
Examples:
1. Phones - people can choose phones based on sets of brands, sets of modells (which is tied to their year too), sets of specs, sets of colors
2. Wallets - sets of brands, colors, sizes, materials
3. Headphones - sets of brands, sizes, types (headset or ear pods), colors
4. Sneakers - sets of brands, years of production, condition, modells
5. Alcoholic bevereges - sets of types (whisky, vodka, brandy, rakia etc), brands, percenteges of alcohol
### Activity 2: Comparing floating point numbers
Answer:
```c
bool equals_dbl(double d1, double d2)
{
bool flag = (d1 == d2);
if(flag == false && (d1-d2) < 0.00000000001 && (d2-d1) < 0.0000001)
{
flag = true;
}
return flag;
}
```
### Activity 3: Comparing compound data types
```c
bool equals_prs(const person_t * obj1, const person_t * obj2) {
return obj1->name == obj2->name && obj1->year_of_birth==obj2->year_of_birth;
}
```
### Activity 4: Function prototypes
```c
bool set_contains(set_t * set, double data);
void set_add(set_t * set, double data);
void set_remove(set_t * set, double data);
```
### 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;
}
}
```
Record your answer here
### Activity 6: Function implementations
```c
bool set_contains(set_t* set, double data)
{
for(int i = 0; i < set->size; ++i)
{
if(set->data == &data && (set->data[i] - data) < 0.0001)
{
return true;
}
}
return false;
}
void set_add(set_t* set, double data)
{
if(false == set_contains(set, data))
{
ensure_cap(set);
set->data[set->size] = data;
set->size++;
}
}
void set_remove(set_t* set, double data)
{
for(int i = 0; i < set->size; ++i)
{
if(set->data[i] == data)
{
for(int match = i; match < set->size; ++match )
{
set->data[match] = set->data[match+1];
}
--set->size;
}
}
}
```
### Activity 7: Time complexity of remove and add
| Operation | Time complexity |
|-----------| --------------- |
| Contains | O(n) |
| Add | O(1) |
| Remove | O(1) |
The reason for the O(1) time complexity is not the full answer. Neither is the O(n) on the lookup algorythem. In the worst case (assuming the value we are looking for is ineed NOT present in the set) then it ineed is O(n), which is indirectly reflected on the other operations. If the lookups take O(n) every time then the other operations will also yield O(n), that is because of the nature of both the approach followed here and the nature of sets. Where removing/adding are always performed hand in hand with the lookup. The only exceptions here are prepending and appending, which will always yield O(1). In other words, the linear search performed as it is, drags the other operations with it into O(n).
### Activity 8: Binary search
Value to find: 46: 13th place
| Binary search step | lo | hi | mid |
|--------------------|-----|-----|-----|
| 1 | 0 | 16 | 8 |
| 2 | 9 | 16 | 12 |
| 3 | 13 | 16 | 14 |
| 4 | | | |
| 5 | | | |
Value to find: 4: not in set
| Binary search step | lo | hi | mid |
|--------------------|-----|-----|-----|
| 1 | 0 | 16 | 8 |
| 2 | 0 | 8 | 4 |
| 3 | 0 | 4 | 2 |
| 4 | 0 | 2 | 1 |
| 5 | | | |
### Activity 9: Binary search - Time complexity
| Array size | Lookups |
|------------|---------|
| 16 | 5 |
| 32 | 6 |
| 64 | 7 |
| 128 | 8 |
| 256 | 9 |
|1000 | 10|
| 4000 | 13|
|10 000| 14|
|1048576| 21|
Time complexity: O(log n)
### Activity 10: Implementing index_of
```c
size_t indexOf(const set_t * set, double value)
{
size_t lo = 0, hi = set->size;
size_t mid;
while (lo < hi) {
mid = lo + (hi - lo) / 2;
if (equals_dbl(set->data[mid], value)) {
//printf("%lf\n",set->data[mid]);
return mid;
}
else if (set->data[mid] < value) {
lo = mid + 1;
}
else {
hi = mid;
}
}
if(lo==hi) mid=hi;
return mid;
}
```
Record your answer here
### Activity 11: Modifying the sorted array
```c
/// set_add:
void set_add(set_t* set, double data)
{
if(!set_contains(set, data))
{
ensure_cap(set);
for (int i = set->size; i > indexOf(set,data); --i) {
set->data[i]=set->data[i-1];
}
set->data[indexOf(set,data)]=data;
set->size++;
}
}
/// set_remove:
void set_remove(set_t* set, double data)
{
if(set_contains(set,data)) {
for (int i = indexOf(set, data); i < set->size; ++i) {
set->data[i] = set->data[i + 1];
}
set->size--;
}
}
/// set_contains:
bool set_contains(set_t* set, double data)
{
return data==set->data[indexOf(set,data)];
}
```
Record your answer here
### Activity 12: Time complexity of the sorted set
| Operation | Time complexity |
|-----------| --------------- |
| Add | O(n) |
| Remove | O(n) |
| Contains | O(1) |
Record your answer here
## 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
Formulate at least one lesson learned.
### What were the surprises
### What problems we've encountered
Fill in...
### What was or still is unclear
```c=
set_add(set, 41.0 + 0.5 + 0.2 + 0.2 + 0.1);
4 set_remove(set, 43.0 - 0.5 - 0.2 - 0.2 - 0.1);
```
These two lines of code gives two different answers even thought it supposed to be the same number. The difference is around 0.00000006 as I remember. Why????
### How did the group perform?
How was the collaboration? What were the reasons for hick-ups? What worked well? What can be improved next time?
Sign in with Wallet
Connect another wallet