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

This quiz explores the fundamental properties of algorithms and their role in the problem-solving process in programming. Learn to identify key algorithm characteristics such as finiteness and definiteness, and understand how these properties contribute to effective programming. Test your knowledge on how these concepts apply in practical scenarios.