3.17 Algorithmic Efficiency

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

Challenge

Try and fix this ineficcient code! Only change the code between the two commented lines. Fully programmed solution will improve your grade, at a minimum show that you tried.

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')
0.2598538398742676 seconds

3.18 Undecidable Problems

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)
(105, ['Del Norte', 'Westview', 'Poway', 'RanchoBernardo', 'MtCarmel'])

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! :)

Grading:

Challenge Homework
.15 pts for attempt .65 for attempt
.20 pts for complete .70 for complete
.25 pts for above and beyond .75 pts for above and beyond