Homework 3.17 - 3.18
Vocabulary
- Problem: general description of a task that can or cannot be solved algorithmically
- Decision Problem: problem with yes or no example
- Organization Problem:problem with a goal of finding the best answer
- Instance: problem with a specific input
- Efficiency: amount of computing needed to solve a problem
- Polynomial Efficiency (Good): Work is proportional to time
- Exponential Efficiency (Bad): Work is not proportial to time (2:1)
- Heuristic Approach: When optimal solutions are inefficient, look for possibly best solution
- Decidable Problem: Problem with a specific input that will give a certain output
- Undecidable Problem: Problem that cannot be solved and can't give an output
Notes
- an instance is a problem with a specific input
- Computing is the total amount of time required to solve an entire problem
- Polynomial Efficiency- Everytime you go through the list it would get longer, the time to code ratio is 1:1
- Decidable problem: Problem with a specific input that will give a certain output
- Undecidable problem: Problem that cannot be solved and can't give an output
- The goal of all code is to be the most efficient and solve a problem in least amount of time needed
- More cycles of a code means it will take a longer time to run it all
- Hueristic approach sacrifices optimal solution in order to achieve efficiency
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
#--------------------
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,
'RanchoBernardo':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 = []
#CODE,CODE,CODE
drivetime = dataset[RanchoBernardo[Westview]]
return(drivetime,order)
start = 'DelNorte'
# 'dataset' is the name of the nested key value pair