Do Now!!!

Set up your notebook by either wgetting the lesson or tracking it by your own (We would recommend wgetting since there are some fill in the blanks!)
wget here: https://raw.githubusercontent.com/mmaxwu/Tri2-GroupFastpages/master/_notebooks/2022-12-dd-lesson.ipynb

3.17: Algorithm Efficiency

Purpose:

The purpose of this lesson is to help students understand how to make an efficient program and optimize it and understand its importance to the CSP curriculum.

What is Algorithmic Efficiency?

The ability of an algorithm to solve a problem in an efficient way
- An efficient algorithm solves a problem quickly and with a minimum amount of resources, such as time and memory.
How do we determine if an algorithm is efficient or not?
- One way we can do this is by determining the time complexity of the algorithm.
- Another way is through space complexity.

Traveling Merchant Problem Hacks:

What did you and your team discuss? (record below)

We can try every possible route and determine which one is the shortest. (All of them will look like an incomplete circle)

A heuristic solution is an approach to a problem that produces a solution that isn't necessarily optimal but can be used when normal methods take forever

Describe the method used to solve the traveling merchant problem. (record below)

Indianapolis > Cincinnati > Louisville > Chicago > Detroit > Columbus > Indianapolis

Find the shortest distance to a neighboring city and take that route.

3.18: Undecidable Problems

Purpose:

The purpose of this lesson is to introduce students to the concept of undecidable problems in computer science and to explain why these problems are important.

Key vocabulary:

Decision problem
Decidable problem
Undecidable problem

Decision Problem

A decision problem is a problem in computer science and mathematics that can be solved by a yes-no answer, also known as a binary answer. In other words, a decision problem is a problem for which there are only two possible outputs:"yes" or "no". There are two types of decision problems that Collegeboard goes over:

Decidable Problems

Undecidable Problems

A decidable problem is a problem in computer science and mathematics for which an algorithm can be created that can always produce a correct answer or solution. In other words, a decidable problem is a problem for which there exists an algorithm that can be used to determine whether a given input is a valid solution or not.

An undecidable problem is a problem in computer science and mathematics for which it is impossible to create an algorithm that can always provide a correct answer or solution. This means that it is not possible for an algorithm to always determine whether a given input is a valid solution to an undecidable problem.

Decidable Problems

A decidable problem is an algorithm that can always have an output of yes or no given any input. It is always correct.

Example of a Decidable Problem

The procedure below tests to see if a number is divisible by 13. If it is, it returns true. If it isn't, it returns false.

def divideThirteen(number):
    if number % 13 == 0:
        return True
    else:
        return False

print(divideThirteen(26))
print(divideThirteen(30))

True
False

Undecidable Problems

An Example of a Forever Running Code

The code keeps adding 1 to the variable number until number is no longer an integer(This is not the python data type "integer", it's the integer in number theory). However, there is no end to this code, making the computer run forever. There is no halt to the code.

# This is not an undecidable problem
i = 0
number = 1
def integerTest(n):
    # Testing if the number is an integer
    if n%1 ==0:
        return True
    else:
        return False
# Using while loop to keep searching an a non-integer above 1. Note that the computer runs forever.
while i == 0:
    number += 1
    if integerTest(number) == False:
        i +=1
        print("Done")

The Halting Problem

The halting problem is an example of an undecidable problem. It states that it is not always possible to correctly determine whether a code halts or runs forever.

There is no way to write an algorithm to analyze and determine whether a body of code can run forever or not.

Halting Problem Example:

In order to understand this, suppose that an algorithm was able to analyze whether a code halts or not. Let's call this algorithm HaltChecker.
HaltChecker analyzes the program,program P, and its input,input I. If program P halts with input I, HaltChecker returns an output of "halts". If program P doesn't halt(runs forever) with input I, HaltChecker returns an output of "never". For example, in the code where it tests if variable number, the code runs forever, so HaltChecker returns an output of "never".
Then, we add another algorithm called Reverser which reverses HaltChecker's output. So, if "never" is the output of HaltChecker, then the output of Reverser is "halts". It's also the same the other way around: if HaltChecker has an output of "halts", then Reverser has an output of "never".
We combine these algorithms into one entire body of code.
Since Reverser is the algorithm at the end, hence giving the ultimate output, notice how it prints "never" when in fact there is an end(As proved by HaltChecker), and how it also prints "halts" when there is in fact is no end to the code(Also proved by HaltChecker). As a result, HaltChecker is inaccurate and this is an undecidable problem.

This Diagram Sums up the Entire Process in the Bulleted List:

reverser

Credits of diagram and example to Khan Academy

FAQ

Q: If Reverser is causing the problem, why not remove it?
A: Removing Reverser will remove the problems, however, we are looking for ways which create the problem of not outputting a correct result. One example is enough to prove that it is an undecidable problem since it proves that the code is not completely accurate.

Extra Things to Notice

Note that while a computer may take a long time to run a section of code, it does not mean that the computer is going to run forever.
Humans are able to solve some undecidable problems. The entire Halting Problem example was to prove that computers cannot solve undecidable problems.

Hacks

Come up with one situation in which a computer runs into an undecidable problem. Explain why it is considered an undecidable problem.

One situation in which a computer might run into an undecidable problem is if it is asked to determine whether a given statement in first-order logic is true or false. This problem is known as the decision problem, and it is considered to be undecidable because there is no algorithm that can always determine the truth or falsehood of a given statement in first-order logic. This is because first-order logic is a powerful and expressive language that can be used to describe a wide range of concepts and relationships, and it is impossible to predict how a given statement will behave in all possible scenarios. Furthermore, there are statements in first-order logic that are known to be true, but for which there is no proof within the system, making it impossible to determine their truth or falsehood using a logical algorithm.

3.17 Homework

Your homework for Algorithmic Efficiency is pretty simple.

Use the 1st code below and graph it (Desmos, TI Inpire Cas, e.t.c), change the x value only!
Label the number of loops done as x and the time (microseconds) to find the index as y
Connect the points
Do the same thing with the 2nd code
Compare the two graphs and explain which one of the two is more efficient and why (min. 2 sentences)
Insert images of the graph either in your blog or on review ticket

import time

def linear_search(lst, x):
    start_time = time.perf_counter_ns() # records time (nanoseconds)
    for i in range(len(lst)): # loops through the entire list 

        if lst[i] == x: # until the x value we are looking for is found
            end_time = time.perf_counter_ns() # records time again
            total_time = (end_time - start_time) // 1000 # subtracts last recorded time and first recorded time
            print("Found element after {} loops in {} microseconds".format(i+1, total_time)) # prints the results
            return print("Your number was found at", i)
            
    end_time = time.perf_counter_ns() # records the time again
    total_time = (end_time - start_time) // 1000 # subtracts last recorded time and first recorded time
    print("Element not found after {} loops in {} microseconds".format(len(lst), total_time)) # prints the results
    return "Your number wasn't found :("


lst = list(range(1, 10001)) # list with numbers 1-10000

x = 10000 # replace with an integer between 1 and 10000 (I suggest big numbers like 500, 2000, so on)

linear_search(lst, x) # runs procedure

import time 

def binary_search(lt, x):
    start_time = time.perf_counter_ns() # starts timer
    low = 0 # sets the lower side 
    mid = 0 # sets mid value
    high = len(lt) -1 # sets the higher side
    num_loops = 0 # number of loops the search undergoes to find the x value

    while low<=high: # Loop ran until mid is reached
        num_loops += 1 # adds one loop each time process is repeated
        mid = (low + high) // 2 # takes the lowest and highest possible numbers and divides by 2 and rounds to closest whole #

        if lt[mid] == x:
            end_time = time.perf_counter_ns() # records time
            total_time = (end_time - start_time) // 1000 # time in microseconds
            print("Element found after {} loops in {} microseconds".format(num_loops, total_time)) # prints the results
            return mid # returns the index value

        elif lt[mid] > x: # if mid was higher than x value, then sets new highest value as mid -1 
            high = mid -1 

        elif lt[mid] < x:
            low = mid + 1 # if mid was lower than x, sets the new low as mid + 1
            
    end_time = time.perf_counter_ns()
    total_time = (end_time - start_time) // 1000 
    print("Element not found after {} loops in {} microseconds".format(num_loops, total_time)) # prints the results
    return "Your number wasn't found :("


lt = list(range(1, 10001)) # list with numbers 1-10000

x = 10000 # replace with an integer between 1 and 10000 (I suggest big numbers like 500, 2000, so on)

binary_search(lt, x) # runs procedure

Graph 1

Graph 2

Comparison

The graph of procedure #2 fluctuates more, however, the average time is far less in comparison to that of the first procedure. This proves that procedure #2 is generally more efficient and lighter on the computer than procedure #1.

3.18 Homework:

Use the Jupyter notebook to write an algorithm that solves a decidable problem. You can use math or whatever else you would like to do.
Write code to get the computer to run forever. Check this example if you need help, but please come up with your own idea.

# Here is an algorithm that solves a decidable problem
# It finds the maximum value in a list


# defines the maximum value function
def max_value(numbers):
  # sets the initial maximum value to the first number in the list
  max_val = numbers[0]

  # iterates over the numbers in the list
  for number in numbers:
    # if the current number is greater than the maximum value,
    # update the maximum value
    if number > max_val:
      max_val = number

  # return the maximum value
  return max_val


lst = [2, 5, 3, 6, 4, 1]

max_value(lst)

6

# This procedure runs forever

def run_forever(n):
  while True:
    n += 2
    print(n)

run_forever(7)

# The error below appears because I have to force stop the procedure. This is the expected outcome

---------------------------------------------------------------------------
KeyboardInterrupt                         Traceback (most recent call last)
/home/azeemk/vscode/fastpages-project/_notebooks/2022-12-14-studentTeaching17-18.ipynb Cell 22 in <cell line: 6>()
      <a href='vscode-notebook-cell://wsl%2Bubuntu/home/azeemk/vscode/fastpages-project/_notebooks/2022-12-14-studentTeaching17-18.ipynb#X31sdnNjb2RlLXJlbW90ZQ%3D%3D?line=2'>3</a>     n += 2
      <a href='vscode-notebook-cell://wsl%2Bubuntu/home/azeemk/vscode/fastpages-project/_notebooks/2022-12-14-studentTeaching17-18.ipynb#X31sdnNjb2RlLXJlbW90ZQ%3D%3D?line=3'>4</a>     print(n)
----> <a href='vscode-notebook-cell://wsl%2Bubuntu/home/azeemk/vscode/fastpages-project/_notebooks/2022-12-14-studentTeaching17-18.ipynb#X31sdnNjb2RlLXJlbW90ZQ%3D%3D?line=5'>6</a> run_forever(7)

/home/azeemk/vscode/fastpages-project/_notebooks/2022-12-14-studentTeaching17-18.ipynb Cell 22 in run_forever(n)
      <a href='vscode-notebook-cell://wsl%2Bubuntu/home/azeemk/vscode/fastpages-project/_notebooks/2022-12-14-studentTeaching17-18.ipynb#X31sdnNjb2RlLXJlbW90ZQ%3D%3D?line=1'>2</a> while True:
      <a href='vscode-notebook-cell://wsl%2Bubuntu/home/azeemk/vscode/fastpages-project/_notebooks/2022-12-14-studentTeaching17-18.ipynb#X31sdnNjb2RlLXJlbW90ZQ%3D%3D?line=2'>3</a>   n += 2
----> <a href='vscode-notebook-cell://wsl%2Bubuntu/home/azeemk/vscode/fastpages-project/_notebooks/2022-12-14-studentTeaching17-18.ipynb#X31sdnNjb2RlLXJlbW90ZQ%3D%3D?line=3'>4</a>   print(n)

File ~/.local/lib/python3.8/site-packages/ipykernel/iostream.py:542, in OutStream.write(self, string)
    539     raise ValueError("I/O operation on closed file")
    540 else:
--> 542     is_child = not self._is_master_process()
    543     # only touch the buffer in the IO thread to avoid races
    544     with self._buffer_lock:

File ~/.local/lib/python3.8/site-packages/ipykernel/iostream.py:430, in OutStream._is_master_process(self)
    429 def _is_master_process(self):
--> 430     return os.getpid() == self._master_pid

KeyboardInterrupt: