Data Structures Lab PCCSL307 KTU 2024 Scheme - Dr Binu V P

  📌  Problem Idea You are given  K sorted lists . You want to merge them into  one final sorted list . Instead of merging two lists at a time (which can be slow), you use a  min-heap  to  efficiently find the smallest element  among all current nodes. ⚙️  Naive Approach Concatenate all lists into one. Sort the combined list. ❌  Time Complexity:  O(N log N) (where N = total number of nodes) ✅  Optimized Approach — Using a Min-Heap (Priority Queue) Idea Maintain a  min-heap  containing the  first node  (smallest element) from each of the k lists. Repeatedly: Extract the  minimum node  from the heap. Append it to the result list. Insert the  next node  from the same list into the heap (if it exists). This way, the smallest available element is always efficiently found in  O(log k)  time. 🧠  Algorithm Input: k  sorted linked lists Output: A single sorted linked list Step...

Create a text file that contains the names and marks of students in a class.Then, read the data from the file, apply the Quick Sort algorithm to sort the students based on their marks in decreasing order, and store the sorted data back into a file This is a very practical file handling + sorting algorithm problem 👏. 🎯 Goal You need to: Create a text file that contains student names and marks. Read data from that file. Sort students by marks in decreasing order using Quick Sort . Write the sorted data back to a new file. 🧠 Algorithm Input Format (in text file) Alice 85 Bob 92 Charlie 78 David 95 Eve 88 Steps Read the data from file Open the input file (e.g., students.txt ) in read mode. Read each line → extract name and marks . Store them in an array of structures. Apply Quick Sort Choose a pivot (first or last element). Partition the array so that: Marks greater than pivot are on the left (for decreasing order). Marks sma...

  🧩 Problem: Merge k Sorted Linked Lists You are given k sorted linked lists. Your task is to merge them into one sorted linked list efficiently. ⚙️ Naive Approach Concatenate all lists into one. Sort the combined list. ❌ Time Complexity: O(N log N) (where N = total number of nodes) ✅ Optimized Approach — Using a Min-Heap (Priority Queue) Idea Maintain a min-heap containing the first node (smallest element) from each of the k lists. Repeatedly: Extract the minimum node from the heap. Append it to the result list. Insert the next node from the same list into the heap (if it exists). This way, the smallest available element is always efficiently found in O(log k) time. 🧠 Algorithm Input: k sorted linked lists Output: A single sorted linked list Steps: Create a min-heap (using array or priority queue). Insert the head node of each linked list into the heap (store value + pointer). Initialize an empty result list (using dummy node). ...