Solved-Assignment 4- Solution

Description

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?

Bubble sort, insertion sort, selection sort, quick sort, merge sort, heap sort.
Question 3: Let = { , , , , , , } be a collection of objects with the following benefit-weight

values: : (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.

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.

Put your answers in one file and submit to elearning.