CSC15 Final Exam Study Guide - Sample Solutions


1. Write a function to reverse a string (non-destructively).  For example,
reverse("abcd") should return "dcba"

def reverse(S):
    R = ""    # string to be constructed
    i = 0     
    while i<len(S):
	  R = S[i]+R   # S[i] is always added to the front of R, thus reversed
	  i +=1
    return R
#reverse


1b. (challenge) write reverse recursively

def rev(S):
    if S=="": return S  # base case
    else: return rev(S[1:])+S[0]  # S[1:] is string without first char.
#rev

def irev(S,R):  # initial parameter to R should be ""
    if S=="": return R
    else return irev(S[1:],S[0]+R)


2. Write a function 'sublist' to determine if every element of list A
is also contained in list B.  for example, sublist([2,4,5],[1,2,4,6,5])
should return True (and False otherwise).  Duplicates don't count.

def sublist(A,B):
    i = 0
    answer = True
    while i<len(A) and answer:
	  if not (A[i] in B): answer = False
	  i +=1
    return answer
#sublist


2c. (mild challenge). Write a version of sublist that also respects the
order of appearence of the elements, so sublist([4,2,1],[3,4,1,5,2]) should
return False, because 4,2,1 do not appear in the same order in the second
list.  (the best solution was due to a former student).

def sublist3(A,B):   # this is a forall-there exists nested loop
    i, j = 0
    answer = True
    while i<len(A) and answer:
	  an2 = False
	  while j<len(B) and not an2:
		if A[i]==B[i]: an2 = True
		j += 1  # trick here is that j is NOT reset.
          # while j
          if not an2: answer = False
	  i += 1
    #while i
    return answer
#sublist3



3. Write a function to determine if a list is sorted. For example,
sorted([2,5,8,9]) should return True (return False otherwise).

def sorted(A):
    answer = True
    i = 0
    while i<len(A)-1 and answer:
	  if A[i] > A[i+1]: answer = False
	  i +=1
    return answer
#sorted.


4. Write a function 'substringcount' that counts the number of times
the substring A occurs in the string B.  For example,
substringcount("aba","aababa") should return 2, since two subtrings,
both equal to "aba", are found in the second list.  Note that the
substrings can overlap.


Note: there is the following built-in operation that finds substrings:

s.find(sub): Returns the lowest index in s where substring sub is
found. Returns -1 if sub is not found.

But you'll have to decide to use it or write your function from scratch.

# first version:
def subcount(A,B):
    j = 0  # indexes B
    count = 0  # counts substrings
    while j<len(B):
	  BR = B[j:]   # only look at B starting from j
	  if BR.find(A) != -1: count += 1
	  j += 1
    #while
    return count
#subcount


def substringcount(A,B):
    count = 0
    j = 0  # indexes B
    while j < len(B):
        i = 0  # indexes A
        issubstring = True
	while i<len(A) and j+i<len(B) and issubstring:
	      if A[i] != B[j+i]: issubstring = False
	      i += 1
	# inner while
	if i<len(A): issubstring=False  # reached end of B before end of A
	if issubstring: count += 1
	j += 1  # increment index in B to start looking from.
    # outer while
    return count
# substringcount
	  


5.  You want to write a class to represent a MTA metrocard...

fare = 3.00
bonus = .11  # 11% bonus, but may change
class metrocard:
  def __init__(self,amt):
      if (amt>=2*fare): 
            amt = amt + (amt*bonus)
      self.balance = amt  # set initial balance
      # alternatively:
      # self.balance = 0
      # self.refill(amt) # see code below
  # init
  
  def refill(self,amt):
      if (amt>=2*fare): 
            amt = amt + (amt*bonus)
      self.balance += amt 
  # refill

  def swipe(self):
     if self.balance>=fare:
        self.balance -= fare;
        print "have a nice trip"
     else:
        print "insufficient balance"
  #swipe

  def ridesleft(self):
    return int(self.balance/fare)
  #
  
  def transfer(self,other):
     other.balance += self.balance
     self.balance = 0
  #

  def __cmp__(self,other):
     a,b = self.balance,other.balance
     if a==b: return 0
     if a<b : return -1
     if a>b : return 1
     # note: if a and b were both integers, it would suffice to say
     # return a-b
#metrocard

### Your class must support the following code:

mycard = metrocard(10) # new metro card with $11.10 balance created
mycard.refill(20)      # add $22.20 to balance
mycard.swipe()         # subtract fare from balance
		       # print message if insufficient funds
print mycard.ridesleft() # calculate number of rides this card still has left
                         # as an integer
mycard.transfer(othercard) # mycard and othercard are both metrocard objects.
                           # the balance of mycard should be transferred
                           # to othercard.
print mycard < othercard   # prints true since othercard has higher balance


6. Write a class to represent a PC: Each PC has the following attributes:

  1. cpu model , e.g (intel core2 dou)
  2. cpu clock speed in ghz (e.g 2.4)
  3. ram: amount of memory in megabytes, 1gig = 1024 megs
  4. drivespace: amount of hard disk space in gigabytes.
  5. videocard: e.g "nvidia 8600xt"

  You may also change these to be more specific, like "numberofcores" and
  speparate "videomake" and "videomodel".

Write a class to represent a PC with the the above attributes.

Write at least the following methods:

upgrade : increase ram and hard drive space
overclock : increase cpu clock speed and start a fire
changevideo : replace old video card with a new one
betterthan : compares "self" pc with another pc and determines which
  one is better (faster cpu, more memory, maybe better video card, etc ...)
  Set your own criteria.

Write code that creates PC objects and call the methods you've defined.


class PC:
      def __init__(self,cpu,speed,ram,disk,gpu):
	  self.cpu = cpu
	  self.cpuclock = speed
	  self.ram = ram
	  self.diskspace = disk
	  self.video = gpu
      # init

      def upgrade(self,r,h):
	  self.ram += r
	  self.diskspace += h

      def overclock(self,factor):
	  self.cpuclock += self.cpuclock * factor

      def changevideo(self,newgpu):
	  self.video = newgpu

      def betterthan(self,otherpc):
	  if self.cpuclock > otherpc.cpuclock and self.ram > otherpc.ram:
	     return True
	  else: return False
#PC 

mypc = PC("core2 quad",2.4,4096,1000,"nvidia 8600GT")
yourpc = PC("pentium 4",1.0, 256, 20, "ati radeon")
yourpc.upgrade(128,20)  % add 128 megs and 20 gigs
mypc.overclock(0.25)  # overclock by 25%
mypc.changevideo("nvidia 8800GTx")
if mypc.betterthan(yourpc): print "my pc is better than your pc"


----
7. # Determine the output of the following program fragments and explain why.

# i
A = [2,4,6]
def f(B):
    B = [1,3,5]
# f
f(A)
print A   

prints [2,4,6].  Nothing was changed, B is a local variable (which is a
pointer).



# ii.  Draw a memory-allocation diagram at the point indicated.
x = 0
A = [2,4,6]
def f(B,x):
    x = x+1
    B[1] = x
    B = [7,8,9]
    # draw stack-heap allocation diagram for this point
#f
f(A,x)
print x, A[1]


prints 0, 1   # change to B[1] was made before B was reassigned.


# Memory allocation diagrams must be clear as to what delineates stack frames,
# the content of each stack frame.  And for pointers, where they point to.


#iii

class AA:
    def __init__(t,x):
        t.x = x
        t.y = 0
    # init

    def f(self,a):
        self.y = a + self.x
    # f

    def g(s,B):
        if s.x+s.y > B.x+B.y: return True
        else: return False
    #g
#AA

A = AA(3)
B = AA(4)
A.f(3)
if A.g(B): print "yes"    # prints yes
print A.y, B.y            # prints 6,0

    

#iv
k = 0
while k < 4:
    j = ord("A")+k       # ord("A") is 65
    while j <= ord("D"): # ord("D") is 68
        print chr(j),    # note , (no new line)
        j +=1
    # while j
    k += 1
    print ""  # prints new line
# while k

output:
A B C D 
B C D 
C D 
D 


#v

def f(x):
    if x<2: return x
    else: return f(x-1) + x
#f
print f(6) 

prints 21  (1+2+3+4+5+6)
    

8.  Determine the output of the following code:

def f(A,x):
  A[0] += 1
  x += 1
#

a = [2,3,5,7]
x = 2
f(a,x)
print a[0],x

## answer: prints  3,2
A[0] has been changed because the A and a points to the same array, but
x inside f is a local only change.


9.  Write a function to determine if two permutations are inverses of
eachother.  Each permutation is an array of size n that contains the
numbers 0 to n-1.  Two permuatation arrays P and Q are inverses if
P[Q[x]] = x. For example, inverses([2,0,1],[1,2,0]) should return True.
You may assume that P and Q are both valid permutations

def inverses(P,Q):
  if len(P) != len(Q): return False
  answer = True
  i = 0
  while i<len(P) and answer:
    if P[Q[i]] != i: answer = False
    i += 1
  #while
  return answer
#inverses


10. Determine what would happen when you run the following recursive program,
AND EXPLAIN WHY.

def f(n):
  if n<2: return 1
  else: return f(n-2) + 1

f(10000000000)

a.) the program loops forever
b.) the program returns only after thousands or more years
c.) the program crashes after a short while
d.) the program returns quickly

answer:
c. stack overflow after 1000 recursive calls; 10000000000/2 are needed

10b. what does f(6) return?

4

### In addition to these problems, don't forget to review the midterm exam.