Fundamentals of algorithms

What is an Algorithm?

Before we start talking about algorithms, we should try to figure out what an algorithm actually is. We could, for example, have a short look at how others define an algorithm:

Several definitions found in the WWW:

Browsing the web, we can find quite a number definitions of the term "algorithm". Here's a small collection of them.

Definition 1:

"An algorithm is a computable set of steps to achieve a desired result." - (found on numerous websites)

Definition 2:

An algorithm is a set of rules that specify the order and kind of arithmetic operations that are used on specified set of data.

Definition 3:

An algorithm is a sequence of finite number of steps arranged in a specific logical order which, when executed, will produce a correct solution for a specific problem. - (taken from an undergraduate course at UMBC).

Definition 4:

An algorithm is a set of instructions for solving a problem. When the instructions are followed, it must eventually stop with an answer. - (given by Prof. Carol Wolf in a course on algorithms).

Definition 5:

An algorithm is a finite, definite, effective procedure, with some output. - (given by Donald Knuth)

Essential properties of an algorithm

Though the given definitions differ slightly, we can clearly extract the essential properties an algorithm should have:

    * an algorithm is finite (w.r.t.: set of instructions, use of resources, time of computation)
  • * instructions are precise and computable.
  • * instructions have a specified logical order, however, we can discriminate between
  • - - deterministic algorithms (every step has a well-defined successor), and
  • - - non-deterministic algorithms (randomized algorithms, but also parallel algorithms!)
  • * produce a result.

Basic questions about algorithms:
For each algorithm, especially a new one, we should ask the following basic questions:

  • * does it terminate?
    * is it correct?
    * is the result of the algorithm determined?
    * how much memory will it use?

 

3.1 Fundamentals of algorithms

3.2 Programming

3.3 Fundamentals of data representation

3.4 Computer systems

3.5 Fundamentals of computer networks

3.6 Fundamentals of cyber security

3.7 Ethical, legal and environmental impacts of digital technology on wider society, including issues of privacy

3.8 Aspects of software development

Glossary and other links

Glossary of computing terms.

AQA 8520: The 2016 syllabus