Prelim. Exams: Design and Analysis of Algorithms Fall 2022
Design and Analysis of Algorithms
Problem #l
Suppose that you are given an input sequence of n elements in the form of nlk subsequences, each containing k elements.
- Design an algorithm to sort all nlk subsequences. What is the time complexity of the algorithm?
- Design an algorithm to merge the nlk sorted subsequences into one sorted sequence. What is the time complexity of the algorithm?
Problem #2
Show the hash table after you insert the keys 5, 28, 19, 15, 20, 33, 12, 17, 10. Show the same hash table after collisions are resolved by chaining. Let the hash table have 7 slots and let the hash function be h(k) = k mod 7.
Problem #3
Professor Gekko has always dreamed of inline skating across North Dakota. He plans to cross the state on highway U.S. 2, which runs from Grand Forks, on the eastern border with Minnesota, to Williston, near the western border with Montana. The professor can carry two liters of water, and he can skate m miles before running out of water. The professor will start in Grand Forks with two full liters of water. His official North Dakota state map shows all the places along U.S. 2 at which he can refill his water and the distances between these locations. The professor's goal is to minimize the number of water stops along his route across the state. Give an algorithm by which he can determine which water stops he should make. Analyze the running time.