CSC15 Final Exam Study Guide


Scope: the final exam will be comprehensive, with some emphasis on material
covered in the latter part of the course (since lab 6), however,
basic algorithms (such as finding the index of the largest value) will still
be covered.

Study Advice: focus on the latest topics first: classes and objects,
pointers and 2D arrays, then review the earlier materials.

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 

  Note: definitely study nested while loops

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

How do define and call functions.  

Global versus local variables.

Hashmaps (dictionaries/association lists) and how to use them.

Impact of pointers with respect to arrays, dictionaries and objects, including
the problem of creating and copying 2D arrays
(why [[0]*columns]*rows doesn't work)

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

Recursion:  Understand the potential problems of recursion: 
  1. redundant computations (naive fibonacci function)
  2. stack overflow (factorial)
  3. separate recursive *thinking* from recursive *programming*

Important Algorithms:

  Binary search
  Binary factorization - use of %2, //2 to analyze binary data
  forall and there-exists types of loops, including nested loops
  Binary representation, including hexadecimal numbers and converting
     between different bases.
  Procedures related to sorting
  Procedures pertaining to permutations/scrambling
  Classes and objects: how to define
    purpose of constructor, self parameter, "instance" methods and vars 
    versus class-level methods and vars, how to call methods, the
    fact that objects are mutable/destructible structures.

RSA will not be covered on the exam.  However, I suggest you become
familiar with the fastexp (aka powermod) function, which computes x**n % m
in log-n steps by binary factorization on n.

*** the *efficiency* of your code will count. ***

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

File I/O, Gtk graphics (the only I/O you need to know is print),
for loops (you can use them in your code if appropriate)


Review of some of the most important algorithms (but don't just study
these!)

def binsearch(x,A): # search for x in sorted array A
  min, max = 0,len(A)-1
  answer = False
  while answer==False and min<=max:
    mid = (min+max)//2
    if x<A[mid]: max=mid-1
    elif x>A[mid]: min = mid+1
    else: answer = True
  # while
  return answer
#binsearch

# find binary factors of n: (e.g. 13 = 8 + 4 +1)
def binfactors(n):
  Factors = [] # factors
  factor = 1;  # first factor, 1, then 2, then 4, then 8, etc...
  while n>0:
    if n%2==1: Factors.append(factor)  # add this factor to F
    factor = factor*2 
    n = n//2
  # 
  return Factors
#binfactors 

... others can be found in the sample programs on the homepage.

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

Practice problems.  (Sample solutions to be posted)


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

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 $2.75
but that may change in the future, so be sure to represent it using a
class-variable.  When a metrocard is created, it is given an initial
balance. Each use (swipe) of the card will 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 ($5.50) or more, you are
given a 11% bonus.  These values are the same for each metrocard, but
may change.  

### Your class must support the following code WITHOUT MODIFICATION:

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:
                           # this requires overloading the < operator

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
	# or just   return s.x+s.y > B.x+B.y
    #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),end="")    # (no new line)
        j +=1
    # while j
    k += 1
    print("")  # prints new line
# while k


#v

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. Binary code is often represented using "hexadecimal" notation, which
    are base-16 numbers.  With decimal numbers, each digit has one of
    10 values (0-9), with binary numbers, each digit has one of two values
    (0 or 1), and with hexadecimal numbers, each digit has one of 16 values,
    0-9 plus A, B, C, D, E, F.  A has value 10, B 11, C 12, D 13, E 14 and
    F 15.  Each hexadecimal digit corresponds to exactly 4 binary digits.
    For example, decimal number 26 is represented in hexadecimal
    as 1A, which is 16 + 10.  A number such as 2AF has (decimal) value
    2*16**2 + 10*16**1 + 15*16**0.  In binary, 2AF is 0010 1010 1111.

    Write a function that returns the hexadecimal representation of a
    (non-negative) decimal integer as a string.  For example, hex(26) 
    should return "1A"

10b. Write a function that takes a hex string and returns an integer.
For example, hexToInt("2A") should return 42 (32+10)

    
11. Write a (recursive) program that returns the sum of all integers
found in an arbitrarily nested list/array.  For example,

print(nestedsum([3,[[[[4],3]]],[1,[2]]]))  # should print 13

to test if some value x is a list (array) or integer, you can use

if isinstance(x,list): ...
if isinstance(x,int): ...

or 

if type(x) == type([]): ..
if type(x) == type(1): ...