2.3 - Algorithms

Question 1

Define an Algorithm

Answer 1

A set of steps must be followed, one after each other to solve a problem.

Question 2

What are the 3 main components of an algorithm?

Answer 2

1. Input
2. Process
3. Output

Question 3

What are the qualitites of a good algorithm?

Answer 3

• has clear + precisly stated steps that produce the correct output for any set of valid inputs.
• allows for invalid inputs.
• must always terminate at soome point.
• should execute efficiently in as few steps as possible.
• designed so other people can understand + modify if necessary.

Question 4

Define a statement

Answer 4

A single line of instruction in code.

Question 5

Define efficiency

Answer 5

No. of assignment statements. Less lines = more efficient + less memory storage is used. Instructions proceed quicker.

Question 6

What can cause execution time to be longer?

Answer 6

If the promblem size is bigger or there is a larger amount of data.

Question 7

What is the equation for a linear function?

Answer 7

f(n) = an +b
a + b are constants
e.g. f(n) = 3n, f(n) = n + 5, f(n) = 6n + 1

Question 8

What is the equation for a constant function?

Answer 8

f(1)
e.g f(2), f(100)

Question 9

Define a constant function.

Answer 9

No matter how large n gets, f(1) stays the same.

Question 10

What is the order of magnitde for a linear function?

Answer 10

O(n)

Question 11

Define a linear function.

Answer 11

Everything increases in a straight line

Question 12

What is the equation for a quadratic function?

Answer 12

f(n) = an∧(2) + bn + c

Question 13

Define a quadratic function.

Answer 13

As n increases, the n∧(2) term increases much faster than either of the other terms.

Question 14

What is a stack?

Answer 14

A stack is an abstract data type that serves as a collection of elements. An example of FILO. (Try to imagine FILO with books.)

Question 15

What is the order of magnitude for a quadratic function?

Answer 15

O(n∧2)

Question 16

What is a queue

Answer 16

A queue is an abstract data type (ADT) is a logical description of how we view the data and possible operations, that holds an ordered. It is an example of FIFO. Often represented as an array.

Question 17

What is the dominent term?

Answer 17

The term that grows the fastest.
e.g n² grows faster than n, so if we have g(n) = n² + 5n + 6, it will be big O(n²).

Question 18

What is the equation for a logarithmic function?

Answer 18

f(n) = alog∨(2)n
e.g. log∨(2)16 = log∨(2)2∧(4)

Question 19

Define a logarithmic function.

Answer 19

the logarithm of a number of a number is the power to which the base must be rasied to make it equal to the number. f(n) increases very slowly in relation to n.

Question 20

What is the order of magnitude for a logarithmic function?

Answer 20

O(log n)

Question 21

What is Big-O notation?

Answer 21

A measure of time complexity of an algorithm. An aproximation of the time taken to execute an algroithm for a given number of items in a data set.

Question 22

What are trees

Answer 22

A tree is a connected, undirected graph with no cycles, a common abstract data type (ADT)

Question 23

What is a rooted tree?

Answer 23

A rooted tree is a tree with one node that is defined as the root. Every node except the root has one unique parent (different from binary tree)

Question 24

How do divide + conquer algorithms (logarithmic functions) work?

Answer 24

They halve the size of the problem at each pass. So the time complexity increases very slowly as the problem size increases.
e.g. in binary search algorithm, for balenced tree of 1024 (i.e. 2∧(10)) only 10 items need to be explained. Or 2948 (i.e. 2∧(11)) only 11 items need to be explaned.

Question 25

What is a permutation?

Answer 25

A permutation of n items is the number of ways the n items can be arranged.

Question 26

What is a repition permutation?

Question 27

What is a no repition permutation?

Question 28

What is the time complexity of a no repition permutation?

Answer 28

O(n!)

Question 29

What is the time complexity of a repition permutation?