Video 3.17-18 Hacks
Notes
3.17.1
- A problem is a description of a task that may or may not be able to be solved through the use of an algorithm. An instance of a problem includes a specific input. One example of this type of problem is a sorting problem.
- A decision problem is a problem with a binary answer (yes or no). An optimization problem is a problem with the objective of finding the BEST solution amongst many possibilities to solve a problem.
- An algorithm's efficiency is determine through formal or mathematical reasoning.
It is important to know which algorithm is the most efficient and if the algorithm can work for that specific situation.
3.17.2
An algorithm is a process or set of rules to be followed in calculations or other problem-solving operations.
There are four different types of algorithms.
- 1 step: The first step consists of an integer being multiplied by a variable 'n'. An example of this could be 5 * n.
- Linear
- 2 step: A two-step algorithm consists of an integer to the power of the variable 'n'.
- Exponential
- 3 step: A three-step algorithm is an algorithm where there is a variable multiplied by an integer, all to the power of 2.
- Square
- 4 step: A four-step algorithm is a variable factorial. For instance, 5! = 5 4 3 2 1 = 120.
- Factorial
When an algorithm is linear or square, it runs in a reasonable amount of time. However, if the algorithm is exponential or factorial, they are considered to be run in an unreasonable amount of time. A "reasonable amount of time" is when the algorithm increases by smaller values instead of jumping from a lower value to a much higher value.
Run Times
We can categorize the run time of an algorithm according to how the number of steps increases as the input size increases. Does it always take the same amount of time? That's a constant increase, a very fast run time. Does it always require looking at every possible permutation of the input? That's an exponential increase, a very slow run time. Most run times are somewhere between.
Constant Time
When an algorithm runs in constant time, it means that it always takes a fixed number of steps, no matter how large the input size increases.
Linear Time
When an algorithm grows in linear time, its number of steps increases in direct proportion to the input size.
Quadratic Time
When an algorithm grows in quadratic time, its steps increase in proportion to the input size squared. Several list sorting algorithms run in quadratic time, like selection sort. That algorithm starts from the front of the list, then keeps finding the next smallest value in the list and swapping it with the current value.
Exponential Time
When an algorithm grows in superpolynomial time, its number of steps increases faster than a polynomial function of the input size. An algorithm often requires superpolynomial time when it must look at every permutation of values.
Polynomial time describes any run time that does not increase faster than n^k which includes Constant time, Quadratic time, and other higher degree polynomials. Superpolynomial time describes any run time that does increase faster than n^k which includes Exponential time and factorial time. So polynomial is considered reasonable.
3.18
What is a decidable problem?
These are problems for which algorithms can be written to solve/produce a correct output for all possible inputs.
What is an undecidable problem?
These are problems for which no algorithms can be built that can provide a correct yes or no answer. Undecidable problems may have some instances of algorithmic solutions, but there are no algorithmic solutions that can solve all instances of the problem.
Vocabulary
- Undecidable problem:problems for which no algorithms can be built that can provide a correct yes or no answer or a solution
- Decidable problem:problems for which algorthms could be written to solve/produce a correct output for all inputs.
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.
Answer: A decidable problem is a problem for which algorithms can be written to solve/produce a correct output for all possible inputs. An example is if checking if a specific number is odd or even.
num = 7
if num % 2 == 1:
print("is odd")
else:
print("is even")
An undecidable problem is a problem for which no algorithms can be built that can provide a correct yes or no answer. An example is trying to find what the weather is going to be in a million years, no one can know because no one has traveled a million years.
Hack 3
Rewrite this JavaScript Code in a more efficient way
Answer: When there were two else's I just made one shorter and made it more efficient. I tried to use the recursion method but that did not work. I researched more about the recursion method and I realized that it is a method of solving a computational problem where the solution depends on solutions to smaller instances of the same problem. Recursion solves such recursive problems by using functions that call themselves from within their own code.
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 (a[counter]> a[counter+1] && a[counter]> a[counter-1]){
peak = a[counter]
peak_index = counter
counter = array.length
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
}
}
}
}
data = [9, 1, 7, 6, 2, 8, 5, 3, 4, 0]
data.sort()
print(data)
from itertools import permutations
comb = permutations([1, 2, 3], 3)
for i in comb:
print(i)