Algorithms T1 Design of Algorithms

OCR A Level Computer Science - Analysis and Design of Algorithms

Unit Overview

• Focus: Analysis and design of algorithms

• Paper: H446 - Paper 2

• Teaching and learning tool from OCR

Starter Problem: Security Door Code

• Problem: Security door at a football ground has the code 1966. Any combination of these numbers can open the door.

• Question: How many different combinations exist?

• Answer: Calculate using permutations: 4!/2! = 12.

Starter Problem: Prime Number Sum

• Problem: In how many different ways can 2017 be expressed as the sum of two prime numbers?

• Answer: 0 possibilities. Since 2017 is odd, it cannot be the sum of two odd primes. The only even prime is 2 which does not yield a valid prime pair (2017 = 2 + 2015, but 2015 is not prime).

Objectives of the Unit

• Analyze the suitability of algorithms for different tasks and datasets.

• Familiarize with measures for determining algorithm efficiency.

• Define constants, linear, polynomial, exponential, and logarithmic functions.

• Utilize Big-O notation for comparing time complexities of algorithms.

• Derive and articulate the time complexity of algorithms.

Keywords

• Algorithm

• Complexity

• Big-O Notation

• Efficiency

• Permutation

• Linear, Logarithmic, Polynomial, Exponential Functions

What is an Algorithm?

• Definition: A step-by-step procedure for calculations, data processing, and automated reasoning tasks.

• Examples: Algorithms used to solve numerous real-world problems. Some problems remain unsolved today.

Problems Solved by Algorithms

1. Routing Problems: Shortest routes for data on the internet.

2. Salesman Problems: Efficient route coverage for salesmen.

3. Aircraft Timetabling: Manage crew flight hours effectively.

4. Information Retrieval: Searching databases efficiently.

5. Security: Encrypting communications to prevent hacking.

6. Data Sorting: Organizing large datasets.

7. Compiler Design: Translating high-level languages to machine code.

Properties of a Good Algorithm

• Clear, precise steps yielding correct output for valid inputs.

• Ability to handle invalid inputs gracefully.

• Must terminate at some point.

• Efficient execution using minimal steps.

• Clear enough for others to understand and modify.

Efficiency of Algorithms

• Example Algorithm: Sum from 1 to 1000 using two different methods:

  • Method 1: Iterative summation (inefficient, 1001 statements).

  • Method 2: Mathematical formula (efficient, only 2 statements).

• Importance of minimizing assignment statements as a measure of efficiency.

Execution Time vs Problem Size

• Generally, larger data sizes increase execution time.

• Analyze statements involved in processing n items (conventional loop vs formulaic approach).

Functions in Mathematics

• Definition: A function is represented by equations (e.g., y = mx + b).

• General Form: f(n) = an + b.

Types of Functions

Linear Functions

• Form: f(n) = an + b (e.g., f(n) = 3n).

• Growth in a straight line; time complexity: O(n).

Quadratic Functions

• Form: f(n) = an² + bn + c.

• Dominant term is n²; complexity: O(n²).

Logarithmic Functions

• Form: f(n) = a log₂(n).

• Grows slowly compared to linear; time complexity: O(log n).

Big-O Notation

• Purpose: Describes time complexity and approximates execution time relative to the number of items in datasets.

• Examples:

  • O(1): Constant complexity.

  • O(log n): Efficient with large datasets.

  • O(n): Linear complexity.

  • O(n²): Polynomial complexity, inefficient for large datasets.

  • O(2ⁿ): Exponential complexity, extremely inefficient.

Analyzing Algorithms

• Approach: Count the number of steps (assignment statements) in computations to derive time complexity.

• Dominant terms are crucial when evaluating algorithm efficiency (e.g., O(n²)).

Permutations

• Definition: Arrangement of n items in different orders; can have repetition.

• Types:

  • With repetition (e.g., 100 combinations in a 2-digit lock).

  • Without repetition (3! arrangements of 3 differently colored balls).

Summary of Time Complexities

• Utilize visual aids or charts for easier comparison between complexities.

Final Plenary

• Key points:

  • Big-O notation evaluates the growth rate of runtime as problem size increases.

  • O(n!) and O(2ⁿ) are inefficient for large n.

  • O(log n) is very efficient, with limited impact on computation time as n increases.