Introduction to Algorithms

Module 1: Introduction to Algorithms

• An algorithm consists of unambiguous instructions used for finding solutions to a problem in a finite amount of time for any legitimate input. Algorithms must be concise
• An algorithm must satisfy the following criteria:

Algorithm Criteria

• Input: Zero or more quantities are externally supplied.

• Output: At least one quantity is produced. An algorithm can generate one or more outputs

• Definiteness: Each instruction must be clear and unambiguous.

• Finiteness: The algorithm terminates after a finite number of steps when tracing algorithm instructions for all valid cases; all operations must be finite.

• Effectiveness: Each instruction must be basic enough to be carried out by a person using only a pencil and paper; operations must be more than definite, they must be feasible and convenient.

• Algorithms that are definite and effective are "Computational Procedures".

• The diagrammatic representation of an algorithm illustrates the motion of the algorithm by using input being fed into a "computer" to generate an output

Important Points/Properties:

• The unambiguity requirement for each step of an algorithm cannot be compromised.
• The range of inputs for which an algorithm works needs to be specified carefully.
• The same algorithm can be represented in other ways.
• Several algorithms can solve the same problem.
• Algorithms for the same problem can be based on different ideas and solve the problem with varying speeds.

Fundamentals of Algorithmic Problem Solving

• Designing and analyzing an algorithm typically requires a sequence of steps:
  • Understand the problem
  • Decide on:
    • Computational means
    • Exact vs approximate solving
    • Algorithm design technique
  • Design an algorithm
  • Prove correctness
  • Analyze the algorithm
  • Code the algorithm
• Algorithms can be procedural solutions to problems.

Steps for Problem Solving:

• Step 1: Understanding the Problem

  • Fully understand the problem before designing an algorithm. Carefully read the problem's description
  • Do small examples by hand or consider special cases.
  • It is important to specify the set of instances an algorithm needs to handle; otherwise, the algorithm may work for a majority of inputs but crash on a "boundary" value.
  • A correct algorithm works correctly for all legitimate inputs.

• Step 2: Decide on Computational Means

  • Ascertain the capabilities of the computational device. The vast majority of algorithms in use today are designed to be programmed for a computer closely resembling the Von Neumann machine.
  • The essence of this architecture is random-access memory (RAM).
  • The central assumption is that instructions are executed one after another, one operation at a time. Thus, algorithms designed to be executed on such machines are called sequential algorithms.
  • The RAM model's central assumption does not hold for newer computers that can execute operations concurrently(parallel); algorithms that do take advantage of this (parallel processing) are called parallel algorithms.
  • The speed and memory available on a particular computer system are other factors to consider.

• Step 3: Exact vs. Approximate Problem Solving

  • Choice to solve the problem approximately or exactly
  • Algorithms that solve problems exactly are called exact algorithms.
  • Algorithms which solve the problem approximately are called approximate algorithms.

• Why Opt for Approximation Algorithms?

  • Some important problems simply cannot be solved exactly for most of their instances, such as extracting square roots, solving non-linear equations, and evaluating definite integrals
  • Available exact algorithms are unacceptably slow due to the problem's intrinsic complexity.
  • An approximation algorithm can be a part of a more sophisticated algorithm that solves a problem exactly.

• Step 4: Types of Algorithm Design Techniques

  • An algorithm design technique (or "strategy" or "paradigm") is a general approach applicable to a variety of problems from different computing areas.
    • Designing algorithms solve a specific problem.
    • Algorithm design techniques make it possible to classify algorithms according to an underlying design idea.
    • Design techniques can categorize and study algorithms.

• Step 5: Design an Algorithm and Data Structures

  • Designing an algorithm for a problem can be challenging. Some design techniques can be simply inapplicable. Several techniques may need to be combined.
    • Properly choosing data structures for operations is important.
    • Algorithms + Data Structures = Programs.
    • Data structures remain important for design and analysis of algorithms in object-oriented programming.

• Step 6: Method of Specifying an Algorithm

  • The algorithm should be specified in some fashion once is designed
  • Widely used options are Pseudocode & Flowcharts.
    • Pseudocode is a mixture of a natural language and programming language-like constructs.
    • Pseudocode is a step-by-step description of an algorithm.
    • Pseudocode is the intermediate state between an idea and its implementation (code).
    • A flowchart shows an algorithm by connecting geometric shapes containing descriptions of algorithm steps.
    • A flowchart illustrates the algorithm.

• Step 7: Proving Correctness

  • Prove an algorithm's correctness once specified by proving/yielding the required result for any legitimate input in a finite amount of time.

• Step 8: Coding an Algorithm

  • An algorithm has to be implemented as a computer program
    • Programming an algorithm presents both peril and opportunity
    • Code optimization may improve running time.

Fundamentals of the Analysis of Algorithm Efficiency

• Analysis Framework

  • Algorithms can be analyzed within this framework
    • Means of measuring
      • Space complexity
      • Input size
      • Time/Running time
    • Compute complexities

• Efficiency is measured in time or space

• Checking whether an algorithm is efficient involves a systematic approach that is modeled as an analysis framework.

• Algorithm efficiency can be decided by measuring performance.

Measuring Algorithm Performance

• Measure performance by computing two factors:
  • Amount of time required by an algorithm to execute (time complexity, running time, time efficiency)
  • Amount of storage required (space complexity, memory space, space efficiency) These can be used to select an algorithm -Selecting can algorithm is based on:
  • Simplicity
  • Generality
  • Speed
  • Memory

Memory/Space Complexity

• The amount of memory required by an algorithm to run is space complexity.
• Use constant and instance characteristics to compute space complexity.
• Space requirement s(P) can be given with the equation S(P) = C + Sp. - C is a constant (fixed part) and denotes space taken by inputs, outputs, instructions, variables, and identifiers. - Sp is space dependent upon instance characteristics (variable part), where space requirement depends on the particular problem instance, like control statements or Recursion Slack

Time Complexity

• Amount of time required by an algorithm to run Completion is "Time Complexity".

• Time complexity cannot be computed with physically clocked time

• Multiuser system execution depends on factors like:

  • System load
  • Number of other programs running
  • Instruction set used
  • Speed of underlying hardware

• Time complexity is given in terms of frequency count.

• The frequency count denotes how many times a particular statement is executed-a count denoting the number of times of execution. Examples can be listed

Measuring an Input Size

• Efficiency of an algorithm is directly proportional to the input size or range; algorithms can be measured as a function of n, where n indicates the input size. - When multiplying two matrices, the efficiency of an algorithm depends on the number of multiplications performed, not on the order of matrices. - Also, the input given could be a square or a non-square matrix

• The amount of bits indicated the size - Some algorithms require more than one parameter to indicate the size of their ilp; - Size is measured by the number of bits in the n's binary representation: B = floor(log₂n+1).

• Algorithms run longer on longer inputs, such as sorting naive algorithms (- n²) or Best algorithm (- nlogn)