Probs

TRYST- 2008 Algorythms – Prelims Team Number: Team name: Member 1: Member 2: College: Contact Number:

Start time: Submission time: Contact Number:

Instructions: The paper has 15 questions. The total allotted time is 90 minutes. You are required to write solutions or algorithms in English, no code is expected. Write your answers in the space provided only. Points for each problem are written against it. Happy solving and have fun!!!

Q1.)

Given an array of n numbers, find the k­ smallest numbers efficiently.(10)

Q2.) An array of numbers is said to be k­shuffled if each number of the array is at a position not  more than k away from its position in the sorted array. Give an efficient algorithm to sort a k­ shuffled array.(10)

Q3.) What is the minimum number of times pen must be lifted from the page to while drawing  each of the following figures: (7)

Q4.) How will you place 24 rooks on a chess board so that if you remove any 20, at least 2 of the  remaining 4 are always attacking.(5)

Q5.)

Chess­board problem (4+4=8)

Figure 1

Figure 2

a.) Two opposite corner squares are deleted from an 8*8 chess board as shown in figure 1 above.  Prove the remaining squares cannot be covered exactly by dominoes (rectangles consisting of two  adjacent squares.)

b.) Two squares from each of two opposite corners are deleted as shown in the figure 2 above.  Prove that the remaining squares cannot be covered exactly by copies of the “T­shape” and its  rotations. 

Q6.) There are three people A, B and C each having a secret number a,b and c respectively. Any  two people can communicate with each other without the third person knowing. Give a strategy so  that each of them gets to know the sum of the three numbers without knowing the numbers of the  other two people.(4)

Q7.) Replace the same characters by the same numerals so that the mathematical operations are  correct.(10) ALFA + BETA + GAMA = DELTA

Q8.) There is a building with 100 floors. You are given 2 special types of eggs. Now, there is a  floor F on the building such that if you drop any egg from this floor or higher, then the egg would  break and if an egg is dropped from a lower floor, the egg will not break. Your goal is to find this  floor F. The only operation you can perform is to drop an egg off some floor and see what happens.  If the egg breaks, it cannot be reused but if does not break, you can reuse it. What is the minimum  number of times, you'll have to drop the eggs to find F. (7)

Q9.) Let G = (V,E) be an undirected graph with weights on the edges. You are given that the  number of edges on the shortest path between u and v is at most k. Give an order(k*E) algorithm to  find the shortest path between u and v.(8)

Q10.) There is a circular track on which there are 'n' refueling stations from where you can get a  fixed amount of fuel. F­i(amount of fuel from i­th station.) The total amount of fuel is exactly equal  to the fuel needed to go round the track once. You begin your journey with empty fuel in your  vehicle. When you come at a fuel station, you take the fuel available. If your fuel ends somewhere  in the middle of the journey, you are stuck. Give an efficient algorithm to find a starting point so  that you don't get stuck anywhere in during the one trip of the track. Assume that you start from a  fuel station. (No points for n^2 solution) (15)

Q11.) You are given an undirected graph G with weights on the edges and the minimal spanning  tree T of the graph. Now an edge is added to G to obtain a new graph G’. How will you compute  the minimal spanning tree for the new graph efficiently?(8)

Q12.) There is a box containing n balls numbered from 1 to n. The box was emptied by taking  balls randomly out of the box. You are given for each ball, how many balls numbered higher than it  were taken out before it. How will you find the order in which the balls were taken out?(12)

Q13.) A sequence of numbers a1,a2..... an is said to be anti monotonic if  a1 > a2 < a3 > a4 < a5..... an. Given a sequence of numbers, find the length of the longest anti­monotonic subsequence of the given  sequence.(No points for n^2 algorithm).(15)

Q14.) You are given a histogram. How will you find the maximum area of a rectangle contained  totally inside it? (No points for n^2 algorithm.)  (15)

Q15.) Hexagons Find a loop(cycle) through the centers of some of the hexagons in the diagram subject to the  following constraints. The cycle 1.) proceeds from one hexagon to an adjacent hexagon through the center of each hexagon, 2.)  passes through no hexagon more than once,  3.) does not go through any numbered hexagon, and  4.) never makes a sharp­angled turn (i.e., a turn at a 60o angle). 

Each number indicates how many of the adjacent hexagons are part of the path. (15)