ADS MODULE 2
Question 1:
Event Scheduling with Heaps
You are tasked with managing a system that schedules events based on their start time.
Events must be processed in the order of their start time. You are given a list of events, where
each event is represented as a tuple (event_name, start_time). For example:
events = [ ("Meeting", 9), ("Workshop", 11), ("Conference", 10), ("Presentation", 14),
("Lunch", 12), ("Interview", 13)]
a) Illustrate the advantages of using a heap for this scheduling problem compared to a
simple sorted list or array?
b) Design and develop a code to manage the event schedule using a Min-Heap. Show
how to insert all the events into the Min-Heap step-by-step, ensuring that the event
with the earliest start time is at the root. Implement a code to Allow the user to
change the priority of a specific event and Re-heapify the heap to restore the heap
property after the priority change.
c) Once all events are inserted, simulate the event processing by removing events one
by one from the heap. Show the order in which events will be processed. After
processing, a new event ("Emergency Meeting", 8) needs to be added. Insert this
event into the existing heap and show how the heap structure adjusts. Analyze the
time complexities of heap construction, event removal, and insertion operations, and
compare them with array-based and linked list–based priority queues.
Question 2:
Optimizing Task Scheduling Using Heap Sort
In TaskManager, the system uses a heap data structure to prioritize and sort tasks based on
their urgency levels. You are the system architect responsible for implementing a heap sort
algorithm to ensure that tasks are executed in the correct order. The task list starts unsorted,
and you need to perform a series of operations to manage the task scheduling efficiently.
Operations to Perform:
a) Discuss the advantages and disadvantages of using heap sort compared to other
sorting algorithms like quicksort or merge sort.
b) Design and implement a code for extracting high prioritized elements after
constructing the max heap and create the process of sorting the array using heap sort.
Include the intermediate states of the array after each extraction of the maximum
1
[Link] implementing heap sort, develop the code to measure and output the
number of comparisons and swaps performed during the heap construction and
sorting process.
c) You are given the following urgency levels for tasks: [8, 3, 5, 4, 1, 7, 6, 2]. Using the
Heap Sort algorithm, arrange them in ascending order. Demonstrate step-by-step
how the max heap is built from the unsorted array, showing the array representation
after each heapify operation, and then illustrate how elements are extracted one by
one to achieve the final sorted order. Finally, analyze the time complexity of building
the heap, performing all extractions with re-heapification, and the overall Heap Sort
algorithm, and compare these complexities with Merge Sort and Quick Sort.
Question 3:
Merging Data Streams Using Heaps
You are managing data streams from two different sensors. Each sensor provides time-
stamped data points in increasing order of time. Your task is to merge these two data streams
into a single, continuous stream of time-ordered data points.
Sensor 1 provides data: [(1, 10), (4, 15), (5, 20)]
Sensor 2 provides data: [(2, 12), (3, 18), (6, 25)]
a) Discuss the role of a min-heap in merging multiple sorted data streams into a single
sorted output? Illustrate why the heap-based approach more efficient than simply
concatenating all streams and then sorting them?
b) Use a Min-Heap, develop a code to merge these two data streams into one. Start by
inserting the first data point from each sensor into the heap. Design and develop a
function that removes the given data point from the Min-Heap and adjusts the
structure accordingly.
c) Two sorted data streams from different sensors are to be merged using a min-heap.
Construct the min-heap by merging the two streams and produce the merged sorted
sequence. After merging, a new data point (7, 30) from Sensor 2 arrives; insert this
element into the min-heap and show the updated merged stream. Next, demonstrate
how to delete a specific data point, for example (2, 12), from the heap while
maintaining the min-heap property. Finally, update an existing data point, changing
(5, 20) to (5, 22), by developing an update operation for the min-heap. Analyze the
time complexity of each operation—heap construction, insertion, deletion, and
update.
2
Question 4:
You are working as a software engineer for a task scheduling system. The system maintains a
dynamic set of tasks, each with a priority level, and must efficiently schedule and process
tasks based on their priority.
You are given the following array of task priorities: 5, 37, 82, 15, 69, 54, 8, 91, 20, 47, 63,
29, 75, 6, 42, 98
Tasks:
a) Discuss why heaps are suitable for implementing priority queues. Describe the
heapify process (both upward and downward) and its role in heap construction.
b) Design and develop an algorithm to build a heap using two approaches: Successive
insertions with upward heapification (Top-down approach) and Heapify from the
last non-leaf node downwards (Bottom-up approach).
c) Convert the given array into a Max Heap and a Min Heap, showing the array or tree
representation after construction. Delete all elements from both heaps and note the
order in which elements are removed. Explain the sorting order observed for Max
Heap and Min Heap. Compare the time complexities of building a heap using the
top-down and bottom-up approaches. Explain why one approach is more efficient
than the other.
Problem 5:
DNA Sequence Analysis Using Knuth-Morris-Pratt (KMP) Algorithm
You are a bioinformatics analyst tasked with finding specific patterns in DNA sequences.
You need to implement the Knuth-Morris-Pratt (KMP) algorithm to efficiently search for a
sequence.
Operations to Perform:
DNA Sequence:
ACGTACGTAGCTAGCTA
Pattern to Search:
GTA
a) Explain the purpose of the Longest Prefix Suffix (LPS) array in the KMP
algorithm. How does it help reduce the number of comparisons when searching for a
pattern in a text?
3
b) Design and develop the KMP algorithm to search for the pattern GTA in the given
DNA sequence. Show the steps taken during the search process, including the
construction of the longest prefix-suffix (LPS) [Link] your implementation to
handle multiple patterns (e.g., GTA, ACG). Show how the KMP algorithm processes
each pattern and the results of the searches. After successfully finding the patterns,
create a function to count how many times each pattern occurs in the sequence.
c) Analyze the time complexity of the KMP algorithm in terms of the lengths of the
text and the pattern. Compare the efficiency of KMP with the naive string matching
approach in terms of worst-case behavior.
Question 6:
Efficient Domain Name Storage for a DNS Server
A DNS server stores millions of domain names and frequently searches for these domain
names to resolve them to IP addresses. Given the following domain names:
"[Link]", "[Link]", "[Link]", "[Link]",
"[Link]"
a) Describe the structure of a standard trie and a compressed trie (Patricia trie).
Illustrate how does a compressed trie differ from a standard trie in terms of node
representation and storage efficiency?
b) Design and develop an algorithm to Search for the domain "[Link]" in the
compressed Trie and trace the search path.
c) Construct a Compressed Trie to store these domain names. Show how the structure
of the compressed Trie differs from a standard Trie, emphasizing where compression
[Link] a new domain name "[Link]" to the Trie. Show how
the compressed structure changes and explain how compression helps reduce
memory usage. Compare the time complexity of searching for a domain name in a
compressed Trie versus a standard Trie.
Problem 7: Text Search in a Document Using Rabin-Karp Algorithm
You are developing a text editor and need to implement the Rabin-Karp algorithm to find a
specific word in a document efficiently.
Operations to Perform:
Document Text:
The quick brown fox jumps over the lazy dog.
4
Word to Search:
fox
a) Illustrate the working principle of the Rabin-Karp algorithm for pattern matching.
Describe the rolling hash technique used in the Rabin-Karp algorithm. How does it
help in computing hash values of successive substrings efficiently?
b) Design and develop the Rabin-Karp algorithm to search for the word fox in the
document. Show the hash calculations during the search process. Extend your
algorithm to search for multiple words (e.g., fox, dog). Display the positions where
each word is found in the document. Develop a function to replace all occurrences of
a specific word with another word (e.g., replace fox with cat). Show the modified
document text.
c) Analyze the average-case and worst-case time complexities of the Rabin-Karp
algorithm, and how they are influenced by the hash function and the number of
hash collisions. Compare the time complexity of Rabin-Karp with the naive string
matching algorithm and discuss scenarios in which Rabin-Karp performs
significantly better.
Problem 8: Plagiarism Detection Using Boyer-Moore Algorithm
You are developing a plagiarism detection system for academic papers. You need to use the
Boyer-Moore algorithm to find instances of suspected copied text.
Operations to Perform:
Original Text:
The quick brown fox jumps over the lazy dog.
Suspected Text:
brown fox jumps
a) Discuss how the Boyer-Moore algorithm improves pattern matching efficiency
compared to the naive approach. Focus on the mechanisms it uses to skip sections of
the text. Discuss the benefits of using the Boyer-Moore algorithm over naive string
matching methods.
b) Design and develop the Boyer-Moore algorithm to search for the suspected text in the
original text. Show the search process step-by-step, including the character shifts.
Modify the algorithm to handle cases where the suspected text has variations (e.g.,
brown Fox Jumps). Show how the algorithm can still identify the [Link] finding
matches, develop a function that calculates the similarity percentage between the
original and suspected texts.
c) Analyze the best-case, average-case and worst-case time complexities of the Boyer-
Moore algorithm, and how the use of its heuristics affects performance. Compare the
5
time complexity of Boyer-Moore with the naive string matching algorithm and
discuss scenarios in which Boyer-Moore performs significantly better.
Problem 9: Auto-Completion System Using Trie
You are building an auto-completion feature for a search engine. The system should suggest
possible completions for a partially entered query using a Trie data structure.
Operations to Perform:
Initial Set of Words: apple, app, application, bat, ball, batman.
a) Compare a standard trie and a suffix trie in terms of their structure, the type
of data they store, and the kind of string queries they efficiently support.
Describe how searching for a prefix in a standard trie differs from searching
for a substring in a suffix trie.
b) Design and develop a function to find all possible completions for the prefix
‘app’. Display the list of suggested completions. Create a function to delete the
word application from the Trie. Show the Trie structure after the deleting the
word ‘ball’.
c) Construct a standard trie by inserting all the given words. Illustrate the trie
structure after all insertions. Convert the constructed standard trie into a
compressed trie (Patricia trie). Show the compressed trie structure. Using
the compressed trie, insert a new word “appetite” into the compressed trie
and show the updated trie structure. Discuss the time complexity of
insertion, search for completions, and trie compression, and explain why
compressed tries are more efficient in terms of space and search time.
Problem 10: Spell Checker Using Trie
You are tasked with creating a spell-checking feature for a text editor. The feature will use a
Trie to suggest corrections for misspelled words.
Operations to Perform:
Initial Dictionary Words: cat, cut, cart, com, dog, dot, dive.
a) Compare standard tries, compressed tries, and suffix tries in terms of Storage
efficiency, Search operations (prefix vs substring), Use cases.
b) Design and develop a Trie to store the initial dictionary words. Show the Trie
structure after all words have been inserted. Implement a function to check if the word
‘cot’ exists in the Trie. If it doesn’t, suggest similar words by finding words with a
6
one-character difference. Develop a function that returns all words in the Trie that
start with the prefix ‘do’. Display the matching words.
c) Construct a standard trie by inserting all the given words. Show the trie structure
after all insertions. Convert the constructed standard trie into a compressed trie
(Patricia trie). Show the compressed trie structure after conversion. Choose one of
the words, e.g., "dive", and construct a suffix trie for it. Show how all possible
suffixes of the word are represented in the trie. Analyze the time complexity of
insertion and search operations in each trie type.