Algorithms: Definitions, Properties, and Representations

Introduction to Algorithms

• Algorithms are a fundamental topic in mathematics and computer science.
• An algorithm is defined as a set of ordered instructions designed to solve a specific problem.
• Algorithms consist of instructions that can be in the form of code or written steps, such as recipes or instruction manuals.
• The end result of an algorithm is the solution to the problem.

Examples of Algorithms

• YouTube's Related Videos: An algorithm suggests related videos based on viewing history and interests.
• Google Search: Algorithms are used to display search results based on relevance.
• These algorithms share common characteristics: ordered instructions and problem-solving capabilities.
• Algorithms are often likened to functions in code, which provide a specific output or complete a task.

Key Characteristics of Algorithms

• Algorithms possess three key characteristics:
  • Precision
  • Well-defined
  • Finiteness

Precision

• Precision refers to the accuracy of an algorithm in solving a problem.
• An algorithm should provide accurate answers and effectively solve the problem it is designed for.
• Efficiency, particularly time efficiency, is crucial.
• Time efficiency means the algorithm should execute quickly.
• It's a practical tradeoff between precision and time. Sometimes, slightly less precise results are acceptable if the algorithm runs faster.
• Example: An algorithm in a satnav should find the quickest route in a reasonable time (e.g., a minute), not an excessively long time (e.g., a day).
• Another example: Google search results should be displayed quickly (e.g., in half a second) even if more precise results would take longer to retrieve (e.g., 10 minutes).

Well-Defined

• Well-defined algorithms have specific inputs and outputs.
• Input and output are often denoted as I/O.
• Example:
  • Inputs: 2 and 8; Output: 16. The algorithm multiplies the inputs together: 2 \times 8 = 16.
• More complex example:
  • Input: 16; Outputs: 4 and -4. The algorithm calculates the square root of 16.
  • \sqrt{16} = \pm 4 because (4 \times 4 = 16) and (-4 \times -4 = 16).
• Algorithms can have multiple inputs with one output, or even no inputs (null input) with an output (e.g., a random number generator).

Finiteness

• Finiteness means that an algorithm should not run indefinitely.
• The algorithm must have a defined stopping point.
• If an algorithm cannot find an answer, it should terminate rather than running forever, which would cause a runtime error.

Representing Algorithms

• Algorithms are typically executed by computers but can be represented in two main ways:
  • Pseudo code
  • Flow diagrams (or flowcharts)

Pseudo Code

• Pseudo code is a high-level, informal description of code.
• It is written primarily in English, making it easy for humans to read and understand.
• Pseudo code is not executed by computers; it is used for planning and design.
• It's useful for planning control assessments and expressing algorithms in exams.
• Example of pseudo code for adding values in a list:
  list = [1, 2, 3, 4, 5] total = 0 for each number in list: total = total + number end for print total
• The equivalent Python code would be:
  python list = [1, 2, 3, 4, 5] total = 0 for number in list: total += number print(total)
• Pseudo code conventions may vary, but it should be easily readable and interpretable.
• Assignment of variables or lists can be done using an arrow (e.g., list <- [1, 2, 3]) or an equals sign.
• Loop and function endings can be marked with end for or similar notations.

Flow Diagrams

• Flow diagrams are pictorial representations of code.
• They provide a visual version of pseudo code.
• Flow diagrams may be less detailed but can be easier for some people to use.
• Flow diagrams consist of different blocks representing steps in the algorithm.
  • Start block: Denotes the start of the program (one output, no inputs).
  • Process block: Represents an operation carried out by the algorithm (one input, one output).
  • Decision block: Represents a Boolean choice (one input, two outputs).
  • End block: Denotes the end of the program (one input, no outputs).
• Key concepts often represented in flow diagrams are:
  • Sequence
  • Selection
  • Iteration

Summary

• This lecture provided an introduction to algorithms.
• Algorithms are defined as ordered instructions that solve a problem.
• Key characteristics of algorithms include precision, being well-defined, and finiteness.
• Algorithms can be represented using pseudo code or flow diagrams for planning and communication.