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 output
- Efficiency: amount of computing needed to solve a problem
- Polynomial Efficiency (Good): more work takes a proportial 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 is more efficient
- Decidable Problem: a decision problem that has a clear solution that will always make a correct output
- Undecidable Problem: a problem with no solution that is not guaranteed to produe the correct output
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):
#--------------------
timeinc = len(array) - 1
timedec = 0
while timeinc >= timedec:
mid = (timeinc + timedec) // 2
if array[mid] == value:
return True
elif array[mid] > value:
timeinc = mid - 1
else:
timedec = 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')
Notes
- more cycles = longer time to run
- computer must guess when to stop loading something which is why things might time out
- if the first step says error and the second step says no error, proving the first step was wrong- paradox
- show that there is a limit to the power of computers- some prolems are impossible to solve, but can be solved by alternative methods
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':{
'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):
drivetime = 0
order = [start]
for i in range(len(data)):
if drivetime <= 25:
order.append(start)
i = 0
end = (start, dataset)
while i < len(end[0]):
print("the best route is" + start)
start = 'DelNorte'