+1(978)310-4246 credencewriters@gmail.com
  

Description

Task

files:

merge_k.c

– You can only modify this file. Implement the required functions in it. You can write any other helper functions that you want to use in this file. Do not modify any other given file.

list.h

,

list.c

,

merge_k.h

,

merge_k_client.c

– merge_k_client.c has compilation and execution instructions given as comment.

run_data4_INCOMPLETE.txt

– Sample output file of the program as given (BEFORE students implement their part). Note that this HAS MEMORY LEAKS because it creates teh linked lists, but does not free them. After you mode the nodes in the sorted linked list, and print the list, you should free all its nodes.

run_data4_sol.txt

– Sample output file of the program behaviour AFTER you have correctly implemented your code. It has no memory leaks or errors.

data4.txt

– sample data file. This is a UNIX file (LF as End-Of-Line). The data file is in the format:k N1 val11 val12 … val1N1 N2 val21 val22 … val2N2 … Nk valk1 valk2 … valkNk E.g. 4 5 3 1 9 0 16 3 20 22 27 7 9 12 0 78 5 9 4 1 8  represents: k = 5 linked lists (and each following k lines gives a linked list: first the size and then the elements:) list of size 5: 3-> 1-> 9-> 0-> 16 list of size 3: 20-> 22-> 27 list of size 7: 9-> 12-> 0-> 78-> 5-> 9-> 4 list of size 1: 8

A method for merging k sorted linked lists into one big sorted list is to use a Min-Heap of the linked lists, using the data of the first node as the priority. So when comparing 2 (sorted) linked lists, you need to compare the value of the data in the first node of each list. The remove_min operation removes and returns the first node of the first list and readjusts the heap based on the new first node of that list. If the list becomes empty it is removed from the heap. (See the expected data behavior shown below)

You are given the implementation of common functions on linked lists in list.c file and client code, merge_k_client.c, that reads data for k lists, puts the lists in an array of lists, calls methods to sort the lists, to rearrange the array into a Min-Heap and to use the min heap to merge the k lists into a sorted list.

Requirements:

The file merge_k.c has placeholders for methods you need to implement. You can add any helper functions in that file. You cannot modify any other file (you cannot modify any header file either). Implement the correct functionality for the methods in merge_k.c:void sort_list(nodePT L);  nodePT make_heap(int k, nodePT heap[k]);   nodePT remove_min(int* k, nodePT heap[(*k)]); nodePT merge_k(int k, nodePT heap[k]);

Note that even though remove_min() is not called in the given client code, it may be called by other testing code, so it has to be implemented.

Implement insertion sort to sort the given linked lists.

Read the comments in the given files (.c and .h files) as they explain the process.

The buildMaxHeap() pseudocode in slides gives the process for turning an array into a heap.

The k linked lists should be merged by MOVING the existing nodes from the k lists into the result list. Your code should NOT create any new node. (Do NOT create new nodes and free the old ones.)

The print_list_pointer() function prints both the data and the memory address for each node s.t. it can be easily checked that a node was moved (e.g. as part of insertion sort or when removing it from heap and moving it in the result list).

There should be no errors when ran with Valgrind. See Code page for an example of Valgrind output with no errors.

Notes:

Pseudocode for all the functionality related to the Heap is provided in the slides. But there it is assumed that the data in the heap is stored starting at index1, (so at indexes 1 to N), whereas in your code it will be stored starting at index 0 (so indexes 0 to (N-1)). Why this change? So that a) you see how it works with index 0 as well, b) you have to make some changes, as opposed to just copying the code from the sides.

When starting from index 0, the index calculations are modified as follows: for a node at index i, the index of the parent is floor((i-1)/2) (instead of floor(i/1)) and for the children 2i+1 and 2i+2 (instead of 2i and 2i+1).

In the slides the pseudocode is for a Max-Heap (where the max is at the top and the max is removed), you have to implement a Min-Heap (where the min is at the top and the min is removed by a remove_min operation). Why? Because that is what is needed here and again, you have to modify something and simply copy from the slides.

The buildMaxHeap() pseudocode in slides gives the process for turning an array into a heap.

Expected behavior of data (for data given in data4.txt):

Table with lists before sorting:
3 1 9 0 16
20 22 27
9 12 0 78 5 9 4
8

Table with lists after sorting:
0 1 3 9 16
20 22 27
0 4 5 9 9 12 78
8

Table rearranged as Min_heap:
0 1 3 9 16
8
0 4 5 9 9 12 78
20 22 27

Afer removing one node (i.e. after one remove_min operation)
(It removes the 0 from 0 1 3 9 16 and readjusts the heap by swapping
1 3 9 16    with
0 4 5 9 9 12 78)
0 4 5 9 9 12 78
8
1 3 9 16
20 22 27

After another remove_min
1 3 9 16
8
4 5 9 9 12 78
20 22 27

After another remove_min
3 9 16    // no actual lists swapped in Heap as 3 is still min
8
4 5 9 9 12 78
20 22 27

What is the time and space complexity to use MinHeap to merge k SORTED linked list? (This is part of the work in Task 1. For Task 1, you DO need to sort the linked lists, but here I am asking for the time complexity of the work needed to merge them after they are sorted, using the MinHeap. Assume the number of nodes in all the lists is N (that is N is the sum of the number of nodes in each list).

Write your answer in

time_space.txt

Submit your own test file. It must have the same format as the given one, the code can read it. It shoud have a different number of linked lists (k). There is no requirement on the linked lists data.

If your code does not work for your test file, yous still get the points for the test file itself.

The file must be in UNIX format.

Name the file student.txt.

update:

run_data4_sol.txt (Links to an external site.)

– Updated 4/6, 1:42pm (because of my debugging phase it was missing the bottom work with merging and printing the sorted list. CLICK REFRESH ON THE PAGE WITH THE .txt file) Sample output file of the program behavior AFTER you have correctly implemented your code. It has no memory leaks or errors.

run_data4_sol_DEBUG.txt (Links to an external site.)

– Added 4/6, 2:10pm. It prints the sorted list and the heap after each node removal from the heap and added in the sorted list. You should NOT print all the debugging information in the program you submit. I posted this to help you understand how the data (the nodes) should move throughout the execution of the program.

  
error: Content is protected !!