# Algorithms &
# Data Structures week 5
# Sets

Team name: power rangers
Date: 19-3-2021

Members

Emilio Hodge
Stan Beddinkhaus
Morris Rouwhorst
Joey Vultink

| Role | Name |
|-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|------|
| **Facilitator** keeps track of time, assigns tasks and makes sure all the group members are heard and that decisions are agreed upon. |Joey|
| **Spokesperson** communicates group’s questions and problems to the teacher and talks to other teams; presents the group’s findings. |Emilio|
| **Reflector** observes and assesses the interactions and performance among team members. Provides positive feedback and intervenes with suggestions to improve groups’ processes. |Stan|
| **Recorder** guides consensus building in the group by recording answers to questions. Collects important information and data. |Morris|

## Activities

### Activity 1: Find out: set membership
When you need to show your name bound entrance ticket for something
At the border passport or ID

At the airport boarding pass

if you go to the club and you need to verify that your above 18 years old.

### Activity 2: Comparing floating point numbers

#include <stdio.h>
#include <stdbool.h>
#include <math.h>

 _Bool equals_dbl(double d1, double d2){
    double EPS = 1e-323;
     if (abs(d1-d2) < EPS){
         return true;
    }
    return false;
}
int main() {
    double a = 41.0 + 0.5 + 0.2 + 0.2 + 0.1;
    double b = 43.0 - 0.5 - 0.2 - 0.2 - 0.1;
    _Bool equal = equals_dbl(a, b);
    printf("a and b are %s", equal? "equal" : "not equal");

    return 0;
}

### Activity 3: Comparing compound data types

_Bool equals_prs(const void *obj1, const void *obj2) {
    const Person *p1 = (const Person *) obj1;   //Top
    const Person *p2 = (const Person *) obj2;
    if ((p1->yearOfBirth == p2->yearOfBirth) && (strcmp(p1->name, p2->name))) {
        return true;
    }
    return false;
}

int main() {
    Person p1;
    Person p2;
    p2.name = 'henk';
    p1.name = 'frits';
    p2.yearOfBirth = 1980;
    p1.yearOfBirth = 1918;
    _Bool equal = equals_prs(&p1, &p2);
    printf("a and b are %s", equal ? "equal" : "not equal");
    return 0;
}

### Activity 4: Function prototypes

void Remove(Set* set, int value) {
    if (contains(set,value) == false){
        printf("Remove function no worky because data no containy value :).\n");
        return;
    }
    if (set->size == 0) {
        printf("No elements in array.\n");
    } else {
        for (int i = 0; i < set->size; i++) {
            if (value == set->data[i]) {
                for (int j = i + 1; j < set->size; j++)
                    set->data[j - 1] = set->data[j];
                set->size--;
                printf("element removed.\n");
                break;
            }
        }

    }
}

bool contains(Set* set, int value) {
    for (int i = 0; i < set->size; i++) {
        if (value == set->data[i]) {
            printf("Contains function returns true.\n");
            return true;
        }
    }
    printf("Contains function returns false.\n");
    return false;
}

void add(Set* set, int value) {
    if ((set->size >= set->capacity)) {
        printf("Successfully overflowed in add function.\n");
    } else {
        set->data[set->size] = value;
        set->size++;
        printf("Successfully added value.\n");
    }
}

int main() {
    double dataSet[] = {2,3,4,5,7};
    Set set;
    set.size = 0;
    set.capacity = DEFAULT_CAP;
    set.data = malloc(DEFAULT_CAP * sizeof(double));
    for (int i = 0; i < sizeof(dataSet)/sizeof(double); i++){
        add(&set, dataSet[i]);
    }
    Remove(&set, 3);
    contains(&set, 0);
    for (int i = 0; i <= set.size; i++) {
        printf("%.0f\n", set.data[i]);
    }

### Activity 5: Function implementations

#include <stdio.h>
#include <stdbool.h>
#include <malloc.h>
#include <string.h>

static const int DEFAULT_CAP=64;
typedef struct {
    double *data;
    int size; // number of items in this set
    int capacity; // size of the `data` array
    int factor;
} Set;

Set *makeSet() {
    Set *set = malloc(sizeof(Set));
    set->size = 0;
    set->capacity = DEFAULT_CAP;
    set->data = malloc(DEFAULT_CAP * sizeof(double));
    return set;
}

void destroySet(Set *set) {
    free(set->data);
    free(set);
}

void add(Set *set, int value) {                         //void *realloc(void *ptr, size_t size)
    if ((set->size >= set->capacity)) {
        set->factor++;
        if ((set->data=realloc(set->data, set->factor * DEFAULT_CAP*sizeof(double)))==NULL)       //realloc moet geassigned worden anders gaat het fout
               printf("Error.\n");
         else{
        printf("Successfully overflowed and resized in add function.\n");
        set->capacity=DEFAULT_CAP * set->factor;
         }
    }
    set->data[set->size] = value;
    set->size++;
    printf("Successfully added value.\n");

}

int contains(Set *set, int value) {
    for (int i = 0; i < set->size; i++) {
        if (value == set->data[i]) {
            printf("Contains function returns true.\n");
            return true;
        }
    }
    printf("Contains function returns false.\n");
    return false;
}

void Remove(Set *set, int value) {
    if (contains(set, value) == false) {
        printf("Remove function no worky because data no containy value :).\n");
        return;
    }
    if (set->size == 0) {
        printf("No elements in array.\n");
    } else {
        for (int i = 0; i < set->size; i++) {
            if (value == set->data[i]) {
                if (memmove(&set->data[i], &set->data[i + 1], (set->size * sizeof(double)*set->factor-i)) != NULL) {  // void *memmove(void *str1, const void *str2, size_t n)set
                    set->size--;
                    //   for (int j = i + 1; j < set->size; j++)
                    //   set->data[j - 1] = set->data[j];
                    printf("Element removed.\n");
                    return;
                } else {
                    printf("Failure !!!!!.\n");
                }
            }
        }
    }
}

int main() {
    Set *set = makeSet();
    set->factor = 1;
    for (int i = 0; i < 128; i++) {
        add(set,(double)i);
    }
    Remove(set, 3);
    //Remove(set,30);
    contains(set, 0);
    for (int i = 0; i < set->size; i++) {
        printf("%.0f\n", set->data[i]);
    }
    destroySet(set);
    return 0;
}

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

Record your answer here

### Activity 7: Binary search

Record your answer here

### Activity 8: Implementing indexOf

### Activity 9: Functions add and remove for the sorted array

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

### Activity 11: Functions indexOf and contains

### Activity 12: Functions add and remove

## Look back

### What we've learnt

Fill in...

### What were the surprises

Fill in...

### What problems we've encountered

Fill in...

### What was or still is unclear

Fill in...

### 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?