Algorithm and Problem Solving Concepts

Algorithm and Properties of Algorithm

• An algorithm is a step-by-step problem-solving procedure, designed for implementation as a computer program.
• It's a finite, deterministic, and effective method, defining a sequence of well-defined statements.
• The algorithm is independent of the underlying programming language, allowing for diverse implementations.
• Key properties of algorithms:
  • Finiteness: The algorithm ends after a finite number of steps.
  • Definiteness: Each step is precisely defined, avoiding ambiguity.
  • Input: The algorithm accepts zero or more input quantities.
  • Output: The algorithm produces at least one output quantity.
  • Effectiveness: All operations are basic enough to be executed in finite time by humans using pen and paper.

Problem Solving Process

• Programming is a problem-solving process.
• This includes identifying the problem, determining data to manipulate, and defining expected results.
• Areas of focus in the problem-solving process:
  • Problem domain: Raw data (input) and processed data (output).
  • Machine domain: Storage medium (bits, bytes, words) and processing unit (arithmetic, comparison operations).
  • Solution domain: Links the problem and machine domains, focusing on data structures and algorithm synthesis.
• No set standards for writing algorithms, as it depends on the problem and resources.
• Common constructs like loops and flow controls are used in algorithm representation.

Mathematical Functions

• Mathematical functions are essential for algorithm creation and analysis.
• Floor function (⎿x⏌): Returns the greatest integer less than or equal to x.
• Ceiling function (⎾x⏋): Returns the smallest integer greater than or equal to x.
• Modulo function (x mod y): Returns the remainder when x is divided by y.
• Identities simplify analysis:
  • ⎾x⏋ = ⎿x⏌ if and only if x is an integer.
  • ⎾x⏋ =⎿x⏌ + 1 if and only if x is not an integer.
  • ⎣ - x ⎦ = -⎾x⏋
  • ⎣ x ⎦ + ⎣ y ⎦ 1

Big-Oh Notation

• Used to measure the complexity of algorithms.
• Categorizes time or space requirements based on the input size (n).
  • O(n) (Linear): Time or space requirement grows linearly with the input size.
  • O(n log2n): Time requirement grows slightly faster than linear due to logarithmic operations.
  • O(n2) (Quadratic): Time requirement grows quadratically with the input size.
  • O(n3) (Cubic): Time requirement grows cubically with the input size.
  • O(2n) (Exponential): Time requirement grows exponentially with the input size - very inefficient for large inputs.
  • Constant time complexity: The algorithm's execution takes the same amount of time regardless of the input size.

Complexity Examples

• O(n) (Linear): Sequential search takes a linear amount of time to find a specific element in a list.
• O(n log2n): Heap sort combines comparisons and sorting steps, leading to a slightly faster than linear time complexity.
• O(n2): Insertion sort compares every element to all other elements, resulting in a quadratic time complexity.
• O(n3): Floyd's algorithm for finding shortest paths takes a cubic amount of time to compute the results.
• O(2n) (Exponential): Rarely implemented because for large datasets, the time required for execution becomes practically impossible.

Operations on the O-Notation:

• Rule for Sums: If T 1(n) is O(f(n)) and T 2(n) is O(g(n)), then T 1(n) + T 2(n) is O(max(f(n), g(n))).
• Rule for Multiplication: If T 1(n) is O(f(n)) and T 2(n) is O(g(n)), then T 1(n) * T 2(n) is O(f(n) * g(n)).
• Rule for Dominance: If f(n) is asymptotically larger than g(n), then O(f(n) + g(n)) is O(f(n)).