# Week 6 - Sets
## Team
Team name: Totally Useless
Date: 2022/03/23
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. | Ines |
| **Spokesperson** communicates group’s questions and problems to the teacher and talks to other teams; presents the group’s findings. | Adelina |
| **Reflector** observes and assesses the interactions and performance among team members. Provides positive feedback and intervenes with suggestions to improve groups’ processes. | Justas |
| **Recorder** guides consensus building in the group by recording answers to questions. Collects important information and data. | Tautvydas |
## 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
* When tickets are checked to a specific event, it is checked whether that ticket belongs in the list of valid tickets to check if the ticket owner can participate in the event.
* When entering a building (office, school) restricted to a specific group of people, access will be given to enter if you are on the list of people that have access to this building.
* Going abroad, you are checked whether you can go throught a border control post by identifying whether their ID belongs in the list of valid IDs.
* When looking to buy a product of a specific category, it is only enough to identify whether it belongs in the list of that category to buy it.
* Checking whether your discount applies to a specific product. It is required to check whether that product belongs in the discounted product list.
### 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.
* It is more efficient to compare floats with an implemeted function or with the absolute value of the difference.
```c
bool equals_dbl(double d1, double d2) {
double precision=0.000000001;
if (fabs(d1-d2)<precision){
return true;
}
else {
return false;
}
}
```
### Activity 3: Comparing compound data types
```c
bool equals_prs(const person_t* obj1, const person_t* obj2){
if(strcmp(obj1->name, obj2->name)==0 && obj1->year_of_birth==obj2->year_of_birth){
return true;
}
else{
return false;
}
}
```
### Activity 4: Function prototypes
```c
void set_add(set_t *new_set, double value);
void set_remove(set_t *new_set, double value);
bool set_contains( set_t const *new_set , double value) ;
```
### 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;
}
}
```
The first version of the code is the correct one as it realloc already frees the set->data, meaning the that the second version of the code would free the set of values twice, leading to multiple potential errors. Additionally, the first version checks whether the realloc was successful or not to actually resize the data in the set.
### Activity 6: Function implementations
```c
void set_add(set_t *new_set, double value){
if(!set_contains(new_set, value)){
ensure_cap(new_set);
new_set->data[new_set->size+1]=value;
new_set->size++;
}
}
bool set_contains( set_t const *new_set , double value) {
for(int index=0; index< new_set->size; ++index){
if(equals_dbl(value,new_set->data[index])){
return true;
}
}
return false;
}
void set_remove(set_t *new_set, double value){
bool found = false;
for(int index=0; index<new_set->size; ++index){
if(new_set->data[index]==value){
found = true;
}
if(found){
new_set->data[index]=new_set->data[index+1];
}
}
free(&new_set->data[new_set->size-1]);
new_set->size--;
}
```
Record your answer here
### Activity 7: Time complexity of remove and add
| Operation | Time complexity |
|-----------| --------------- |
| Contains | O(n) |
| Add | O(n) |
| Remove | O(n) |
Record your answer here
### 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 | - | - | - |
| 5 | - | - | - |
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 |
| 5 | 0 | 1 | 0 |
### Activity 9: Binary search - Time complexity
| Array size | Lookups |
|------------|---------|
| 16 | 5 |
| 32 | 6 |
| 64 | 7 |
| 128 | 8 |
| 256 | 9 |
If the data structure's size is increased to twice its previous size, the will be one additional lookup, which adds to the worst time complexity. This is because the binary search keep dividing the data structure in two halfs, which it keeps on repeating, until it finds the value or is unable to do so. The time complexity is O(logn).
### Activity 10: Implementing index_of
```c
size_t index_of(const set_t * set, double needle) {
size_t lo = 0, hi = set->size;
if (needle == 0) {
return 0;
}
while (lo < hi) {
size_t mid = lo + (hi - lo) / 2;
if (equals_dbl(set->data[mid], needle)) {
return mid - 1;
}
else if (set->data[mid] < needle) {
lo = mid + 1;
}
else if (set->data[mid] > needle) {
hi = mid;
}
}
return hi - 1;
}
```
### Activity 11: Modifying the sorted array
```c
/// set_add:
void mm(char* dest, char* src, size_t count){
if (dest > src){
for (int i=count-1; i >= 0; --i)
dest[i] = src[i];
}
}
void set_add(set_t *new_set, double value) {
if(!set_contains(new_set, value)){
ensure_cap(new_set);
size_t position = indexOf(new_set, value);
memmove(&(new_set->data[position+1]), &(new_set->data[position]), sizeof(double)*(new_set->size - position-1));
// for(size_t i=new_set->size-1; i>position; i--){
// new_set->data[i]=new_set->data[i-1];
// }
new_set->data[position] = value;
new_set->size++;
}
}
/// set_remove:
void set_remove(set_t *new_set, double value){
if(set_contains(new_set, value)){
size_t position = indexOf(new_set, value);
memmove(&(new_set->data[position]), &(new_set->data[position+1]), sizeof(double)*(new_set->size - position));
}
free(&new_set->data[new_set->size-1]);
new_set->size--;
}
/// set_contains:
bool set_contains(set_t* set, double needle){
size_t index = indexOf(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(logn) |
| Remove | O(logn) |
| Contains | O(logn) |
The reason why the time comlexity of adding, removing and contains is O(logn) is because the operations al contain the indexOf function which does the binary search which has a complexity of O(logn) which makes it the complexity for the other functions.
## Generic set (optional)
### Activity 13: Functions index_of and contains
### Activity 14: Functions add and remove
## Looking back
### What we've learnt
* We understood basic principles of set operations: insert, delete and lookup(contains).
* We deepend our knolege of time complexities.
### What were the surprises
* We did not encounter any surprises. Most of the exercises were straightforward and easy to understand.
### What problems we've encountered
* We had some issues with activity 11 were the capacity would stay at this number "4215456" all the time. We changed the increment from 1.5 to 2 and it fixed itself but we do not think it fixed the original bugs.
### What was or still is unclear
* Besides the problem with the activity 11 we do not have any questions.
### How did the group perform?
* Our team did a lot of co-operation during this week's assignments. The first few activities were quite easy to do but for the last ones, we co-operated to help each other out. We believe our teamwork has improved tremendously since the first week.
Sign in with Wallet
Connect another wallet