Algorithms and Pseudocode

Algorithms

• An algorithm comprises a finite sequence of well-defined steps to perform specific tasks.
• Each step in an algorithm is a clear instruction that can be completed in a finite time.
• The order of steps is clear, and the process is guaranteed to stop after a finite number of steps.
• An algorithm provides a sequence of steps that leads to the desired answer when presented with a problem.
• To find the least number in the set {3, 5, 6, 1, 2, 7}, compare each number from the previous and choose which is less, and repeat.
• The least number in the set {3, 5, 6, 1, 2, 7} is 1.

Pseudocode

• Algorithms are associated with computer language.
• Pseudocode generalizes the algorithm, and overcomes the limitations of using a specific programming language.
• Pseudocode provides an intermediate step between an English description and its translation to a computer language.
• To find the minimum value in a finite sequence using pseudocode:
  • Set min to the first integer.
  • For each subsequent integer, if it is less than min, update min.
  • Return min as the smallest element.

Flowcharts

• Flowcharts illustrate algorithms to aid in program visualization.
• Flowcharts are read from top to bottom and left to right.
• Start/Stop symbol represents the beginning and end of the code.
• Process symbol represents an instruction to be carried out.
• Decision symbol is used to split into multiple paths, selection and repetition.
• Input/Output symbol represents data entry by a user or data display by the program.
• Arrows indicate the flow of the algorithm.

Properties of Algorithms

• Input refers to the input values from a specified set.
• Output refers to the output values from a specified set, representing the solution.
• Definiteness means the steps must be defined precisely.
• Correctness means the algorithm produces the correct output values.
• Finiteness means the algorithm stops after a finite number of steps.
• Effectiveness means each step can be performed exactly in a finite amount of time.
• Generality means the procedure applies to all problems of the desired form.

Control Structures

• Control structures instruct the algorithm on what commands to execute, when, and how.
• Conditional controls set conditions for algorithm step execution using "if".
• If-then executes a command if a condition is true.
  • For example, setting Output to "Passed" if student score x ≥ 60.
• If-then-else executes one command if a condition is true, and another if false.
  • For example, Output "Passed" if student score x ≥ 60, else Output "Failed".

Loop Controls

• Loop controls dictate how many times a step will be executed.
• A for-do loop repeats a step for a specified number of times.
  • Input the number of elements in the set, n.
  • Input the elements x1, x2, …, xn.
  • Set min  x1
  • i2
  • For i =2 to n do
    • If xi < min then
      • min  xi
    • ii+1
  • Output min.
• A while-do loop repeats a step as long as a condition is true.
  • Find the order of the factor two for a given integer n (n = 2order)
  • Input a positive integer n
  • order  0
  • While n is even do
    • n  n/2
    • order  order + 1
  • Output order.
• A repeat-until loop repeats a step until a condition is true.
  • List all integers from n to 1.
  • Input a positive integer n
  • i  n
  • Repeat until i = 0
    • Output i
    • i  i – 1

Tracing an Algorithm

• Tracing involves going through the algorithm's steps to generate a result.
• Tracing begins with an input, follow each step until the algorithm ends.
• Tracing tests the algorithm's consistency and to spot errors.
• Trace tables include the steps, inputs, variables, and output.