Vocab

  • Problem: description of a task that may or may not be able to be solved through the use of an algorithm.
  • Decision problem: a problem with a binary answer (yes or no).
  • Optimization problem: a problem with the objective of finding the BEST solution amongst many possibilities to solve a problem.
  • Decidable problem: problem for which algorithms can be written to solve/produce a correct output for all possible inputs.
  • Undecidable problem: These are problems for which no algorithms can be built that can provide a correct yes or no answer.

Notes

  • An algorithm's efficiency is determine through formal or mathematical reasoning.
  • An algorithm’s efficiency can be informally measured by determining the number of times a statement or group of statements executes.
  • Algorithms with a polynomial efficiency or slower (constant, linear, square, cube, etc.) are said to run in a reasonable amount of time. Algorithms with exponential or factorial efficiencies are examples of algorithms that run in an unreasonable amount of time.
  • Some problems cannot be solved in a reasonable amount of time because there is no efficient algorithm for solving them. In these cases, approximate solutions are sought.

Hacks

  1. Decidable problems are designed to produce an output for every possible input, and example is Linear Search. Undecidable problems cannot have algorithms be built that can produce a correct answer an example is a paradox.

  2. C. is a three step algorithm

  3. peakFinder code

function findpeak(ar)
{
    var peak = -Infinity;

    // Cycle through all the elements of the array
    for(var i = 0; i < ar.length; i++)
    {
        var el = ar[i];

        // If an element is of type array then invoke the same function
        // to find out the maximum element of that subarray
        if ( Array.isArray(el) )
        {
            el = findpeak( el );
        }

        if ( el > peak )
        {
            peak = el;
        }
    }

    return peak;
}
  1. merge sort
arr = [5,1,6,2,7,3,4,8]


def Merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2
        left = arr[:mid]
        right = arr[mid:]

        Merge_sort(left)
        Merge_sort(right)

        i = 0
        j = 0
        k = 0

        while i < len(left) and j < len(right):
            if left[i] <= right[j]:
                arr[k] = left[i]
                i += 1
            else:
                arr[k] = right[j]
                j += 1
            k += 1

        while i < len(left):
            arr[k] = left[i]
            i += 1
            k += 1
        while j < len(right):
            arr[k] = right[j]
            j += 1
            k += 1

MS = Merge_sort(arr)
for i in range(len(arr)):
    print(arr[i])

1
2
3
4
5
6
7
8
  1. Heap Permutation
def heap_permutation(data, n):
    if n == 1:
        print(data)
        return
        
from itertools import permutations 

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

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

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