Homework 3.17 - 3.18
- 3.17 Algorithmic Efficiency
- 3.18 Undecidable Problems
- Homework!
- Explanation for What Went Wrong
- Update
Vocabulary
- Problem: a general description of a task that can or cannot be solved algorithmically
- Decision Problem: A problem with a yes or no example
- 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
- 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 guaranteed to produce the correct output
3.17 Notes
- There are multiple types of problems
- Decision Problems, which are problems with a yes or no answer
- Organization Problems, which are problems that have a goal of finding the best answer
- In addition to problems, there are also two types of efficiencies when it comes to algorithms
- Polynomial Efficient is a good thing, as adding an extra job will only add a little bit of time
- Exponential Efficient, on the other hand, is a bad thing, as adding even one extra job can exponentially increase the amount of time necessary to complete a task
- In simple terms, the Heuristic Approach is essentially the method in which you find an answer that is "close enough" to be perfect
- This demonstrates that the best or optimal answer to a problem is not always going to be 100% perfect
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):
#--------------------
# uses binary search to make this algorithm more time efficient
low = 0
high = len(array) - 1
while low <= high:
mid = (low + high) // 2
if value < array[mid]:
high = mid - 1
elif value > array[mid]:
low = mid + 1
else:
return True
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')
3.18 Notes
- When it comes to solving problems in our daily lives, computers cannot always do everything correctly
- The video of the halting problem does a great job at demonstrating this, as in the process of feeding "X" with its own blueprints, "H" said that the machine would not get stuck even though it did
- "H" was also wrong in stating that feeding "X" its own blueprints would cause it to get stuck when it did not
- This thus proves that even though "H" is designed to always be right, it cannot always perform tasks correctly with situations like the ones described above
- There are simply certain machines or programs that cannot logically exist because they sometimes state the opposite of what actually happens
- For example, a computer might guess when to stop loading a website that might never load, and this is why the internet connection times out if it takes too long to 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 = {
'Del Norte':{
'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, data):
# create a list of all locations except Del Norte
locations = list(data.keys())
if start in locations:
locations.remove(start)
# create a list to store the order of the locations
order = [start]
# create a variable to store the total driving time
time = 0
# while there are still locations to visit
while locations:
# find the location with the minimum driving time from the current location
min_time = float('inf')
min_location = None
for location in locations:
t = data[order[-1]][location]
if t < min_time:
min_time = t
min_location = location
# add the minimum location to the order and remove it from the list of locations
order.append(min_location)
locations.remove(min_location)
# add the minimum driving time to the total time
time += min_time
# add the driving time from the final location back to Del Norte
time += data[order[-1]][start]
# return the total driving time and order of locations
return time, order
start = 'Del Norte'
# 'dataset' is the name of the nested key value pair
fastestroute(start, dataset)
Explanation for What Went Wrong
I noticed how I kept getting the same error involving the key error "Del Norte", and I tried several times to adjust the naming of Del Norte in the earlier code segment with all of the locations. Despite my efforts, I kept getting the same error. I tried to see if anyone else had a similar issue like this online and tried out what they did to solve it for themselves, but it unfortunately was still not enough to fix the problem. Although I could not get this code segment to work, I still think I was able to learn a lot overall from the lesson for 3.18 and was at least able to show that I did the best I could on this homework assignment.
Update
I was actually able to figure out how to get the code to work. It turns out that the names of the locations in the data set were inconsistent in how they were named, causing the error described above to appear. I corrected the names and made sure that everything was consistent and I was able to get everything working! :)