Definitions

Question 1

Sedgewick (2011): Algorithm

Answer 1

The term algorithm is used in computer science to describe
methods for solving problems that are suited for computer
implementation.

Question 2

Aho, Hopcroft & Ulman (1975): Algorithm

Answer 2

An algorithm is a finite sequence of instructions, each of which
has a clear meaning and can be performed with a finite
amount of effort in a finite length of time.

Question 3

Levitin (2003): Algorithm

Answer 3

An algorithm is a finite sequence of an ambiguous instructions for solving a problem, i.e, for obtaining the required output for any legitimate input in a finite amount of time.

Question 4

Iterative Algorithm

Answer 4

Iteration is the repetition of a process in order to generate a sequence of outcomes. The sequence will approach some endpoint or end value. Each repetition of the process is a single iteration, and the outcome of each iteration is then the starting point of the next iteration.

Question 5

Direct Recursion Algorithm

Answer 5

If a function calls itself, it’s known as direct recursion.

Question 6

Indirect Recursion Algorithm

Answer 6

Indirect recursion occurs when a function is called not by itself but by another function that it called (either directly or indirectly). For example, if f calls f, that is direct recursion, but if f calls g which calls f, then that is indirect recursion of f.

Question 7

Divide and Conquer Algorithm

Answer 7

Divide and conquer is an algorithm design paradigm based on multi-branched recursion. A divide-and-conquer algorithm works by recursively breaking down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved directly.

Question 8

Dynamic Programming Algorithms

Answer 8

Like divide-and-conquer method, Dynamic Programming solves problems by combining the solutions of subproblems. Moreover, Dynamic Programming algorithm solves each sub-problem just once and then saves its answer in a table, thereby avoiding the work of re-computing the answer every time.

Question 9

Randomised Algorithms

Answer 9

An algorithm that uses random numbers to decide what to do next anywhere in its logic is called Randomised Algorithm.

Question 10

Brute Force Algorithms

Answer 10

Brute Force Algorithms refer to a programming style that does not include any shortcuts to improve performance, but instead relies on sheer computing power to try all possibilities until the solution to a problem is found.

Question 11

Euclid’s Algorithm for GCD

Answer 11

• Step 1: If n = 0, return the value of m as the answer and stop; otherwise, proceed to step 2.
• Step 2: Divide m by n and assign the value of the remainder to r.
• Step 3: Assign the value of n to m and the value of r to n. Go to step 1.

Question 12

cₒₚ

Answer 12

The cost (time) to execute an algorithm’s basic operation on some computer

Question 13

C(n)

Answer 13

The number of times the operation needs to be executed

Question 14

~1: Constant time

Answer 14

Normally the amount of time that a instruction takes under the RAM model

Question 15

~log n: Logarithmic

Answer 15

It normally occurs in algorithms that transform a bigger problem into a smaller version that whose input size is a ration of the original problem. Common in searching and in some tree algorithms.

Question 16

~n: Linear

Answer 16

Algorithms that are forced to pass through all elements of the input (of size n) a number (constant) of times yield linear running time.

Question 17

~nᵏlog n: Polylogarithmic

Answer 17

Typical of algorithms that break the problem into
smaller parts, solve the problem for the smaller parts and combine the solution to obtain the solution of the original problem instance. k >= 1

Question 18

n²: Quadratic

Answer 18

A subset of the polynomial solutions. Quadratic solutions are still acceptable and are relatively efficient to small to medium scale problem sizes. Typical of algorithms that have to analyse all pairs of elements of the input.

Question 19

n³: Cubic

Answer 19

Not very efficient but still polynomial. A classical example of algorithms in this class is the matrix multiplication.

Question 20

2ⁿ: Exponential

Answer 20

Unfortunately quite a few known solutions to practical problems are in this category. This is as bad as testing all possible answers to a problem. When algorithms fall in this category, algorithm designers go in search of approximation algorithms.

Question 21

C(n) = n: Worst

Answer 21

The worst-case efficiency of an algorithm is its efficiency for the worst-case input of size n, which is an input (or inputs) of size n for which the algorithm runs the longest among all possible inputs of that size.

Question 22

C(n): Best

Answer 22

The best-case efficiency of an algorithm is its efficiency for the best-case input of size n, which is an input (or
inputs) of size n for which the algorithm runs the fastest among all the inputs of that size.

Question 23

RAM model

Answer 23

Used for counting the number of steps to calculate the time complexity of an algorithm.

Question 24

O(g(n)): Notation

Answer 24

A function t(n) is said to be in the O(g(n)), denoted by t(n) = O(g(n)), if there exist some positive constant c and some nonnegative integer n0. t(n) ≤ cg(n), ∀n ≥ n0

Question 25

o(g(n)): Notation

Answer 25

t(n) < cg(n), ∀n ≥ n0: Strict O Notation

Question 26

Ω(g(n)): Notation

Answer 26

t(n) ≥ cg(n), ∀n ≥ n0

Question 27

ω(g(n)): Notation

Answer 27

t(n) > cg(n), ∀n ≥ n0: Strict Ω Notation

Question 28

Θ(g(n)): Notation

Answer 28

c1 g(n) ≤ t(n) ≤ c2 g(n), ∀n ≥ n0

Question 29

Transitivity

Answer 29

The relation between three elements such that if it holds between the first and second and it also holds between the second and third it must necessarily hold between the first and third.

Question 30

Reflexivity

Answer 30

A function is always a lower and upper bound of itself but never a strict lower or upper bound.

Question 31

Symmetry

Answer 31

f(n) = Θ(g(n)) if and only if g(n) = Θ(f(n))

Question 32

Transpose Symmetry

Answer 32

f(n) = O(g(n)) if and only if g(n) = Ω(f(n)),
f(n) = o(g(n)) if and only if g(n) = ω(f(n))

Question 33

Recursive Method

Answer 33

The ability to “transform” a problem into one or more smaller instances of the same problem. Then solving these instances to find a solution to the large problem.

Question 34

Linear Data structure

Answer 34

• There is a unique first element
• There is a unique last element
• Every component has a unique predecessor (except the first)
• Every component has a unique successor (except the last)