Encode ' 01 Prelims

OSP Contest at Impetus 2001,
UVCE IEEE Student Chapter,
29th June 2001.



This programming contest is for 1 hour for a total of 100 points. You need not use any programming language, algorithms or pseudo code will do, wherever necessary. Good clean handwriting is essential as only what can be read can be graded. This paper is meant for your edification and can be retained, so please use the plain paper sheets provided by the organizers. The finals will have 6 teams competing for top honours. The OSP organiser's decision is final in all respects.

Please write your name, college, semester clearly and boldly on all the sheets.



Shorties ( 3 points each = 15 )

  1. Write a short expression / function / arithmetic / algebraic statement (less than 20 characters) for the following:

    1. Determine if a given number is a exact power of two or not.

      Return 0 for 2,4,8,16,... etc and 1 otherwise.

      x & (x -1 )

    2. The greatest common divisior of two numbers m, n.

      gcd (m,n)

      • ( m > n) := (n == 0) ? m : gcd (m, n mod m)
      • (m < n) := gcd (n,m)
    3. Given two integer x and n, determine the closest number greater than or equal to x where n is a power of two.

      Return 112 for x = 100, n = 16 and so on.

      x + n - x % n, optimally (x + n - 1) &(n -1)

    4. Determine a real function f(x) for all positive x such that f(f(x)) = -x.

      (x & 1) ? x - 1 : - (x +1)

    5. Given that all projects have a start date (ds) and end date (de), find out the projects active between any given [d1,d2] range ( >, < and == operators work on dates).

      Return 1 if a project is active between the fixed values [d1,d2] and 0 otherwise. Accept two dates ds and de as input.

      ((ds < d2) && (de > d1) ? 1 : 0


Moderates ( 8 points each = 40 )

  1. Given a stream of n -1 integers in random order with no duplicates from the range [0..n-1] how could you determine which one was missing? Optimal solution is linear time, constant space.

    sum them, == n ( n - 1) / 2. Subtract. If diff == 0, value = 0, else value = diff.

  2. Given an array of n integers which are positive and negative, collect all the positive ones at the start of the array and all the negative ones at the end of the array. Do not make more than n comparisions.

    Keep two indexs moving from left to right and right to left. Switch when necessary. Terminate when they cross.

  3. Given that you do not have the ability to print directly at any point on the screen but only have the normal ouput statements how can you optimally display a sine curve on the screen. You can assume that the \( \sin (\emptyset ) \) function exists.

    Assume / Obtain Max Min values for X and Y. Generate the points and store them in a structure in which all the points for one line are stored in a array / vector. Iterate over this data structure.

  4. Write a procedure to produce all the prime factors for an integer x in the most optimal manner.

    Test for divisibility by 2,3. Then starting at 5 to \( \sqrt{x} \) -1 iterate in steps of +2, +4 alterating. Determine prime for each such value.

  5. Given an array of n small integers, right rotate them by x locations using no other intermediate variables for storage.

    Swap ( a,b) without intermediate variables is easy :=). Swap x integers from the start with x integers from the end. Then swap all n -x integers from x onwards.


Bigzillas ( 15 points each = 45)

  1. In a sequence of n integers, determine the largest and second largest integer by using less 2 * (n -1) comparisions at worst. Determine the number of comparisions that your algorithm will take.

    Hash them. Takes n comparisions. Then 1 more to determine second largest. Total = n + 1.

  2. Accept two integers n and x. You have the marks for some n students for the subjects Physics, Chemistry, Mathematics, Biology. You are interested in finding the ratio between the marks in Physics and Mathematics. Determine the top and bottom x ratios.

    Maintain two sorted queues for the highest and lowest. Each new value is Binary Sorted into them (\( \lg x \) time) and inserted if required. This has to be done twice for all n integers, so \( 2*n*lg(x) \) at worst case. If n \( \approx \) x consider sorting the entire data ( \( n\lg n \) time).

  3. I bring you three inverted cups and tell you there is gold under one of them. You pick one, but before you open, I open one of the others and show you it is empty. Would you like to switch? If yes, why? If no, why?

    1. It does not matter. The probability of finding gold in the remaining two cups was equal in the beginning, and they are still equal now. The fact that you put your hand on one of them cannot increase or decrease its probability of having gold under it.
    2. If we repeated this experiment a million times, you would get the gold only one third of the time by sticking to your first cup. People who consistently switch would win the other two thirds. Therefore you should switch.



Greets go out to: uvce2000, ppr98, rsm, madhur, bharat, krishna_\( \pi \), leonara and the rest of the folks. So long and thanks for all the fish: Bjarne Stroustup, Ken Thompson, Vijayan, Jon Bentley, Donald E Knuth, Joy Joseph, Linus Torvalds. This paper along with answers and the paper to be used for the finals and the answers to that will be available at:

http://www.geocities.com/madhumkurup/program/InsightOSP01/OSP.html.

Madhu M Kurup,
mmk aT yahoo dASH inc dOT com,
Yahoo Web Services India Pvt Ltd.