Homework 3.17 - 3.18
Vocabulary
- Problem: A description of something that can or cannot be solved.
- Decision Problem: A problem that has a yes or no answer.
- Organization Problem: A problem with the goal of finding the best solution.
- Instance: A problem with a certain input.
- Efficiency: Amount of effort needed to solve a problem. In coding, the effort is known as computing.
- Polynomial Efficiency (Good): Work takes a proportional amount more time.
- Exponential Efficiency (Bad): Work takes an exponential amount more time.
- Heuristic Approach: When the current solution is inefficive, search for a more efficient optimal solution.
- Decidable Problem: A decision problem with one clear and correct solution.
- Undecidable Problem: A decision problem with no solution or multiple solutions that many not be correct.
Notes
- Efficiency in computer science is how fast a computer can run a process and/or program.
- Unnecessary blocks of code will decrease the efficiency of the code. With less functions, the efficiency is higher and the process and/or program takes up less time to run.
- The difference in exponential efficiency and polynomial efficiency is huge. Polynomial efficiency is way more efficient than exponential efficiency.
- Heuristic Approach is when you try to find the best possible solution and in this case, the most efficient.
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
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')
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):
#--------------------
for i in range(len(array)):
if value == array[i]:
return True
elif value > array[i]:
return False
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
- Decidable problems: problems with an answer of yes or no.
- Decidable problem will always have a clear and correct answer.
- Undecidable problems will not always have a correct or clear answer and will somethings have none or multiple that may be incorrect.
- contradicting coding will lead to it getting stuck
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]))