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
  • Different codes have different efficiencies
  • It is important to pay attention to efficiencies especially when dealing with large code segments and having a limited hardware
  • Improved efficiencies make programs faster and better for users
  • 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

Vocabulary

  • 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

Hack 1

A decidable problem is one which an algorithm will be able to solve no matter the input. An undecidable problem is one where it is not possible for any algorithm to come to a correct solution. Sometimes, an undecidable problem can have some parts solved by an algorithm, but for a problem to be decidable, it must have all parts solved by an algorithm.

Hack 2

  • Answer: C. (3x8)^2
  • This is correct because it is features 2 integers being multiplied together and then raised to the power of 2.

Hack 3

  • Explanation for Code: Defines a function to find a peak, and goes through each item, and checks if it is greater than the stored value.

  • Why this is more efficient: This uses much less code and will work for all lists. This code is easy to write an understand.

    • NOTE: A binary search would be much more time efficient, as it would use exponential time. However, I was having trouble creating this code due to the overall challenge and expertise needed for creating such a complex algorithm.
function peak_finder(array) {
  var peak = array[0];
  for (i = 0; i < array.length; i ++) {
    if (array[i] > peak) {
      var peak = array[i];
    }
  }
  return peak;
}

var numbers = [1, 2, 3, 4, 5, 6, 7, 8];
console.log(peak_finder(numbers));

8

Hack 4

  • Explanation for Code: This code defines a list, which has the numbers. Then, it redefines the list of numbers, using the function in Python called sorted. This automatically sorts the data in order from lowest to highest.

  • Why this is more efficient: This is a much smaller piece of code, making it much easier to write and understand. It calls the data less and does not create any new variables other than data. It uses a built in function to sort the data, instead of recreating a function to do so.

data = [9, 1, 7, 6, 2, 8, 5, 3, 4, 0]
data = sorted(data)
print(data)

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

Hack 5

  • Explanation for Code: Imports the permutation method from the library itertools. Using this, we can use a built in command to create permutations. Using a for loop, we can iterate through all possible permutations, and print them.

  • Why this is more efficient: This is not only a much smaller piece of code, but it does not require recalling a variable multiple times, like in the former program. This is also more efficient for the developer, as it allows for the individual to code much less and in a simpler fashion.

from itertools import permutations

data = [1, 2, 3]

for i in permutations(data):
    print(i)

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