CSC15 Final Exam Study Guide


Scope: the final exam will be comprehensive, with emphasis on material
covered after the midterm.

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.  Usually, destructive operations are statments (no return value).
Non-destructive (or constructive) operations always return a value.

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

while loops and nested while loops, loops and arrays 

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

How do define and call functions.  

Global versus local variables.

Hashtables and how to use them.

Impact of pointers with respect to arrays and objects. 

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

oop features including operator overloading - know how to define __cmp__

Recursion: 
   Some basic concepts covered.
   Maybe a challenge problem will ask you to devise a recursive program.
   Understand the importance of the depth of recursion (what could make
   a recursive program crash).

Important Algorithms:

  Binary search**
  Binary factorization
  Procedures related to sorting (such as inserting into sorted array)
  Procedures pertaining to permutations/scrambling
  forall and there-exists types of loops.

Unlike on the midterm, the *efficiency* of your code will count.

---
*** The following topics will NOT be on the exam: ***

File IO, gtk graphics (the only io you need to know is print)
for loops (you can use them in your code if appropriate)
Advanced recursive algorithms.
Binary number systems, two's complement arithmetic, will NOT be covered
  -- but binary factorization may be covered.

***HOWEVER, there will be 1-2 challenge problems where some advanced topics
are inherent.


***Labs to pay special attention to: permutation scrambling lab, oop lab.
-------------------------

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. Write reverse recursively (this would be a challenge).  Hint:
to reverse "abcdef", first reverse "bcdef" to "fedcb", then add "a" to the end.
Given a string s, s[i:j] is the substring from s[i] to s[j-1].

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). 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.  You want to write a class to represent a MTA metrocard.  Each
metrocard has a balance and an expiration date.  Single ride fare is $3.00
but that may change in the future, so be sure to represent it using a
variable.  When a metrocard is created, it is given an initial
balance. Each use (swipe) of the card with subtract an amount from the
balance based on the current fare value, which is the SAME FOR ALL
METROCARDS.  Each time you add a value of 2*fare ($6) or more, you are
given a 11% bonus.  These values are the same for each metrocard, but
may change.  Use global variables to represent them.

### 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 mycard.ridesleft() # calculate number of rides this card still has left
                         # as an integer
## Now write code that joins one card with anther card.
mycard.transfer(othercard) # mycard and othercard are both metrocard objects.
                           # the balance of mycard should be transferred
                           # to othercard.
print mycard < othercard   # print 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 core i7)
  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.  
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
#f
f(A,x)
print x, A[1]

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


# vi

def f(a,b):
    if a==0: return b
    else: return f(b%a,a)
# f

print f(12,8)

# What does this print?
# What mathematical operation does this function implement?

------------
More problems.

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



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.


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

10b. what does f(6) return?


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