can someone do it asap 1. (15 points) Using pseudocode, implement the symmetric

Question

can someone do it asap

1. (15 points) Using pseudocode, implement the symmetric difference function for both a bit vector and a unidirectional LinkedList, such that the runtime is no greater than O(m) for the bit vector version and no greater than O n2) for the Linked List version. You may provide any additional functions you need, but be sure to Justify their runtime as well as the runtime for your symmetric difference function. Further, make sure your pseudocode is actually code and not prose instructions 1

Explanation / Answer

//Time complexity = O(2*(n1 + n2) - 1) = O(N)
//Space complexity = O(n1+n2)
//Solution using vector array.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main () {
int set1[] = {50,100,150,200,250}; //create first set
int set2[] = {500,400,300,200,100}; //create second set
int n1=sizeof(set1)/sizeof(int); //fetch size of set1
int n2=sizeof(set2)/sizeof(int); //fetch size of set2
std::vector<int> v(n1+n2); //create vector of size n1+n2 because maximum length of result can not exceed n1+n2
std::vector<int>::iterator it; //Iterator to access vector values
std::sort(set1,set1+n1); //sort first array
std::sort(set2,set2+n2); //sort second array
it=std::set_symmetric_difference(set1, set1+n1, set2, set2+n2, v.begin()); //calculate symmetric difference and store in v
v.resize(it-v.begin());
for (it=v.begin(); it!=v.end(); ++it){
std::cout<<*it<<" "; //print values of v
}
std::cout<<" ";
return 0;
}

//Time complexity = O(2*n1*n2) = O(N^2)
//Space complexity = O(n1+n2)
//Solution using Linked List.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef struct ll{
int val;
struct ll *next;
}L;
L *head=NULL;
int main () {
int set1[] = {50,100,150,200,250}; //create first set
int set2[] = {500,400,300,200,100}; //create second set
int n1=sizeof(set1)/sizeof(int); //fetch size of set1
int n2=sizeof(set2)/sizeof(int); //fetch size of set2
//Store all the values of set1 which ids not in set 2. This requires O(n1*n2) time complexity
for(int i=0;i<n1;i++)
{
int flag=0;
for(int j=0;j<n2;j++){
if(set1[i] == set2[j]){
flag=1;
break;
}
}
if(flag==0){
//Value is not present in set2. So, store that value to linked list.
L *tmp=(L *)malloc(sizeof(L *));
tmp->val=set1[i];
tmp->next=NULL;
if(head==NULL){
head=tmp;
}
else{
L *t1=head;
while(t1->next != NULL){
t1=t1->next;
}
t1->next=tmp;
}
}
}
//Repeat above step for another set i.e. set2. Time complexity = O(n1*n2)
for(int i=0;i<n2;i++)
{
int flag=0;
for(int j=0;j<n1;j++){
if(set2[i] == set1[j]){
flag=1;
break;
}
}
if(flag==0){
L *tmp=(L *)malloc(sizeof(L *));
tmp->val=set2[i];
tmp->next=NULL;
if(head==NULL){
head=tmp;
}
else{
L *t1=head;
while(t1->next != NULL){
t1=t1->next;
}
t1->next=tmp;
}
}
}
//Print linked list values
L *tmp=head;
while(tmp!=NULL){
cout<<tmp->val<<" ";
tmp=tmp->next;
}
cout<" ";
return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.