CSC 15 Lab 4: Functions, Loops, and Arrays

	              Due in one week.


This class will ask you to write series of functions using loops and
arrays.  The first part is to be done directly in interactive
Python.  The second part should be written as a separate program.  
Only the second part should be submitted.


PART I: Preliminary Drills on Loops and Arrays:

The following problems should be completed inside the Python
interactive interpreter (it will not be collected, and are only
provided for your benefit).

a. Write a while loop that prints every even number from 0 to 100, inclusive.
I.E. the first value should be 0, then 2, then 4, etc... and the last number
should be 100.  Think carefully about how the loop should start and when it
should end.

b. Write a while loop that prints every odd number between 0 and 100 BACKWARDS,
i.e., 99, 97 ...

c. Write a while loop that constructs an array of all odd numbers
between 0 and 100 backwards.  Hint: start with an empty array A = []
then use A.append(...) in your loop.

d. Write a function that take as a parameter n, and returns an array of all odd
numbers from 1 to n.  If n is 0 or negative, then the function should return []
That, is complete the following:

def oddsUpTo(n):
...

So that, for example, calling 

print oddsUpTo(8) 

will print [1,3,5,7]  (i.e., the function should return [1,3,5,7])

The following is an example of a function that returns an array (of binary 
factors of n)
def binfactors(n):
  F = []  # array to be returned
  power = 0
  while n>0:
    if (n%2==1): F.append(2**power)
    n = n/2
    power += 1
  return F
#binfactors

print binfactors(147)   # prints [1, 2, 16, 128]



e. Write a function that takes an array as a parameter and returns the number
of positive numbers in the array. That is, complete the definition of:

def positives(A):
...

so that, for example, calling positives([-2,-5,1,0,7,-6]) will return 2, 
because there are two positive numbers in this sample array.

REMEMBER that you functions must work for any input array, and do not use
input/print statements inside the function.  Only print outside the function.


-----------------------------------------


PART II: Write the following functions in Python.  Everything should be in 
the same file.

0. Write a function that reverses an array.  For example, 
   reverse([2,4,5,7]) should return an array [7,5,4,2].  Hint: do not
   try to change the existing array.  Contruct a new array starting from [].


1. Write a function largesti that returns the INDEX of the largest
   element in an array (which is passed in as a parameter).  If there
   are multiple occurrences of the largest element, the function should
   return -1.  For example, largesti([2,4,1,7,3]) should return 3, since
   the largest element, 7, is at position 3.  largest([4,1,6,2,6]) should
   return -1 because there's a tie.

   Devise several function calls to make sure the code is working correctly.
   e.g. 
   largesti([2,4,1,7,3])

Example: the following function returns the index of x in A, or -1 if
x is not in A:

def indexof(x,A):
  answer = -1; // -1 means x not found in A
  i = 0 # indexes A
  while answer==-1 and i<len(A):
     if A[i]==x: answer = i
     i += 1
  # while
  return answer
#indexof


2. Write a function 'minnn' that takes an array as a parameter and returns 
   the smallest NON-NEGATIVE NUMBER in the array.  For example,
   calling minnn([4,2,-4,1,-5,7]) should return 1, which is the smallest
   non-negative number.  If all the elements in the array are negative, your
   function should return 0.  


3. Write a function that takes an array as a parameter and returns a new 
   array, with every element in the original array doubled.  Call the
   function twox.   For example, twox([1,4,6,8]) should return 
   [2,8,12,16].  It constructs a NEW array with every element in the
   parameter array doubled.  Hint: start with an empty array B =[] and
   use append.

   Devise sample calls ...

4. Write a function that takes an array as a parameter and return an
   array that contains EVERY OTHER ELEMENT of the input parameter.
   for example, calling your function every other([1,3,2,6,4,8]) should
   return the array [1,2,4].  The first element of the array should always
   be included.  If the input parameter is the empty array [], the
   function should also return [].


5. Write a function that takes two arrays as parameters and interleaves 
   them.  For this problem if the two arrays are not of the same length,
   you can return the empty array [].
   For example, interleave([1,3,5,7], [4,6,8,9]) should return the
   array [1,4,3,6,5,8,7,9].

----------------------  Optional but Recommended: --------------------------


6. (Mild Challenge)
   Write a function that returns the INTERSECTION of two arrays.  The
   intersection is the array that contains all elements that belong to
   both input arrays: For example, intersection([3,1,5,2],
   [8,4,1,6,3]) should return [3,1] (or [1,3], which is fine too),
   which is contains all elements that belong to both arrays.  Duplicates
   are fine (the intersection may contain duplicate elements as long as 
   the elements are also duplicated in both input arrays).

   Hint: to find the intersection of A and B, go through each element of
         A and check if its also in B.  Use the built-in 'in' operator.
	 to test if an element is contained in an array.


7a. KILO-Challenge: Write a function that takes an array parameter and return
    the same array without duplicates.  For example, calling
    nodups([3,4,1,3,5,1] should return [3,4,1,5].  All duplicates are
    removed.  Hint: don't try to delete an element from an array.  Instead,
    construct a new array, starting from [], that does not include
    duplicates.


7b. MEGA-Challenge:  Modify problem 1 so that the function returns an array
    containing the indices of all occurrences of the largest element.  For
    example, largests([3,5,8,2,8,4]) should return [2,4] because the largest
    element (8) is found at positions 2 and 4 in the array.

7c. GIGA-Challenge: The "median" value of an array is an element such that
    there are an equal number of elements less than the median as there are
    greater than the median.  For example, median([5,2,8,6,9,10,1])
    is 6, because there are three numbers less than 6 and three numbers 
    greater than 6.  Note that the median is not the same as the average.
    If there are an even number of elements in the array, such as
    [4,2,3,6], then the median should have one more element less
    than it than, so median([4,2,3,6]) should return 3. 
    Write the median function.
    You may also write other functions first that are called from median.

-----

Don't forget: for each function, write at least two different function
calls to test that it works.