APCSP UNIT 8 : DATA

UNIT 8 : DATA

Data Limitations:

Misleading visualizations → truncated y-axis : not starting from 0, omitting data : leaving out points to make a fake trend, breaking convention : tricks the viewer, where slices of the pie chart are not accurately displayed as it’s percentage of the whole, correlation does not imply causation

Data Sanitization : throwing out data that is not well formatted

Binary vs Sequential searching:

Sequential searching locates target values by examining elements from start to finish. Binary search locates the target value from sorted values. This process successively eliminates half the list from consideration.

Algorithm: An algorithm is a step-by-step procedure or set of rules for solving a specific problem or accomplishing a task within a finite number of steps.

Approximate Solution: An approximate solution is a solution that is not exact or precise, but rather an estimation or close enough answer to a problem. It provides a reasonable and practical result without the need for complete accuracy.

Computational Resources: Computational resources refer to the hardware and software components necessary for performing computations or running programs.

Algorithm Efficiency: Runtime + Memory usage

Algorithm Analysis Notation: 

• “N” refers to the number of things being processed

• “T” time complexity, T(n) = the approx. time (# of operational steps) to execute the algorithm as a function of ‘n’

• O(n)  asymptotic upper bound, upper bound on performance as n → infinity : the worst case

• Θ(n) tighter upper/lower bound, as n → infinity

• Ω(n) lower bound on performance, as n → infinity : the best case

Exponential Efficiency: Exponential efficiency refers to an algorithm or function whose running time grows exponentially with respect to its input size. In other words, as the input gets larger, this type of algorithm experiences rapid growth in its execution time.

Factorial Efficiency: Factorial efficiency refers to an algorithm or function whose running time grows factorially with respect to its input size. In other words, as the input gets larger, this type of algorithm experiences extremely rapid growth in its execution time.

Polynomial Efficiency: Polynomial efficiency refers to an algorithm or function that has a time complexity that can be represented by a polynomial equation. This means that the running time of the algorithm grows at a rate proportional to some power of the input size.

Input Size: Input size refers to the amount of data provided as input to an algorithm or program.

Decision Problem: A decision problem is a computational problem that requires a yes or no answer, such as determining whether a given number is prime.

Optimization Problem: An optimization problem involves finding the best solution among many possible solutions, often by maximizing or minimizing an objective function.

Decidable Problem: A decidable problem is a computational problem for which there exists an algorithm that can determine whether a given input has a specific property or satisfies a certain condition.

Halting Problem: The halting problem refers to the question of whether an arbitrary program will halt (terminate) or run forever when executed on some input.

Undecidable Problem: An undecidable problem is a computational problem for which no algorithm can determine whether a given input has a specific property or satisfies a certain condition.

Heuristics: providing a “good enough” solution when an actual solution is impractical or impossible

• Faster than brute force methods

• May not always find the optimal solution

• Based on educated guesses, common sense, expert knowledge

• Useful for complex problems when solutions are impractical

Brute force: systematically enumeration all possible candidates for a solution

• Simple to implement

• Always finds existing solutions

• Often inefficient in large problem sizes

Guaranteed optimal solution