content: import sys
  import matplotlib
  matplotlib.use('Agg')
  import matplotlib.pyplot as plt
  import random
  import datetime
  
  # Import the three change making algorithms
  sys.path.insert(0, "../divide-conquer/")
  sys.path.insert(0, "../dynamic-programming")
  sys.path.insert(0, "../greedy")
  
  from changeslow import changeslow
  from changegreedy import changegreedy
  from changedp import changedp
  
  ### QUESTION 7 ###
  def Q7(slow, minChange, maxChange):
  
  	lenV = []
  	runtimeGreedy = []
  	runtimeDP = []
  	runtimeSlow = []
  
  	numExp = 10
  	maxRange = 1000
  	if (slow):
  		maxRange = 10 # some much smaller number
  
  	for i in range(1, maxRange): # V can be of length 1 to (maxRange - 1)
  		print "\n------ running V length=" + str(i) + "------"
  		lenV.append(i)
  		#print "lenV:", lenV
  		runtimeGreedy.append(0)
  		runtimeDP.append(0)
  		runtimeSlow.append(0)
  
  		for j in range(numExp): # run numExp experiments for this length of V
  			print "\n  ---- running experiment=" + str(j + 1) + " ----"
  			coinArray = []
  
  			for k in range(i): # generate V of size i [1, rand, ..., rand, max=1 + 5*(maxRange-2)]
  				if (k == 0):
  					coinArray.append(1)
  				else:
  					randFrom = coinArray[len(coinArray) - 1] + 1
  					randTo = coinArray[len(coinArray) - 1] + 5
  					coinArray.append(random.randint(randFrom, randTo))
  			change = random.randint(minChange, maxChange)
  			#print "  coinArray:", coinArray				
  			#print "  change:", change			
  
  			print "  running greedy..."
  			start = datetime.datetime.now()
  			_, _ = changegreedy(coinArray, change)
  			end = datetime.datetime.now()
  			delta = end - start
  			delta = int(delta.total_seconds() * 1000000)
  			print "    " + str(delta)
  			runtimeGreedy[i - 1] += delta
  
  			print "  running DP..."
  			start = datetime.datetime.now()
  			_, _ = changedp(coinArray, change)
  			end = datetime.datetime.now()
  			delta = end - start
  			delta = int(delta.total_seconds() * 1000000)
  			print "    " + str(delta)
  			runtimeDP[i - 1] += delta
  			
  			if (slow):
  				print "  running slow..."
  				start = datetime.datetime.now()
  				_, _ = changeslow(coinArray, change)
  				end = datetime.datetime.now()
  				delta = end - start
  				delta = int(delta.total_seconds() * 1000000)
  				print "    " + str(delta)
  				runtimeSlow[i - 1] += delta
  
  		runtimeGreedy[i - 1] /= numExp 
  		runtimeDP[i - 1] /= numExp
  		if (slow):
  			runtimeSlow[i - 1] /= numExp
  
  	plt.figure(21)
  	plt.plot(lenV, runtimeGreedy, 'b-', linewidth=2.0, label='Greedy')
  	plt.plot(lenV, runtimeDP, 'r--', linewidth=2.0, label='DP')
  	if (slow):
  		plt.plot(lenV, runtimeSlow, 'g-.', linewidth=2.0, label='Slow')
  	plt.legend(loc='upper left')
  	plt.title('Runtime vs len(V[]) for randomized V[] and A')
  	plt.ylabel('Avg. Runtime (10^-6 sec)')
  	plt.xlabel('len(V[])')
  	plt.grid(True)
  	if (slow):
  		plt.savefig('img/Q7slow_runtime.png', bbox_inches='tight')
  	else:
  		plt.savefig('img/Q7_runtime.png', bbox_inches='tight')
  		
  
  def main():
  	Q7(False, 100, 100)
  	#Q7(True)
  
  
  if __name__ == "__main__":
  	main()
  