Homework 3.17 - 3.18
Vocabulary
- Problem: general description of a task which can / cant be solved using an algorithm
- Decision Problem: yes / no answer
- Organization Problem: problem with multiple aspects
- Instance: specific input
- Efficiency: making a large problem simpler using some method
- Polynomial Efficiency (Good): more work takes proportional amount of time
- Exponential Efficiency (Bad): more work takes exponential amount of time
- Heuristic Approach: look for am optimal solution
- Decidable Problem: problem with a clear decision as the right answer
- Undecidable Problem: problem with no solution
import time
numlist = [1,3,5,7,9,11,13,15,17,19]
valuelist = [0,3,6,9,12,15,18,21]
def isvalue(value,array):
#--------------------
for i in value:
if i in array:
return True
else:
return False
#--------------------
starttime = time.time()
for i in range(100000):
for i in range(len(valuelist)):
x = isvalue(valuelist[i],numlist)
endtime = time.time()
print(endtime-starttime,'seconds')
Homework!
Make an algorithm that finds the fastest route that hits every location once starting and ending at Del Norte. Make sure to show your thinking. If you are strugling, try using a huristic approach. Remember, what matters more than having perfectly functioning code is that you tried your hardest.
dataset = {
'DelNorte':{
'Westview':15,
'MtCarmel':20,
'Poway':35,
'RanchoBernrdo':50
},
'Westview':{
'Del Norte':15,
'MtCarmel':35,
'Poway':25,
'RanchoBernrdo': 45
},
'MtCarmel':{
'Westview':35,
'Del Norte':20,
'Poway':40,
'RanchoBernrdo':30
},
'Poway':{
'Westview':25,
'MtCarmel':40,
'Del Norte':35,
'RanchoBernrdo':15
},
'RanchoBernardo':{
'Westview':45,
'MtCarmel':30,
'Poway':15,
'Del Norte':50
}
}
def fastestroute(start,data):
drivetime = 0
order = []
order.append(start)
while len(order) < 5:
return(drivetime,order)
distance = 0
for x in data
for i in data [x]
order.append (start)
start = 'DelNorte'
fastestroute(dataset)
# 'dataset' is the name of the nested key value pair