CSC15 Final Exam Study Guide


Practice problems.  (Sample solutions to be posted)


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


2b. (mild challenge). Rewrite the above function to take into account
duplicates.  That is, if x occurs n times in A then it must also occur
at least n times in B.  So sublist([2,2],[1,2,3]) should return False because
there's only one 2 in the second list.  hint: may want to write an 'occurs'
function first.

def occurs(x,A): counts number of times x occurs in A
    answer = 0
    i = 0  
    while i<len(A):
	  if x == A[i]: answer +=1
	  i +=1
    return answer
# occurs

def sublist2(A,B):
    i = 0
    answer = True
    while i<len(A) and answer:
	  if occurs(A[i],A)>occurs(A[i],B): answer = False
	  i += 1
    return answer


2c. (mega-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 Paras Patel).

def sublist3(A,B):
    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
          # 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.  This exercise requires code from your 'date' class of lab 9.  Import it.

You want to write a class to represent a MTA metrocard.  Each metrocard
has a balance and an expiration date.  Each ride costs $2 currently but
that may change in the future, so be sure to represent it using a variable.

Finish writing the following class:

class metrocard:
      def __init__(self,de):
	  self.cost = 2.0    # cost of one ride
	  self.expire = de   # expiration date
	  self.balance = 0   # card balance
      # init
      # note that all metrocards have an initial balance of 0

      ### finish defining the following methods:


      def ridesleft(self):  # return number of rides you can take with card.
	  return self.balance / self.cost

      def addmoney(self,dollars):  # add dollar amount to card, give 1 free
	  self.balance += dollars  # ride for every $10 added.
	  self.balance += (dollars/10) * 2.0
      
      def swipe(self,dayused): # subtract $2, print error if card expired
	  if dayused.before(self.expire): self.balance -= self.cost
	  else: print "card expired"

      def join(self,othercard): # join other card's balance with self.balance.
				# reset othercard's balance to zero.
				# print warning if othercard's expiration
				# date is later than self's expiration date.
	  self.balance += othercard.balance
	  othercard.balance = 0
	  if self.expire.before(othercard.expire): 
	     print "other card has later expiration date"
       # join
# class metrocard

### Your class must support the following code:

mycard = metrocard(date(12,10,2008)) # card that expires on 12/10/08
mycard.addmoney(20)
mycard.swipe()
print mycard.ridesleft()

## Now write code that joins one card with anther card.
mynewcard = metrocard(date(12,11,2009))
mynewcard.join(mycard)


# Be careful: only the functions swipe and join can print.


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 3",1.0, 256, 20, "ati mach64")
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)
    


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