Introduction to Algorithms

Overview

An algorithm is a step-by-step set of instructions designed to perform a task or solve a problem. In Computer Science, algorithms are crucial for automating processes, solving complex problems efficiently, and improving program performance. Understanding how to design, analyse, and implement algorithms is a core skill.

Algorithm Design

• Purpose: To solve a specific problem efficiently and logically.
• Approach:
  • Understand the problem: Break it down into smaller components.
  • Choose an approach: This could be iterative, recursive, or a combination.
  • Design steps: Outline a clear sequence of operations to achieve the goal.

Algorithm Representation

Algorithms can be represented in various forms, such as:

Flowcharts:

A visual representation of an algorithm using symbols such as:

• Oval: Start/End
• Rectangle: Process (e.g., calculations)
• Diamond: Decision (e.g., IF statements)
• Arrow: Flow of control

[Start] --> [Input x] --> [Is x > 10?] -- Yes --> [Print "x is large"] --> [End]
                              |
                             No
                              |
                           [Print "x is small"] --> [End]

Pseudocode:

A high-level, structured, human-readable description of an algorithm.

BEGIN
   INPUT x
   IF x > 10 THEN
      OUTPUT "x is large"
   ELSE
      OUTPUT "x is small"
   ENDIF
END

Program Code:

Written in a specific programming language (e.g., Python). While you are not expected to write perfect syntax, you must demonstrate logical structures.

x = int(input("Enter a number: "))
if x > 10:
    print("x is large")
else:
    print("x is small")

Analysing Algorithms

• Efficiency: How well an algorithm performs regarding time (speed) and space (memory).
• Correctness: Ensures the algorithm provides the expected result for all valid inputs.

Algorithm Structures and Techniques

• Iteration (Loops): Repeating steps (e.g., FOR, WHILE loops).
• Selection (Decision-Making): Using conditions (e.g., IF, ELSE statements).
• Variables and Data Input/Output: Handling user input and displaying results.

Examples

BEGIN
   largest ← list[0]
   FOR each number in list
      IF number > largest THEN
         largest ← number
      ENDIF
   ENDFOR
   OUTPUT largest
END

BEGIN
   factorial ← 1
   FOR i ← 1 TO n
      factorial ← factorial * i
   ENDFOR
   OUTPUT factorial
END

Note Summary