Grading Scheme:

A+	7,8
A		5,6
A-		4
B+	3

Calendar Tips

printHeading(month,year)
	we want to "center" the first line; so we must do some calculation???
	months = {1: "January", 2:"February",....,12:"December"}
       len(months[month])+5
       20 spaces
       
printDays(dno,ndays)
dno = day number for 1st of the month  0: Sunday, 1: Monday,... 6:Saturday  " "*(3*dno)
ndays = #days in the month
  - single digit day then print an extra space  if i < 10:
  - detect "Saturday"???


Time Class

def next(self):

0-59 for seconds and minutes
1-12 for hour
special cases:
	11.59:59 AM  -> 12.0:0 PM
	11.59:59 PM  -> 12.0:0 AM
	
def seconds_between(self,t):
	if self.before(t):
		???? # need a while-loop
	elif self.equal(t):
		return 0
	else:
	    ????
	    
def before(self,t):
		return not self.equal(t) and not self.after(t)
		
		
	Linked List Sorted
	
	
	
	RECURSION
	
	closed-form definitions of functions
	   f(x) = x**2
	   fact(n) = n*(n-1)*(n-2)...1 = 
	   
	inductive definition of functions
	   fact(n) = 1, if n = 0
	              = n * fact(n-1), otherwise
	              
	  fact(3) = 3*fact(2)  = 3   *   2  *  fact(1) = 3 * 2 * 1 * fact(0) = 3*2*1*1 = 6
	  
	  length(xs) = 0,                             if xs = []
	                   = 1 + length(xs[1:]),    otherwise
	
	
	sum(t) = 0, t is empty
	           = value_at_root(t) + sum(left_child(t)) + sum(right_child(t)), otherwise
	           
	           
	           Proof by Mathematical Induction:
	             (1) Basis case
	             (2) Inductive case  P(n) => P(n+1)
	
			Structural Mathematical Induction
	
	sum([10,20,30,40]) = 10 + sum([20,30,40])
	
	xs[0]   - head of  xs
	xs[1:]  - tail of xs
	
	[100,20,30,40]
	if xs[0] > max_list_2(xs[1:]):
		return xs[0]
	else:
		return max_list_2(xs[1:])
	
	
	
	
	max(xs) = None,                    if xs = []
	              = a       ,                    if xs = [a]
	              = max_list_2(xs[1:]), otherwise
	              
Fibonacci series/numbers
1  2  3  4  5  6   7    8     
1, 1, 2, 3, 5, 8, 13, 21, ...... 
		
		
		
DYNAMIC PROGRAMMING

Quicksort

xs = [3,     1,2,6,3,4,9,5,3]

(1)  find a pivot element (let us pick the first)
   pivot = 3
(2) use pivot element to PARTITION xs without pivot into 2 lists: xs_left and xs_right in such a way that 
     xs_left contains all elements of xs that are less than or equal to the pivot
   
   xs_left = [1,2,3,3]
   xs_right = [6,4,9,5]
   
(3) lsort = quicksort(xs_left)
     rsort = quicksort(xs_right)
     
(4) return lsort + [pivot] + rsort

		
		n
n/2       n/2