Homework 3.17 - 3.18
Problem: A general description of a task that can or cannot be solved algorithmically Decision Problem: A problem with a yes or no answer Organization Problem: A problem with a goal of finding the best answer Instance: A problem with a specific input Efficiency: Amount of computing needed to solve a problem Polynomial Efficiency (Good): More work takes a proportional amount of time (1 job is +2 time) Exponential Efficiency (Bad): More work takes an exponential amount more time (1 job is 2x time) Heuristic Approach: When optimal solutions are inefficient, look for a possibly optimal solution that is more efficient Decidable Problem: A decision problem that has a clear solution that will always make a correct output Undecidable Problem: A decision problem with no solution that is not gaurenteed to produce the correct output
import time
def toint(x):
x = int(x)
return(x)
def tostr(x):
x = str(x)
return(x)
def add(x,y):
x = toint(x)
y = toint(y)
z = x + y
z = tostr(z)
return(z)
starttime = time.time()
for i in range(1000000):
x = "1"
y = "2"
answer = add(x,y)
print(answer)
endtime = time.time()
print(endtime-starttime,'seconds')
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):
#----------
high = (len(array) - 1)
low = 0
while high >= low:
mid = (high + low) // 2
if array[mid] == value:
return True
elif array[mid] > value:
high = mid - 1
else:
low = mid + 1
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,
'RanchoBernardo':50
},
'Westview':{
'DelNorte':15,
'MtCarmel':35,
'Poway':25,
'RanchoBernardo': 45
},
'MtCarmel':{
'Westview':35,
'DelNorte':20,
'Poway':40,
'RanchoBernardo':30
},
'Poway':{
'Westview':25,
'MtCarmel':40,
'DelNorte':35,
'RanchoBernardo':15
},
'RanchoBernardo':{
'Westview':45,
'MtCarmel':30,
'Poway':15,
'DelNorte':50
}
}
def fastestroute(start, data):
drivetime = 0
order = [start]
newplace = ""
for i in range(len(data) - 1):
minimum_time = 1000
for place, time in data[order[(len(order) - 1)]].items():
if time < minimum_time and place not in order:
newplace = place
minimum_time = time
drivetime += minimum_time
order.append(newplace)
order.append(start)
drivetime += data[newplace][start]
return(drivetime, order)
start = 'DelNorte'
# 'dataset' is the name of the nested key value pair
results = fastestroute(start, dataset)
print("Drivetime: " + str(results[0]) + " minutes")
print("Order: " + str(results[1]))
I attempted the homework couldn't find the reason why my code wouldn't work.