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.

    2. The greatest common divisior of two numbers m, n.
    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.

    4. Determine a real function f(x) for all positive x such that f(f(x)) = -x.
    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.


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.
  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.
  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.
  4. Write a procedure to produce all the prime factors for an integer x in the most optimal manner.
  5. Given an array of n small integers, right rotate them by x locations using no other intermediate variables for storage.


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.
  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.
  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?





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.