B.1 Design an algorithm and implement in C to printing all the duplicates in a g
ID: 3776668 • Letter: B
Question
B.1 Design an algorithm and implement in C to printing all the duplicates in a given list of unsorted integers. Input integers are in the range 0 to . The output should be a sorted (increasing order) list of duplicates and the algorithm should run with time complexity. Evaluate the run time complexity using ten different cases.
Design an algorithm and write a program to perform the following tasks. 10 marks
B2.1 Read 25 characters and build a binary search tree.
B2.2 Create another binary search tree by extracting all the ovals from the above tree. If there are no ovals in the input, output null.
B2.3 Create another binary search tree by extracting all the consonants from the above tree. If there are no consonants in the input, output null.
B2.4 What would be the number of comparisons required to generate (B2.2) and (B2.3)? Justify your answer.
3a) The weighted graph given below represents the seven different branches of a company located at different places. There are no exact edge weights between two edges. Instead, only partial information is available, such as the edge weights can be S (small), M (Medium) or B (Big), where S<M<B. With this partial information, construct a minimum spanning tree and discuss which edges are excluded and which edges are included in the spanning tree.
Antyakshari is a popular mode of entertainment in get-together parties. Design and develop a program to simulate a similar task. The program should do the fowling tasks.
Read words in a sequence, each word is separated by a space. Validate the input for following
i.Input should contain only alphabets and no characters are allowed
ii.Input should have minimum of two words and each word with at least two characters
Program should traverse the words in the following order
i.Read the first word, then determine lastLetter, which is the last character of this word. Go to nextWord, which is the word starting with lastLetter. The nextWord can be anywhere in the input sequence. If data has multiple words starting with lastLetter choose the nearest word as nextWord.
ii.Do not traverse a word more than once
iii.Stop when stoppingWord is encountered
iv.Print the words in sequence traversed and the length of traversal. Consider each word as length 1.
Comment on the data structure used and its limitations. Suggest any alternative approach to overcome the limitation if any.
Explanation / Answer
B1.
#include<stdio.h>
#include<stdlib.h>
void printRepeating(int arr[], int size)
{
int i, j,temp;
for(i = 0; i < size; i++)
{
for(j = i+1; j < size; j++)
{
if(arr[i]> arr[j])
{
temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
}
}
printf(" Repeating elements are ");
for(i=0;i<size;i++)
{
printf(" %d ", arr[i]);
}
}
int main()
{
int arr[] = {4, 2, 4, 5, 2, 3, 1,6,8,9,6,12,7,0,9,8};
int arr_size = sizeof(arr)/sizeof(arr[0]);
printRepeating(arr, arr_size);
getchar();
return 0;
}
Time Complexity: O(n*n)
b2.
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct node *create(struct node *);
void display(struct node *);
struct node *insertfront(struct node *);
struct node *insertlast(struct node *);
struct node *insert(struct node *);
struct node *delfront(struct node *);
struct node *dellast(struct node *);
struct node *del(struct node *);
struct node
{
char ch;
struct node *next;
};
int main()
{
struct node *hptr=NULL;
hptr=create(hptr);
display(hptr);
hptr=insertfront(hptr);
//display(hptr);
hptr=insertlast(hptr);
//display(hptr);
hptr=insert(hptr);
//display(hptr);
hptr=delfront(hptr);
//display(hptr);
hptr=dellast(hptr);
//display(hptr);
hptr=del(hptr);
//display(hptr);
return 0;
}
struct node *create(struct node *hptr)
{
struct node *first,*last;
char ch;
while(1)
{
printf("Enter the character 0 to quit");
scanf(" %c",&ch);
if(ch=='0')
break;
if(hptr==NULL)
{
hptr=(struct node *)malloc(sizeof(struct node *));
hptr->ch=ch;
hptr->next=NULL;
first=hptr;
}
else
{
last=(struct node *)malloc(sizeof(struct node *));
last->ch=ch;
last->next=NULL;
first->next=last;
first=last;
}
}
return hptr;
}
void display(struct node *hptr)
{
struct node *k;
k=hptr;
while(k!=NULL)
{
printf(" %c ",k->ch);
k=k->next;
}
}
struct node *insertfront(struct node *hptr)
{
struct node *first,*last;
//first=hptr;
char ch;
//char item;
printf("Enter the character ");
scanf(" %c",&ch);
last=(struct node *)malloc(sizeof(struct node *));
last->ch=ch;
last->next=hptr;
hptr=last;
display(hptr);
return hptr;
}
struct node *insertlast(struct node *hptr)
{
struct node *first,*last;
char ch;
printf("Enter the character ");
scanf(" %c",&ch);
last=(struct node *)malloc(sizeof(struct node *));
last->ch=ch;
last->next=NULL;
first=hptr;
while(first->next!=NULL)
first=first->next;
first->next=last;
display(hptr);
return hptr;
}
struct node *insert(struct node *hptr)
{
struct node *first,*last;
char ch,c;
printf("enter after which you want to insert");
scanf(" %c",&c);
first=hptr;
while(first->ch!=c&&first!=NULL)
{ first=first->next;
}
if(first->ch==c)
{
printf("Enter the element");
scanf(" %c",&ch);
last=(struct node *)malloc(sizeof(struct node *));
last->ch=ch;
last->next=first->next;
first->next=last;
}
return hptr;
}
struct node *delfront(struct node *hptr)
{
struct node *t,*first,*last;
t=hptr;
hptr=hptr->next;
printf("element deleted in front");
free(t);
display(hptr);
return hptr;
}
struct node *dellast(struct node *hptr)
{
struct node *t,*first,*last;
first=hptr;
while(first->next!=NULL)
{
t=first;
first=first->next;
}
t->next=NULL;
printf("element deleted last");
free(first);
display(hptr);
return hptr;
}
struct node *del(struct node *hptr)
{
char c;
//int ch;
printf("enter which node you want to delete");
scanf(" %c",&c);
struct node *temp,*prev;
temp=hptr;
while(temp!=NULL&&temp->ch!=c)
{
prev=temp;
temp=temp->next;
}
if(temp->ch==c)
{
prev->next=temp->next;
free(temp);
}
display(hptr);
return hptr;
}
B2
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include <ctype.h>
struct Stud
{
char name[20];
struct Stud *next;
};
struct Stud *hptr=NULL,*tptr;
void createList(char *s)
{
struct Stud *nptr;
nptr=(struct Stud *)malloc(sizeof(struct Stud));
strcpy(nptr->name,s);
if(hptr==NULL)
hptr=tptr=nptr;
else
tptr->next=nptr;
tptr=nptr;
nptr->next=NULL;
}
void display()
{
struct Stud *t;
for(t=hptr;t!=NULL;t=t->next)
printf("%s ",t->name);
}
void delnode(struct Stud **t)
{
if(hptr == *t)
{
hptr = (*t)->next;
hptr->next = (*t)->next->next;
free(*t);
return;
}
else {
struct Stud *current = hptr;
while(current->next != NULL && current->next != *t)
current = current->next;
current->next = current->next->next;
free(*t);
*t = current;
return;
}
}
int isStartVowel(struct Stud *t)
{
char ch = tolower(t->name[0]);
if(ch == 'a' || ch == 'e'|| ch == 'i' || ch == 'o' || ch == 'u')
{
return 1;
}
return 0;
}
void vowelRemove()
{
struct Stud *t= hptr;
for(;t != NULL; t = t->next)
{
if(isStartVowel(t))
{
delnode(&t);
}
}
}
void main()
{
int i;
char str1[20];
for(i = 0; i < 5; i++)
{
scanf("%s",str1);
createList(str1);
}
vowelRemove();
display();
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.