Assignment 2
Data Structures and Algorithms (Fall 2024)
BESE 29 (A, B, C)
Total Marks: 10
Due Date: 8th November 2024
[CLO-3]
Question 1
Consider the following code snippet:
void list::Game1 ( )
{
node* headref = head;
generated = NULL;
node* current = headref;
while (current != NULL) {
node* next = current->next;
Game2(current);
current = next;
}
head = generated;
}
void list::Game2 (node* newnode)
{
if (generated == NULL || generated->data >= newnode->data)
{
newnode->next = generated;
generated = newnode;
}
else {
node* current = generated;
while (current->next != NULL
&& current->next->data < newnode->data)
{
current = current->next;
}
newnode->next = current->next;
current->next = newnode;
}
}
a) Given a linked list (given below), perform a complete dry run of the algorithm and at each
iteration, display the structure of linked list.
head
14 25 4 7 9 17 12 21 NULL
Iteration Linked List (Structure)
generated=NULL
head current
NULL
14 25 4 7 9 17 12 21
b) What is the purpose of the given algorithm?
Question 2
void CocktailSort(int a[], int n)
{
bool swapped = true;
int start = 0;
int end = n - 1;
while (swapped) {
swapped = false;
for (int i = start; i < end; ++i) { //Forward pass
if (a[i] > a[i + 1]) {
swap(a[i], a[i + 1]);
swapped = true;
}
}
if (!swapped)
break;
swapped = false;
--end;
for (int i = end - 1; i >= start; --i) { //backward pass
if (a[i] > a[i + 1]) {
swap(a[i], a[i + 1]);
swapped = true;
}
}
++start;
}
}
int main()
{
int a[] = { 5, 1, 4, 2, 8, 0, 2 };
int n = sizeof(a) / sizeof(a[0]);
CocktailSort(a, n);
return 0;
}
a) Perform dry run and write the output after each forward and backward pass in the table below.
Pass
Starting value of i a (Elements in array after the pass)
(Forward/backward)
b) What is the worst-case time complexity of the above algorithm? Justify your answer.
