Notes 3.17

Problem: a description of a task that can be solved through an algorithm.

  • Instance: includes a specific input, ex: sorting problem

Decision problem: binary problem with answer (yes or no)

Optimization problem: finding the best solution amongst many

Efficiency of an algorithm is determined through formal or mathematical reasoning.

Reasonable amount of time: Linear or square algorithm Unreasonable amount of time: Exponential or factorial algorithm

Types of Run Times (when input increases, does the number of steps it takes to solve the problem increase)</p>

Constant Time: fixed number of steps no matter input

Linear Time: steps increase proportional to input

Quadratic Time: steps increase proportional to input squared

Exponential Time: steps increase faster than polynomial function of input

Notes 3.18

Computers can't solve all problems. Even problems they can solve, may not be able to be done in a short enough amount of time.

Undecidable problem: Problems where an algorithm cannot be built to give an accurate yes or no answer

Decidable problem: Problems for which an algorthm could be written to provide a correct answer

</div> </div> </div>

Hack 1 A decidable problem is one which can be solved with an algorithm and a correct answer with be outputted (example: average of 10 integers). An undecideable problem is one which cannot be correctly solved with an algorithm (example from research: whether a CFG generates all the strings or not).

Hack 2 C, because the algorithm includes a square (classified as 3 steps and reasonable)

Hack 3

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
    }
  }
}
}

function peak_finder2(array){
    if (array.length) === 0{
       return  `Array cannot be empty`
     }else if (array.length === 1){
       return array[0]
     }else{
       let mid_index = Math.floor(array.length*0.5)
      if (array[mid_index +1]>array[mid_index]){
         return peak_finding(array.slice(mid_index + 1 ))
       }else if (array[mid_index -1]>array[mid_index]){ 
        new=array.reverse().slice(mid_index+1).reverse()
        return peak_finding(new)  
        }else{
         return array[mid_index]
        }
      }
}

I had trouble shortening the code myself, so I compares the two and analyzed why the section of code was shortened the way it was.

Explanation: Because counter, peak, and peal_index all equal 0, it is uneccesary to seperate the let statements. Instead the series of else/if statements based on the arrays relative size to zero, can be done as such (instead of using different variables that are not needed).

Hack 4

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]

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

data.sort()

print(data)

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

With help of W3 Schools, I was able to find a much simpler way of sorting the values in a list. This sort() method will also work to sort values in a list alphabetically.

Hack 5

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

[1, 2, 3]
[2, 1, 3]
[3, 1, 2]
[1, 3, 2]
[2, 3, 1]
[3, 2, 1]

from itertools import permutations

perm = permutations([1, 2, 3])

for i in list(perm):
    print(i)

(1, 2, 3)
(1, 3, 2)
(2, 1, 3)
(2, 3, 1)
(3, 1, 2)
(3, 2, 1)

Use of permutations by using a prexisting algorithm is most efficient, and shortens the code significantly.

from itertools import combinations_with_replacement

comb = combinations_with_replacement([1, 2, 3], 3)

for i in list(comb):
    print(i)

(1, 1, 1)
(1, 1, 2)
(1, 1, 3)
(1, 2, 2)
(1, 2, 3)
(1, 3, 3)
(2, 2, 2)
(2, 2, 3)
(2, 3, 3)
(3, 3, 3)

There is also an option of using combinations in python, which may be useful in certain statistical contexts.

Reflection

I found this lesson interesting and relavant, as it shows different ways to identify if a computer will be able to efficiently solve a problem. When a computer cannot solve a problem in a timely manner using the resources provided by code, it is important to find alternate ways to help it complete the same function (as demonstrated in hacks).

</div>