MJ

UNIT 1

1.1 Definition of Algorithm

An algorithm is a procedure consisting of a clear set of instructions or steps designed to solve a particular problem or accomplish a specific task.

How algorithms work?

  1. Algorithms take input data in various formats, such as numbers, text, or images.

  2. The algorithm processes the input data through logical and mathematical operations, manipulating and transforming it as needed.

  3. After the processing, the algorithm produces an output, which could be a result, a decision, or some other meaningful information.

Example of an Algorithm

Linear Search Algorithm

Problem: Find if a specific item exists in a list.

Steps:

  1. Start

  2. Take the list and the item to search for as inputs

  3. Compare each item in the list with the target item

  4. If a match is found, return its position

  5. If the end of the list is reached without finding the item, return "Not Found."

  6. Stop

1.2 Measures of Efficiency

Algorithm efficiency relates to how many resources a computer needs to process an algorithm.

Two main measures for calculating algorithm efficiency:

  • Space complexity

  • Time complexity

Space Complexity

Refers to the amount of memory needed during execution, including:

  1. Memory required to hold the algorithm code

  2. Memory required for input data

  3. Memory required for output data

  4. Working space memory (local variables, stack space, etc.)

Formula: S(a)=c+v(i)

Where:

  • c is the fixed part

  • v(i) is the variable part dependent on the problem instance

Examples:

  • Constant Space (O(1)): Memory usage remains constant regardless of input size.

  • Linear Space (O(n)): Memory usage grows linearly with input size.

  • Quadratic Space (O(n^2)): Memory usage grows quadratically.

  • Logarithmic Space (O(log n)): Memory usage grows logarithmically.

  • Exponential Space (O(2^n)): Memory usage grows exponentially.

Time Complexity

Measures the total time required to execute an algorithm.

Examples:

  • Constant Time (O(1)): Execution time does not depend on input size.

  • Linear Time (O(n)): Execution time grows linearly.

  • Quadratic Time (O(n^2)): Execution time grows quadratically.

  • Logarithmic Time (O(log n)): Execution time grows logarithmically.

  • Exponential Time (O(2^n)): Execution time grows exponentially.

Unethical Code Practices

  • Infinite Loops: No termination condition.

  • Memory Leaks: Accumulating data without cleanup.

  • Unbounded Recursion: Recursion without base case.

  • Fork Bombs: Rapidly creating processes to crash systems.

  • Inefficient Algorithms: Using inefficient approaches for large datasets.

Solutions:

  1. Avoid infinite loops.

  2. Manage memory effectively.

  3. Use recursion carefully.

  4. Prevent denial-of-service attacks.

  5. Choose efficient algorithms.

1.3 Algorithms and Complexity Factors

Factors Affecting Algorithm Complexity:

  1. Programming Language: Impacts memory usage.

  2. Compiler/Interpreter: Affects how code is translated.

  3. Hardware Architecture: Influences execution speed.

  4. Code Optimization: Affects performance and memory efficiency.

1.4 Numerical Algorithms and Computational Complexity

Numerical Algorithms solve mathematical problems involving continuous data, including:

  • Solving equations

  • Finding roots

  • Calculating integrals

  • Approximation methods

  • Linear algebra operations

Computational Complexity studies the resources required to solve computational problems. Key concepts:

  • Time Complexity: Measures execution time.

  • Space Complexity: Measures memory usage.

  • Big O Notation: Describes algorithm efficiency.

  • Complexity Classes: Groups problems by difficulty (P, NP, etc.).

1.5 Numerical Algorithms and Numerical Accuracy

Challenges in Numerical Accuracy:

  • Rounding Errors: Due to limited precision.

  • Truncation Errors: Approximating infinite processes with finite steps.

  • Data Errors: Errors in input data affecting results.

Measures of Accuracy:

  • Absolute Error: Difference between computed and true values.

  • Relative Error: Absolute error divided by the true value.

  • Significant Digits: Reliable digits in a result.

Factors Affecting Accuracy:

  • Algorithm stability

  • Precision of arithmetic calculations

  • Sensitivity of input data (conditioning)

1.6 Types of Algorithm Analysis

  1. Time Complexity Analysis

    • Worst-case: Maximum execution time.

    • Average-case: Expected execution time.

    • Best-case: Minimum execution time.

  2. Space Complexity Analysis

    • Memory used as input size increases.

  3. Amortized Analysis

    • Evaluates cost over multiple operations.

  4. Empirical Analysis (Profiling)

    • Measures actual runtime and memory usage.

  5. Asymptotic Analysis

    • Evaluates growth rate as input size approaches infinity.

1.7 Bounds on Complexity and Models of Computation

Bounds on Complexity:

  • Upper Bound: Maximum resources needed.

  • Lower Bound: Minimum resources required.

Models of Computation:

  1. Sequential Models: Execute instructions linearly.

  2. Functional Models: Treat computation as function evaluation.

  3. Concurrent Models: Allow parallel execution.

Key Aspects of Models:

  • Define computation steps.

  • Manage memory allocation.

  • Handle communication between components.