Algorithms Answers

Robotics club has organized a Robothon. n robots are placed along

the edge of a circular area at the middle of the OAT. Each robot will move along arbitrary tracks inside the circle while leaving behind a heat signature along its trail. However, they have been programmed not to cross their own trail or the trail of another robot, neither will they ever move out of the circle. In case a pair of robots i and j meet at any point, they are removed from the scene and the club will pay a reward sum of M[i, j] to the owners of these robots. Note that some robots can keep moving infinitely without ever meeting another one. Given the reward matrix M where

M[i, j] = M[j, i], design a polynomial time algorithm that determines the maximum money the club might potentially end up spending. For this particular problem, give a very brief justification of the recurrence.

Mr. Monkey is in a garden, and stands in front of a row of banana trees. Let the trees be numbered as t1, t2, · · · tn as usual. He will start walking from some point, say s which is to the left of the leftmost tree. From this point, assume that he moves only to his right. Once he reaches a tree, he has two choices - either to walk past it or climb it and eat exactly one banana. Eating a banana make him jump a some distance over a few trees. In case he lands on the ground, he can continue the above exercise from that point. In case the first jump lands him on a tree, he can either climb down and continue the exercise or he can eat the bananas from there and continue jumping.

Let dist be an array that contains the distance of ti from the starting point s and jump be an array that contains the distance that Mr. Monkey can jump if he eats a banana from ti

Write an O(n*2) algorithm that determines the maximum distance that Mr. Monkey can jump. Note that this does not include the distance he walks or climbs.

What is the memory representation of a triangular matrix

The winner of “Any Destination Contest” was given an P18,000 gift certificate that could be          used to buy a ticket to any of the following destinations.

Code Name

Country

Ticket Price

HK JP KO US UK AF CA

Hongkong Japan Korea United States United Kingdom Africa Canada

12,000 15,000 17,000 24,000 25,000 26,000 28,000

The winner must input the code name of the country he wishes to go to; the country name and amount to be paid should be displayed afterward.

16-20. Code Name = CA 21-25. Code Name = US 26-30. Code Name = AF

The distance between two cities (in km.) is input through the keyboard. Write an algorithm and pseudocode to convert and print this distance in meters, feet, inches, and centimeters.

Write the applications of the Heapsort algorithm and explain time complexity.

 Develop an algorithm that reads in three numbers and writes them all in sorted order, create a flow chart and pseudo code.