vocab

  • Problem: a description of a task that may or may not be able to be solved through the use of an algorithm
  • Instance of a problem: includes a specific input
  • Decision problem: Problem with a binary answer (yes or no)
  • Optimization problem: Problem with the objective of finding the BEST solution amongst many possibilities to solve a problem
  • Decidable Problems: problems for which algorithms can be written to solve/produce a correct output for all possible inputs
  • Undecidable Problems: problems for which no algorithms can be built that can provide a correct yes or no answer
  • Some undecidable problems can have algorithms to solve some parts, but not all parts of the problem
  • 1 Step Problem: When an integer is multiplied by a value(Linear)
  • 2 Step Problem: When an integer is raised to a power of n(Exponential)
  • 3 Step Problem: When an integer is multiplied by a value, and then raised to a power of 2(Square)
  • 4 Step Problem: A factorial problem
  • Constant Time: Will always take the same number of steps, no matter how large input it
  • Linear Time: The number of steps increases in direct proportion to the input size
  • Quadratic Time: The number of steps increase in proportion to the input size squared
  • Exponential Time: The number of steps increase in proportion to the input size squared
  • Polynomial time: any run time that does not increase faster than n^k which includes constant time, quadratic time, and other higher degree polynomials
  • Superpolynomial time: any run time that does increase faster than n^k which includes Exponential time and factorial time
  • Reasonable Time: Algorithms with a polynomial efficiency or lower (constant, linear, square, cube, etc.)
  • Unreasonable Time: Algorithms with exponential or factorial efficiencies

    Notes

    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 can not be solved in a reasonable amount of time, so when this is the case, an approximate solution is found.

Hack 1

A decidable problem is a problem for which an algorithm or a procedure can be written that always terminates after a finite number of steps and correctly answers whether a given input to the problem is a valid solution or not. An example of a decidable problem is determining whether a given string of text is a palindrome (a word or phrase that reads the same forwards and backwards). An undecidable problem is a problem for which it is impossible to design an algorithm or a procedure that always terminates and correctly answers whether a given input is a valid solution or not. An example of an undecidable problem is the Halting problem, which is the problem of determining, given a description of an arbitrary computer program and an input, whether the program will finish running or continue to run forever.

Hack 2

Answer = None of the above. A. 2 x 6 x 8 is a mathematical expression that evaluates to 96, but it is not an algorithm.

B. 4^5 is a mathematical expression that evaluates to 1024, but it is not an algorithm.

C. (3 x 8)^2 is a mathematical expression that evaluates to 144, but it is not an algorithm.

Hack 3

function peakFinder(array) { let start = 0; let end = array.length - 1; while (start <= end) { let mid = Math.floor((start + end) / 2); if (array[mid] > array[mid-1] && array[mid] > array[mid+1]) { return The ${mid} indexed number, ${array[mid]} is a peak; } else if (array[mid] < array[mid-1]) { end = mid - 1; } else { start = mid + 1; } } return “No peak element found”; }

Hack 4

def merge_sort(data): if len(data) <= 1: return data

mid = len(data) // 2 left_data = merge_sort(data[:mid]) right_data = merge_sort(data[mid:])

left_index = 0 right_index = 0 sorted_data = []

while left_index < len(left_data) and right_index < len(right_data): if left_data[left_index] < right_data[right_index]: sorted_data.append(left_data[left_index]) left_index += 1 else: sorted_data.append(right_data[right_index]) right_index += 1

sorted_data += left_data[left_index:] sorted_data += right_data[right_index:]

return sorted_data

if name == ‘main’: data = [9, 1, 7, 6, 2, 8, 5, 3, 4, 0] sorted_data = merge_sort(data) print(sorted_data)

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