Homework 3.17 - 3.18
Vocabulary
- 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
Notes
- several different examples of code can yield the same result, it all depends on efficiency
- less code but same result = more efficient
- When there are many variables and a situation is quite complex, it is often better to use a heuristic approach
- optimal solution is sacrificed to find a more efficient one
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):
#--------------------
exists = False
while exists == False:
for i in range(len(array)):
if value == array[i]:
exists = True
if exists == False:
return exists # removed the second return exists, it becomes much more efficient and takes much less time
#--------------------
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')
Notes
- Sometimes, a computer's own logic proves to be its downfall
- If you fed a program (calculates whether or not a different program would error with one input, and then reversed the output) into itself, a paradox would occur
- first step said error
- second says no error
- therefore first is wrong?
- paradox!
- This happens a lot, which is why it is important for computers to know when to stop loading or to time out
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 struggling, try using a heuristic 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':{
'Del Norte':15,
'MtCarmel':35,
'Poway':25,
'RanchoBernardo': 45
},
'MtCarmel':{
'Westview':35,
'Del Norte':20,
'Poway':40,
'RanchoBernardo':30
},
'Poway':{
'Westview':25,
'MtCarmel':40,
'Del Norte':35,
'RanchoBernardo':15
},
'RanchoBernardo':{
'Westview':45,
'MtCarmel':30,
'Poway':15,
'Del Norte':50
}
}
def fastestroute(start,data):
drivetime = 0
order = []
highschool = ""
for x in range(len(data)): # creating a large minimum so that every other route is faster
min = 10000
for place, drivetime in data[order[(len(order))]]: # determining the drivetime
if drivetime < min: # if the place's drivetime is less than the min, the new min becomes the drivetime so the fastest route is created
highschool = place # school and place are the same if the drivetime is less than min
min = drivetime # drivetime becomes the min
drivetime += min
order.append(highschool)
order.append(start)
return(drivetime,order)
start = 'DelNorte'
route = fastestroute(start,data) # designating the fastest route
for x, place in route[0]:
print(str(x + 1) + place)
print("time is ", route[0])
# 'dataset' is the name of the nested key value pair