Notes

Vocab Definition
Problem a description of a task that may or may not be able to be solved through the use of an algorithm. An instance of a problem includes a specific input. One example of this type of problem is a sorting problem.
Decision problem a problem with a binary answer (yes or no). An optimization problem is a problem with the objective of finding the BEST solution amongst many possibilities to solve a problem.
Algorithm's efficiency determined through formal or mathematical reasoning.
  • An algorithm is a process or set of rules to be followed in calculations or other problem-solving operations.

There are four different types of algorithms.

  • 1 step: The first step consists of an integer being multiplied by a variable 'n'. An example of this could be 5 * n.

    Linear

  • 2 step: A two-step algorithm consists of an integer to the power of the variable 'n'.

    Exponential

  • 3 step: A three-step algorithm is an algorithm where there is a variable multiplied by an integer, all to the power of 2.

    Square

  • 4 step: A four-step algorithm is a variable factorial. For instance, 5! = 5 4 3 2 1 = 120.

    Factorial

Run Times

  • We can categorize the run time of an algorithm according to how the number of steps increases as the input size increases. Does it always take the same amount of time? That's a constant increase, a very fast run time. Does it always require looking at every possible permutation of the input? That's an exponential increase, a very slow run time. Most run times are somewhere between.

    Constant Time

  • When an algorithm runs in constant time, it means that it always takes a fixed number of steps, no matter how large the input size increases.

    Linear Time

  • When an algorithm grows in linear time, its number of steps increases in direct proportion to the input size.

    Quadratic Time

  • When an algorithm grows in quadratic time, its steps increase in proportion to the input size squared. Several list sorting algorithms run in quadratic time, like selection sort. That algorithm starts from the front of the list, then keeps finding the next smallest value in the list and swapping it with the current value.

    Exponential Time

  • When an algorithm grows in superpolynomial time, its number of steps increases faster than a polynomial function of the input size. An algorithm often requires superpolynomial time when it must look at every permutation of values.

  • Polynomial time describes any run time that does not increase faster than n^k which includes Constant time, Quadratic time, and other higher degree polynomials. Superpolynomial time describes any run time that does increase faster than n^k which includes Exponential time and factorial time. So polynomial is considered reasonable.

What is a decidable problem?

  • These are problems for which algorithms can be written to solve/produce a correct output for all possible inputs.

What is an undecidable problem?

  • These are problems for which no algorithms can be built that can provide a correct yes or no answer. Undecidable problems may have some instances of algorithmic solutions, but there are no algorithmic solutions that can solve all instances of the problem.

Vocabulary

  • Undecidable problem:problems for which no algorithms can be built that can provide a correct yes or no answer or a solution Decidable problem:problems for which algorthms could be written to solve/produce a correct output for all inputs.

Hack 1

Please write a short 1-2 sentence explanation describing the difference between decidable and undecidable problems. Make sure to provide at least one example of each.

Decidable problems can be use to design an algorithm unlike undecidable problems that cannot give an algorithm. If any decision problem has a correct algorithm that runs for finite amount of time, then the problem is decidable. Undecidable problems have no algorithm that gives correct output in finite time.

Decidable problem example 

num = 10  #set number equal to random value 
if num > 5: # if the number is greater than 10 
    print("greater than 5") #print 
else: # if less than 10 
    print("not greater than 5") # print

greater than 5

Undecidable problem example 

num = 1
while num == 0: 
  print(num)
  num = num + 1

while num == 0: the number will never equal 0 since it is set to 1, therefore, this is undecidable

Hack 2

Which of the following is a 3 step algorithm?

A. 2 x 6 x 8

B. 4^5

C. (3 x 8)^2

D. None of the above

E. All of the above

EXPLANATION: C is a 3 step algorithm because a variable is being multiplied to an integer, all to the power of two, fitting the criteria of a 3 step algorithm.

Hack 3

Rewrite this JavaScript Code in a More Efficient Way (Hint: Use Binary Search)

function peak_finder(array){
  let counter = 0
  let peak = 0
  let peak_index =0
  while (counter <= array.length){
    console.log(counter)
  if (counter === 0){
    if (a[0]>=a[1]){
      peak = a[0]
      peak_index = counter
      counter = array.length
      return `The ${counter-1} indexed number, ${peak} is a peak`
    }else{
      counter+=1
    }
  }else if(counter === array.length-1){
     if (a[array.length-1] >= a[array.length-2]){
     peak = a[array.length-1]
     peak_index = counter
     counter = array.length
     return `The ${counter-1} indexed number, ${peak} is a peak`
     }
   }else{
      if (a[counter]> a[counter+1] && a[counter]> a[counter-1]){
      peak = a[counter]
      peak_index = counter
      counter = array.length
      return `The ${counter-1} indexed number, ${peak} is a peak`
    }else{
      counter += 1
    }
  }
}
}

  Input In [8]
    function peak_finder(array){
             ^
SyntaxError: invalid syntax

My Hack 3 answer 

function peak_finder(array){
    let counter = 0
    let peak = 0
    let peak_index =0

    recurse(peak_finder);
    // function code
}

recurse();

Recursive function research and example

I was a bit confused on how to rewrite this code in a more efficient way. Now I understand that I would use a recursion to print the outputs in reverse. To learn more about recursion, I took some notes while researching more about it.

Notes

  • A recursive function is a function that calls itself. You essentially create a loop with a function. As you can imagine, these can be tricky functions to write. You do not want your code to run forever.

  • Similar to a loop, a recursive function will be controlled by a condition. Once the condition is met, the function stops calling itself, which stops the loop. This is how you can create a function that calls itself without it running forever.

  • Although a recursive function acts like a loop, it is executed by the computer differently. So, some algorithms are more efficient in a loop and others benefit from a recursive function. But before we look at how to use a recursive function, you need to know how to write one.

FUNCTION name
  IF condition THEN
    RETURN result
  ELSE
    CALL FUNCTION name
END FUNCTION

def factorialFunction(numberToMultiply):
 if numberToMultiply == 1 :
  return 1
 else :
  return numberToMultiply * factorialFunction(numberToMultiply - 1)
 
result = factorialFunction(3)

print(result)

//Outputs: 6

def recursiveFunction(number) :
  if (number % 2) == 0 :
    return number
  else:
    print("That number is not even. Please enter a new number:")
    recursiveFunction(int(input()))
 
print("Enter and even number:")
i = recursiveFunction(int(input()))

Hack 4

Rewrite this Python Code in a More Efficient Way

def merge_sort(data):
    if len(data) <= 1:
        return
    
    mid = len(data) // 2
    left_data = data[:mid]
    right_data = data[mid:]
    
    merge_sort(left_data)
    merge_sort(right_data)
    
    left_index = 0
    right_index = 0
    data_index = 0
    
    while left_index < len(left_data) and right_index < len(right_data):
        if left_data[left_index] < right_data[right_index]:
            data[data_index] = left_data[left_index]
            left_index += 1
        else:
            data[data_index] = right_data[right_index]
            right_index += 1
        data_index += 1
    
    if left_index < len(left_data):
        del data[data_index:]
        data += left_data[left_index:]
    elif right_index < len(right_data):
        del data[data_index:]
        data += right_data[right_index:]
    
if __name__ == '__main__':
    data = [9, 1, 7, 6, 2, 8, 5, 3, 4, 0]
    merge_sort(data)
    print(data)

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

My Hack 4 answer 

data = [9, 1, 7, 6, 2, 8, 5, 3, 4, 0] # unsorted/not in order list of numbers 

print("unsorted data:", data) # unsorted data 

data.sort()  # sort function to sort through data 

print("sorted data", data) # sorted data 

unsorted data: [9, 1, 7, 6, 2, 8, 5, 3, 4, 0]
sorted data [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

I found that using the sort() function was an easier algorithm as it quickly sorts through the list and prints data in order. Since I used the sort() function, I avoided using statements or while loops.

Hack 5

Rewrite this Python Code in a more efficient way

def heap_permutation(data, n):
    if n == 1:
        print(data)
        return
    
    for i in range(n):
        heap_permutation(data, n - 1)
        if n % 2 == 0:
            data[i], data[n-1] = data[n-1], data[i]
        else:
            data[0], data[n-1] = data[n-1], data[0]
    
if __name__ == '__main__':
    data = [1, 2, 3]
    heap_permutation(data, len(data))

My Hack 5 Answer 

from itertools import permutations # using library function 
  
perm = permutations([1, 2, 3], 3) # 3 on outside the bracket is all the permutations of the length 3
  
 
for i in list(perm): 
    print ([i]) # print the obtained permutations

[(1, 2, 3)]
[(1, 3, 2)]
[(2, 1, 3)]
[(2, 3, 1)]
[(3, 1, 2)]
[(3, 2, 1)]

To use the permutations function (returns the number of permutations that are possible for a specified number of objects in a given set), I imported the itertools module.

In this function, it takes a list as an input and returns an object list of tuples ( finite ordered list of elements). The list of tuples that is returned contains all permutations in a list form.

I used the list [1,2,3] from the example above and set a parameter of 3 which would be the length of the permutation since there are 3 numbers.

I then used a for loop to loop through all possible permutations.