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


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


2b. (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-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[j]: 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
# The key is to not reset j back to 0 before the inner loop begins


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


class metrocard:

  fare = 2.75  # current fair, class variable that may change
  bonus = .11  # 11% bonus, but may change
  
  def __init__(self,amt):
      if (amt>=2*metrocard.fare): 
            amt = amt + (amt*metrocard.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*metrocard.fare): 
            amt = amt + (amt*metrocard.bonus)
      self.balance += amt 
  # refill

  def swipe(self):
     if self.balance>=metrocard.fare:
        self.balance -= metrocard.fare;
        #print("have a nice trip")
     else:
        print("insufficient balance")  # better to return instead of print
  #swipe

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

  def __lt__(self,other):  # overrides < operator
     return self.balance < other.balance
#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
othercard = metrocard(20)  # need to create othercard object first (missing before)
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):
	  return (self.cpuclock > otherpc.cpuclock and self.ram > otherpc.ram)
#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.  
x = 0
A = [2,4,6]
def f(B,x):
    x = x+1
    B[1] = x
    B = [7,8,9]
    # explain what's happening in memory at this point (draw a diagram)
#f
f(A,x)
print(x, A[1])


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


#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),end="")    #  (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(a,b):
    if a==0: return b
    else: return f(b%a,a)
# f

print(f(12,8))

# prints 4, which is the gcd (greatest common divisor) of 12 and 8



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. Converting between hexadecimal and decimal integers:

# return hex string rep of non-neg integer n

HD = "0123456789ABCDEF"  # hexadecimal digits

def hex(n):
    hs = ""   # hex string to be returned
    while n>0:
        digit = n%16  # rightmost 4 binary digits = last hex digit
        hs = HD[digit] + hs  # adds hex digit in front of hs
        n = n//16  # shift right 4 bits
    #
    return hs
##
print(hex(26))



# return decimal integer from hex string:

# first construct hash table for hex digits and their values, inverse of HD:
HV = {}  # start with empty table
for i in range(0,len(HD)): HV[HD[i]] = i
## now, HV['A'] will give 10, for example

def hexToInt(hs):  # hs is hex string to be converted
    n = 0  # number to be returned
    power = 0  # start with 16**0
    i = len(hs)-1  # index of last digit
    while i>=0:
        n += HV[hs[i]] * (16**power)
        power += 1
        i -= 1
    #
    return n
# hexToInt

print(hexToInt("2A"))

# alternate solution:
def hexint2(hs):   # hs is a string like "4F2A"
  ax = 0  # accumulator
  i =0
  while i<len(hs):
    val = HV[hs[i]]   # a number between 0 and 15
    ax = ax + val
    if i<len(hs)-1: ax = ax*16  # shifts left 4 bits to make room for next digit
    i = i+1
  return ax
#
  


11.
### recursive program to return sum of all numbers in a nested list:
def nestedsum(A):
    if isinstance(A,int): return A
    if isinstance(A,list):  # can also use  if type(A)==type([])
        ax = 0 # sum accumulator
        for x in A:
            ax += nestedsum(x)
        return ax
    return 0  # default, if not int and not list
#
print(nestedsum([3,[[[[4],3]]],[1,[2]]]))  # prints 13

## alternatively, you can define flatten first.