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
- There are levels to polynomial efficiency
- more cycles = longer time to run
- exponential is much less efficient than polynomial because the amount of necessary cycles increases by a lot more each time
- heuristic Approach sacrifices optimal solutions to improve efficiency and ease of programming
- we need to try and be as time-saving as possible in order to avoid annoying processes
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
else: # here, i simply used an else statement
return exists
return exists
#--------------------
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')
I used binary search in this method
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):
#--------------------
low = 0 #here, I used binary search
high = len(array)-1
while low <= high:
mid = (low+high)//2
if mid == value:
return True
elif 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')
Notes
- in a divisible by 3 example. the answer will always return a correct answer, either true or false, which is a decidable problem
- sometimes, problems can't be solved by a computer
- if there are contradictory statements within the code, there will be an error in the code
- Whenever a computer gets a paradoxical problem, it doesn't know when to stop trying to solve it. This is the reason why computers time out when a site doesnt load.
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):
start = 'DelNorte'
dt = 0
ord = [start]
tp = ""
for i in range(len(data) - 1):
temptime = 1000000000000000000000000000
for loc, time in data[ord[(len(ord) - 1)]].items():
if time < min:
min = time
dt += temptime
ord.append(tp)
ord.append(start)
return (dt, ord)
result = fastestroute(start, dataset)
for i, location in enumerate(result):
print("Location" , str(i + 1) + ")", location)
i += 1
print("The shortest amount of minutes it will take to complete the route is", result[0], "minutes")