Day #1 - Algorithms and their Analysis

In Class Lesson:

• Algorithm - A finite, well-defined sequence of Operations to solve a problem

• Input - A sequence of n numbers/elements <a₁, a₂, …, a_n>

• Output - A permutation (reordering) <a’₁, a’₂, …, a’_n>of the input sequence such that a’₁<= a’₂<= <= a’_n

Problem Types:

• Decision: Problem where the answer is either "yes" or "no", T/F, Boolean

  • Example: Is there a path from point A to point B in this maze?" The answer can be either "yes" or "no."

• Search: Problem where you find a specific item or solution within a larger set of data as long as it meets certain criteria, any solution that satisfies the criteria will do.

  • Example: The basket contains apples, oranges, bananas, and grapes. You want to find a fruit that is orange in color. You can pick any fruit that is orange. If there is more than one orange fruit, any of them will satisfy the criteria.

• Optimization: Problem where you find the best solution based on min/max parameter constraint such as cost, time, or efficiency

  • Example: You need to deliver packages to several locations in the shortest possible time. In this case, the optimization problem is to find the best route that allows you to deliver all the packages in the shortest possible time while meeting the constraints.

Sorting Problem:

• Instance of a Problem: Consists of the input that follows the rules or constraints given in the problem needed to find the solution to the problem

  • I: <3,1,2> O: <1,2,3>

  • I <2₁,4₁,2₂,4₂> O: <2₁,2₂,4₁,4₂>(Stable) OR <2₂,2₁,4₂,4₁>(Unstable)

    • Stable Sort: Keeps the relative order of equal elements

    • Unstable Sort: Does not guarantee the relative order of equal elements

A Correct Algorithm:

• An algorithm is correct IFF (if and only if) an algorithm has two properties:

  • Halts: The algorithm eventually stops running/non-infinite

  • Maps all problem instances to valid outputs: For every input, the algorithm produces a correct and valid output

  

• To find the sum of all numbers from i/1 to n being any positive number

  • If n=5n = 5, then you're summing 1 + 2 + 3 + 4 + 5.

    

• Basis Step/Base Case: Initial step in a proof by induction. It’s where you show that a statement is true for the very first value in the sequence you're considering, usually when n=1

  • Is the foundation of the proof. If the formula doesn’t hold for the smallest value of n, then the entire claim could be false

• Inductive Hypothesis: assumption that the formula or statement you’re trying to prove is true for some arbitrary positive integer k

• Inductive Step (I.S.): Where you show that the formula or statement is true for k, then it must also be true for k +1

• Example: Imagine you have a staircase with an unknown number of steps, but you want to prove you can climb it using a specific pattern: taking 1 step at a time

  • Basis Step: You can climb 1 step to show the pattern is possible

  • Inductive Hypothesis: Assume you can climb k steps one at a time

  • Inductive Step: Prove that you can climb k+1 steps by taking one more step after k steps.

• Loop Invariant: property or condition that holds true during every iteration of a loop, It's used to reason about the correctness of algorithms and to prove that loops behave as expected

  • Initialization: Before the loop begins, the invariant must be true.

  • Maintenance: If the invariant is true before an iteration of the loop, it must remain true after the iteration.

  • Termination: When the loop exits, the invariant can help demonstrate that the algorithm achieved its desired result.

ICE Questions:

Why does SELECTION-SORT only need to operate on the first n-1 elements and not all n elements?

• By the time you have sorted the first n−1 elements, the last element will naturally be in its correct position.

What’s the worst case (asymptotic) runtime for SELECTION-SORT? Is the best case runtime any different? why or why not

• The worst-case and best-case asymptotic runtimes for SELECTION-SORT are both O(n²) because the algorithm performs a fixed number of comparisons regardless of the initial order of the elements.