# Sample Solutions to the problems on the exam study guide

#1. For each line below, determine if it's an expression or statement.  If
#   it's an expression, determine its type.  Assume the following function
#   definition:
       
#      def f(n):
#         return n*n

#a.   S+"C"   # assume S is a string variable

    # This is an expression, S is not changed unless it's S = S+"C"

#b.   A.append("C")   # assume A is an array

    # This is a statement. A is changed (append is "destructive")
  
#c.   f(f(2))  # additional question: what will this return? 

    # It returns 16, the inner f(2) is called first, which returns 4

#2. Determine the output of the following program fragment:

x = 1
y = 2

def f(x):
  x = x+y
  return x
# end f

def g(x):
  y = x+1
  x = y
# end g


print f(x)     # prints 3, but global x is still 1
x = f(x)       # the global x is assigned the return value 3
print x        # prints 3
g(x)           # inside g, x and y are both local, nothing is returned
print x, y     # prints 3, 2 - no changes are made by g to these vars




#3. Determine the output of the following program fragment:

x = 10
while x>0:
  y = 1
  while y<=x:
     print y,  # note , at the end
     y = y+1
  # inner while
  print ""
  x = x - 2    # read this line carefully
#outer while
print x,y  # don't forget this line!

# prints:
#1 2 3 4 5 6 7 8 9 10
#1 2 3 4 5 6 7 8
#1 2 3 4 5 6
#1 2 3 4
#1 2

# last print statement prints 0 3: the inner loop stopped when x was 2,
# it's nolonger the case that y<=x, so y is three after the inner loop stopped


#4. Write a function 'interleave' that constructs the interleave of two
#   arrays.  For example, interleave([1,3,7,9],[4,8,16,32]) should 
#   return the array [1,4,3,8,7,16,9,32].  If the two array parameters
#   are not of the same length, you should just return the empty array [].

def interleave(A,B):
    n = len(A)
    if n!=len(B): return []
    C = [] # array to be built
    i = 0
    while i<n:
        C.append(A[i])
        C.append(B[i])
        i +=1
    return C
# interleave


#5. Two arrays are disjoint if they share no common element.  Write
#a function to test for this property.  For example, disjoint([1,4,2],[5,0,3,8])
#should return True because they share no common element.  The empty
#array is considered disjoint from all other arrays.

def disjoint(A,B):
    i = 0 # loop counter
    answer = True   # forall-predicate: no reason to believe why not just yet
    while i<len(A) and answer:
        if (A[i] in B): answer = False
        i +=1
    return answer
#disjoint

# note you can also use a for loop: for x in A: if (x in B): answer=False
# However, you would not be able to stop the loop as soon as answer becomes
# false, so a while loop is better.  For loops are just a convenience that's
# appropriate only in special cases.
    

#6. A list is sorted if all elements are in order.  For example, [4,7,2,8]
#   is not sorted because 2 should come before the 4.  Write a function 
#   sorted(A) that returns True/False depending on whether A is sorted.
#   Hint: you need to write a loop that checks that A[i]<=A[i+1] for each 
#   index i.  Unlike the "usual" case however, your loop will have to stop
#   one index sooner: both i and i+1 must be <= len(A).  Additional hint:
#   think about whether this is a "for all" or "there exists" type of property.

def sorted(A):
    answer = True   # why not
    i = 0
    while i<len(A)-1 and answer:   # stop one position sooner than usual
        if A[i]>A[i+1]: answer = False
        i =i+1
    return answer


#7. (a little harder)
#   Write a function 'duplicate' to determine if an array contains
#   a duplicate entry (an element that appears more than once).  For
#   example, duplicate([4,5,2,4,1]) should return True and
#   duplicate(["abc","def","ghi"]) should return False.
#
#   hint: you may want to first define a function that counts the number
#   of times an element occurs an array.

def count(x,A): # counts number of times x occurs in A
    counter = 0  # keep the count
    i = 0        # loop counter
    while i<len(A):
        if A[i]==x: counter = counter+1
        i =i+1
    # here, you can also use:   for y in A: if x==y: counter +=1
    return counter
# count

def duplicate(A):
    answer = False  # this is a there-exists type of problem
    i = 0
    while i<len(A) and answer==False:
        if count(A[i],A)>1: answer = True # found a duplicate
        i +=1
    return answer
#duplicate


#8 (similar to problem 6).  Write a function 'pivot' that returns the
#index of the first element in an array that's not in order (not
#sorted).  If all elements are in order, then return -1.  For example,
#pivot([3,6,7,2,9,4]) should return 3, which is the index of the
#element 2. This is the element out of order because it's larger than
#the element (7) preceeding it.  pivot([2,4,6,8,9]) should return -1,
#since all elements are in order.

def pivot(A):
    answer = -1   # default no pivot - this is a there exists type of problem
    i = 1  # start at second index
    while i<len(A) and answer == -1:
        if A[i]<A[i-1]: answer = i  # pivot found
        i +=1
    return answer
#pivot
# note: if the list contains less than 2 elements, while loop won't run.


#9. Write a function that takes a string as an argument and return the
#same string but with all upper case characters into lower case characters.
#Upper case letters have ascii values in the range ord('A') to ord('Z')
#and lower case letters have ascii values from ord('a') to ord('z').
# ord('A') has value 65 and ord('a') has value 97.
# Hint: rebuild the string one character at a time.

def lowercase(S):  # returns string S with all uppercase changed to lower
  ax = ""  # accumulator this time will be a string, initially empty
  i = 0
  while i<len(S):
    code = ord(S[i])  # ascii value of ith character in string
    if (code>=ord('A') and code<=ord('Z')): code = code+32 # 97-65==32
    ax = ax + chr(code) # add character corresponding to code to accumulator
    i += 1
  #while
  return ax
#lowercase

#9b. Write a function that calls the function above, and which determines if 
#two strings are equal regardless of upper/lower case. For example, calling
#yourfunction("aBc","ABc") should return True.

def myfunction(A,B):  # tests if Strings A, B are case-insensitively equal
  return lowercase(A) == lowercase(B)


#10. Explain why binary search requires an array to be sorted.  What would 
#happen if binary search is used on an array that's not sorted.

#Binary search assumes that every number larger than the middle number
# in the array is to the right (at index greater than) the middle number,
# and numbers less than the middle number are to the left.  Thus if an
# array is not sorted, it may not find the number.  The best way to answer
# this question is with an example:

A = [1,4,6,2,8]

#If I'm searching for 2 in A using binary search, I will never find it
# because 2 is not to the left of 6.



#11. Write the following base-10 integers in 8-bit two's complement form:

#a. 34    : 32 + 2: 00100010
#b. -34   : -1 -33: 11011110

#12. Write a function that takes a base-10 positive integer and output it
#    in binary form.


#I will return a string in binary form:

def binform(n):
  s = ""
  while n>0:
     bit = n%2
     s = str(bit)+s
     n = n/2  # shift over next bit
  #
  return s
#


#13. Write a function that takes a binary string such as "00110100" as an
#    argument and return the integer that it represents.  For example,
#    value("00110100") should return 52 and value("1111") should return -1.
#    The bits can vary.

# There are other ways to do it, but here's a nifty one.  I try to generalize
# the code so that if the number is positive, it will add powers of 2 (2**i)
# starting from zero, and if it's negative, it will try to subtract powers
# of 2 starting from -1.

def bintoint(s):
  n = 0;   # default accumulator for non-negatives
  factor = 1  # default + for positive
  bit = '1'   # default char to look for if positive
  if s[0] == '1':  # negative
     n = -1;   # start with 11111... for negatives
     factor = -1  # substract instead of add if negative
     bit = '0'    # look for '0' instead of '1' if negative
  # if negative
  i = 0
  while i<len(s)-1:  # stop before first bit
     if s[len(s)-1-i]==bit:   # start at right end
        n = n + factor*(2**i) # will + or - depending on factor
     i += 1
  #while
  return n
# you can look in sample programs for another solution.