CSC15 Final Exam Study Guide


Scope: the final exam will be comprehensive.  Topics to study:

1. Statements and expressions: understand the difference between destructive
versus non-destructive operations.  Non-destructive operations return a 
value, but does not change any existing values.  Destructive means changing
something.  


Boolean expressions and their use in if-else and while loops

while loops and nested while loops.

Basic built-in functions including str, int, chr, ord, append, etc ...

How do define and call functions.  

Global versus local variables

Runtime stack (how local variables are implemented); 

Usage of pointers with respect to arrays and objects. 

Object-oriented programming using classes.  Understand how to define classes,
create instances of classes, etc ...

Tracing Recursion: there may be a question that asks you for the output of a 
simple recursive program (see sample problems below).  But you will only
have to write recursive programs for at most one challenge question.
---

The following advanced topics will be covered only on 1-2 questions that
are designed to be difficult.  The bulk of the exam is formed by topics
listed above.

Recursion
Inheritance
Higher-order functions

Of these, the one that will appear for sure is recursion.
---


The following topics will NOT be on the exam:

File IO (the only io you need to know is print)
GTK, gui, graphics
for loops (you can use them in your code if appropriate)
Hash tables


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

Practice problems.  (Sample solutions to be posted)


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

1b. (challenge) write reverse recursively


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.

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.

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.


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


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.


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

      def addmoney(self,dollars):  # add dollar amount to card, give 1 free
				   # ride for every $10 added.
      
      def swipe(self,dayused): # subtract $2, print error if 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.
# 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.

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



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


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

# 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"
print A.y, B.y


#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


#v

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

    


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