Notes

3.17 Notes

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 specific input
  • decision problem - a problem with a binary answer (yes or no)
  • optimizing problem - a problem with the objective of finding the BEST solution amongst many possibilities to solve a problem
  • algorithm efficienct - determined through formal or mathematical reasoning
  • algorithm - a process or set of rules to be followed in calculations or other problem-solving operations

Algorithms

  • Have 4 steps

Categorizing run times

Constant time:

  • always takes a fixed number of steps, no matter how large the input size increases.

Linear time:

  • number of steps increases in direct proportion to the input size.

Quadratic time:

  • steps increase in proportion to the input size squared.

Epxponential time:

  • number of steps increases faster than a polynomial function of the input size.

Polynomial:

  • any run time that does not increase faster than n^k which includes Constant time, Quadratic time, and other higher degree polynomials.

Superpolynomial:

  • 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.

3.18 Notes

Decidable problems

These are problems for which algorithms can be written to solve/produce a correct output for all possible inputs. They have simple yes or no answers, true or false, even or odd.

Undecidable problems

These are problems for which no algorithms can be built that can provide a correct yes or no answer. Cannot be solved with any algorithm.

Hacks

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 used to solve simple yes or no problems. Examples of a decidable problem would be:

  • Is it raining?
  • Is it sunny?
  • Are you in school?

Undecidable problems don’t provide a yes or no answer and can’t be solved with an algorithm. These problems may be partially decidable but they will never be decidable. Examples of a undecidable problem would be:

  • God is omnipotent, so can God create a stone that he cannot lift?

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

C, is a three step algorithm because you first have to multiple 3 x 8 (24) and then multiply 24 times 24 (576).

Hack 3

↑ Rewrite this JavaScript Code in a More Efficient Way ↑

Answer:

I didn’t quite understand this hack so I looked at the answer, but from looking at the answer I can tell the differences between the code. First and most obviously, the code was compressed into a smaller form and made shorter/simpler to understand while running the same as the lengthened code. The second thing I notice is that the code in the answer didn’t set the counter, peak, or peak_index to 0, I believe this is because the counter can assume that it is starting at 0 rather than having to write it. The next part of the code is the if else functions that become shortened by commands used such as: array.slice, mid_index (middle of the index is used), reversing the array, and finding the peak of the array. Although, I didn’t quite understand I get why making the code shortened is more beneficial to save time and makes the code look clearer and better to process.

Hack 4

↑ Rewrite this Python Code in a More Efficient Way ↑

Answer:

The code in this could easily have been sorted by using a simple command of creating a variable name and adding a command to sort it. I added my data in a list unsorted, showed it unsorted then proceeded to sort it and show the outcome of it sorted.

Hack 5

↑ Rewrite this Python Code in a More Efficient Way ↑

Answer:

The code defines the function and then procedes to use iteration to go over data structures of all the different ways the numbers 1, 2, and 3 can be ordered. Then it prints the outcome. Simplified and made easy on the eye!