Design and Analysis algorithms(lecture-2) DAA

Unit 1: Introduction to Algorithms 

Lecture 1: Introduction to Algorithm – Definition, Characteristics, and Properties

Algorithm +Data structure = Programming

• Algorithms – An algorithm is a step-by-step procedure or set of rules to be followed in calculations or problem-solving operations. Algorithms are fundamental in computer science, as they form the basis of programs and software. They can be described in various forms, such as natural language, pseudocode, flowcharts, or actual programming languages.
  

  Key Characteristics of an Algorithm:

  1. Input: An algorithm has zero or more inputs.
  2. Output: It must produce at least one output.
  3. Definiteness: Each step of the algorithm must be clearly defined and unambiguous.
  4. Finiteness: The algorithm should terminate after a finite number of steps.
  5. Effectiveness: The operations in the algorithm should be basic enough to be carried out, in principle, by a human using only paper and pencil.

  Example: Finding the Maximum of Two Numbers

  Let’s look at an example algorithm to find the maximum of two numbers:

  Problem:

  Given two numbers, a and b, find the maximum of the two.

  Algorithm (in pseudocode):

  1. Start
  2. Read values for a and b
  3. If a > b, then:
     • Print a is the maximum
  4. Else:
     • Print b is the maximum
  5. Stop

  Explanation:

  • Input: Two numbers a and b.
  • Output: The maximum number between the two.
  • Definiteness: The steps are clearly defined, as the algorithm checks the condition a > b.
  • Finiteness: The algorithm will terminate after either printing a or b.
  • Effectiveness: The comparison a > b is a basic operation that can be easily performed.

  Example Execution:

  Suppose the input values are a = 5 and b = 7.

  • Step 1: Start
  • Step 2: Read values for a and b (a = 5, b = 7)
  • Step 3: Check if a > b (5 > 7). This is false.
  • Step 4: Since the condition is false, go to the else part and print b is the maximum.
  • Step 5: Stop

  So, the output will be 7 is the maximum.