Question

These questions are about an abstract data type for sets of integers. The representation used will be sorted lists without duplicates. To help answer the questions, the following pseudocode of merge-sort for lists may be useful. It is assumed head(x) and tail(x) return the head (first element) and tail (remaining elements) of a list, respectively, and a procedure is available for splitting a list into two lists of approximately equal size.

// returns sorted version of list x
mergesort(x):
        if x is empty or tail(x) is empty then return x
        split x into lists x1 and x2
        s1 = mergesort(x1)
        s2 = mergesort(x2)
        return merge(s2, s2)

// returns merge of sorted lists s1 and s2
merge(s1, s2):
if s1 is empty then return s2
if s2 is empty then return s1
if head(s1) < head(s2) then
        h = head(s1)
        s3 = merge(tail(s1), s2)
        add h to front of s3
        return s3
else
        h = head(s2)
        s3 = merge(s1, tail(s2))
        add h to front of s3
        return s3

(a) Describe an algorithm (preferably using pseudo-code) to determine if a number n is an element of a set s (a sorted list without duplicates) and give the worst case time complexity.

(b) Describe an algorithm to convert an arbitrary list of integers (not necessarily sorted or free of duplicates) to a set (sorted and without duplicates) and give the worst case time complexity.

(c) Describe an algorithm to compute the union of two sets and give the worst case time complexity (the union of two sets is the set of elements which are in either of the two sets).

(d) Describe an algorithm to compute the intersection of two sets and give the worst case time complexity (the intersection of two sets is the set of elements which are in both of the two sets).

(e) Briefly argue why this representation of sets is better than a representation which uses arbitrary lists.

Answer 1

(a) For this task we will use binary search approach . as we have given the sorted list we will take this advantage of this and we will build something by using binary search .Don't worry we will disscuss the binary search by using pseudo-code.  

Below is the pseudocode for binary search.The inputs are the set, which we call given_set; the number n of elements in set; and target, the number being searched for. The output is the index in array of target

1. Let min = 0 and max=n−1.
2. Compute guess as the average of max and min, rounded down so that it is an integer.
3. If set[guess] equals target, then stop. You found it! Return guess.
4. If the guess was too low, that is, set[guess] < target, then set min = guess + 1.
5. Otherwise, the guess was too high. Set max = guess - 1.
6. Go back to step two.

So the above approach is called binary search .

Worst case time complexity of the above algorithm :  log(n)

(b) As we know that in general, Merge Sort is the best-suited sorting algorithm for sorting linked lists efficiently. So,we have given the merge sort method we will use this method for our algorithm .

Algorithm.

1) Sort the elements using given Merge Sort.
2) Remove duplicates in linear time using the algorithm for removing duplicates in sorted Linked List.

Algorithm for merge sort

1. If: The list contains one or fewer elements, return the same list.
2. Else: Divide the list into halves using the splitting function.
3. Sort: Sort ​the two halves of the list.
4. At the end, merge the sorted lists

Algorithm for removing duplicates in sorted list :

Solutions Idea :

In this approach, we will iteratively traverse the entire List. Going to each node one by one, we will compare that node with the adjacent node. If the data value for both the nodes are the same it means that the node is duplicate. We will then de-link one of the duplicate nodes and will follow the same procedure for the rest of the nodes.

Solution Steps :

• We will store the value of the head(start) node into another variable say current.
• We will keep iterating through the linked list until we reach the end node.
• If there is a match of data values between a node and an adjacent node we will detach one of the nodes by saving its neighbour node’s address into the NextNode variable.
• We will then delete that duplicate node and attach the previous node of the deleted duplicate node with NextNode.
• We will keep doing the same for all duplicate nodes if encountered

Pseudo-code :

ListNode removeDuplicatedFromLL(ListNode head)
{
     ListNode current = head;
        
     while(current!=NULL && current.next!=NULL)
     {
         ListNode NextNode = NULL;
         if(current.data == current.next.data)
         {
             NextNode = current.next.next
             delete current.next;  
             current.next = NextNode;
         }
         else
             current = current.next
     }
}

Time Complexity: O(n)+O(nLogn) = O(nLogn) where N is the size of the list / linkedlist ;

(c) Using given Sort algorithm and we will use another search algorithm
Algorithm for finding Union :

1. Initialize union U as empty(list).
2. Find smaller of m and n and sort the smaller set.
3. Copy the smaller set to U.
4. For every element x of larger set, do following
   1. Binary Search x in smaller array. If x is not present, then copy it to U.
5. Return U.

Time complexity of this method : O((m+n)Logm, (m+n)Logn) where m and n are thre size of the sets .

(d) Using given sort algorithm(merge sort) and we will use another search algorithm (Binary serach):

Algorithm for finding Intersection :

1. Initialize intersection I as empty.
2. Find smaller of m and n and sort the smaller set.
3. For every element x of larger set, do following
   1. Binary Search x in smaller set. If x is present, then copy it to I.
4. Return

Time complexity of this method : O((m+n)Logm, (m+n)Logn) where m and n are thre size of the sets .

(e) The bigger downside of arbitrary lists is they fragment free memory and overwork the garbage collector. As an list expands, it creates new, bigger lists, copies the old list to the new one, and frees the old one. Memory fills with big contiguous chunks of free memory that are not big enough for the next allocation. Eventually there's no suitable space for that allocation. Even though 90% of memory is free, no individual piece is big enough to do the job. The GC will work frantically to move things around, but if it takes too long to rearrange the space, it will throw an OutOfMemoryException. If it doesn't give up, it can still slow your program way down. The worst of it is this problem can be hard to predict. Your program will run fine one time. Then, with a bit less memory available, with no warning, it slows or stops.representation of setst uses small, dainty bits of memory and GC's love it. It still runs fine when you're using 99% of your available memory.

Hope you got your answer !

if you still have any doubts please let me know in comment box . Thanks ! happy learning ;)