Question 1: A cable company needs to decide where to put a new service point in a small town where all houses are along one street. Let us view this street as a line and the houses on it have real numbered coordinates { 1, 2, … , }. The service point, p, should be chosen to minimize the total length of cables to all houses, that is, ∑ =1 | − |. Describe an efficient algorithm for finding the optimal location of the service point.
Question 2: A sorting algorithm is said to be stable if it preserves the initial ordering of elements with the same key. Stability of the underlying algorithm is essential for the radix sort algorithm. For the following sorting algorithms, check whether the algorithm is stable or not. If not, can you make it stable without affecting the asymptotic time complexity of the algorithm?
Question 3: Let = { , , , , , , } be a collection of objects with the following benefit-
weight value s: : (12,4). : (10,6), : (8,5), : (11,7), : (14,3), : (7,1), : (9,6). What is an optimal solution to the fractional knapsack problem for S, assuming we have a sack that can hold objects with total weight of 18? Show your work.
Calculate ratio (benefit/weight) for all values
Sort by ratio
Add entire object to knapsack from highest ratio to lowest until the entire object cannot be added to the knapsack. From there, take the largest fraction of that object that can fit into the knapsack and add it. Once we get here we are done.
The optimal solution was to add f, e, a, b, and 4/5 of c to the knapsack to get a value of 49.4
Question 4: Given an unordered sequence of n integers, describe an efficient algorithm for finding k items in the middle of an ordered version of the sequence. Give pseudo code of your algorithm.
