Answer Happy

Design and analysis of algorithm
In a BBC tower, there are n floors and m lifts(m<=n). Every lift will start from a designated floor and terminates at a designated floor. All the lifts move from lower floor to a higher floor. A lift may stop in all the intermediate floors or may stop at a few intermediate floors or may not stop at any of the intermediate floors. The information about every lift is given in the form of a four tuple like : (Lift-i, source-j, destination-k, stops- I, f), where j>k, j</<f<k which means that the lift 'i' starts at floorj, terminates at floor k with stops at floors 1 & f. For example, (lift-3,source-7, destination- 17,stops -6,8 ) means that the lift -3 starts at the 7th floor and terminates at the 17th floor which stops at 6 and 8th floor. (lift-6, source-3, destination-15, stops -nil) means that the lift -6 starts at the 3rd floor and terminates at the 15th floor which does not stop at any level. A person who wants to use the lift will give his request information with source floor (the floor where he enters the lift) and the destination floor. User request information will be in the form of Two Tuple -(Usersource -p, Userdestination -f). For example, (Usersource-7, Userdestination-18), means that the user enters the lift at the 7th floor and wants to reach 18th floor. A sample "lift information” will look like 1. (Lift-1, source-o, destination-22, all) 2. (Lift-2.source-O, destination-22, even numbered floors) 3. (Lift-3, source-10, destination-20,all) 4. (Lift-4, source-o, destination- 10,all) 5. (Lift-5, source-5, destination-21,odd numbered floors) 6. (Lift-6, source-15, destination-20,nill) 7. (Lift-7,source-6, destination-22, even numbered floors) 8. (Lift-8, source-21, destination- 22,all) 1. Given all the information about all the lifts and user-request information, design an algorithm "LComb" to return all the possible sequence of lifts that can be used by the user to reach the destination floor, starting from the source floor. Your algorithm should return all the possible sequence of lifts that has to be used by the user for the purpose. For example, if the above sample input along with the user-request: (Usersource-7, Userdestination-21), is given to the algorithm "LComb”, the algorithm should return [(L4,L5,L8), (L1), (L4, L1) etc.]. [7m] 2. Analyze your proposal in terms of complexity and check whether the solution you had derived is optimal. [3m]