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
- How quickly and efficiently an algorithm solves a problem is key in determining it's value
- Time complexity: amount of time an algorithm uses to complete a given task
- Space complexity: amount of space required by the algo to complete a given task
- better time + space complexity --> better algo
- the faster a problem can be solved, the better
- important to try to make an algorithm as efficient as possible
import time
def betteradd(x,y):
z = x + y
return(z)
starttime = time.time()
for i in range(1000000):
x = 1
y = 2
z = betteradd(x,y)
print(z)
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):
#--------------------
exists = False
while exists == False:
for x in range(len(array)):
if value == array[x]:
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')
- some problems can't be solved (undecidable)
- for these problems, approximations, using heuristics, genetic , and machine learning methods, are made
- examples !
- Universality of a Nondeterministic Pushdown automaton: determining whether all words are accepted.
- The halting problem for a Minsky machine: a finite-state automaton with no inputs and two counters that can be incremented, decremented, and tested for zero
- Trakhtenbrot's theorem - Finite satisfiability is undecidable
- The halting problem (determining whether a Turing machine halts on a given input) and the mortality problem (determining whether it halts for every starting configuration).
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,
'RanchoBernrdo':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):
time = 0
order = []
school = ""
for x in range(len(data)):
min = 15000 #setting min to a big number
for location, time in data[order[(len(order))]]:
if time < min: #if time of location is less than the min set, then make the new min the time of that location
school = location
min = time
dt += min
order.append(school)
order.append(start)
return (dt, order)
start = 'DelNorte'
answer = fastestroute(start, dataset)
for x, location in answer[0]:
print(str(x + 1) + location)
print("Time:", answer[0])