Optimisation + Other Algorithms

Question 1

What is an optimisation algorithm?

Answer 1

An algorithm that finds the best possible solution to the problem proposed.

Question 2

What is an example of an optimisation algorithm?

Answer 2

Dijkstra’s Shortest Path (DSP)

Question 3

What does DSP do?

Answer 3

Calculates the shortest distance between a starting node to all other nodes in the graph

Question 4

What is the efficiency of DSP?

Answer 4

O(n²)

Question 5

What are the uses of DSP?

Answer 5

• Shortest path between two locations in a transport network
• Telephone and computer network planning
• Network routing / packet switching

Question 6

In what terms can algorithms be classified as?

Answer 6

• Time complexity
• Space required

for a given size of dataset

Question 7

What is Big O notation

Answer 7

Used to describe time complexity of of algorithms, based on worst case scenario for that algorithm for a given dataset of size n

Convenient way to compare efficiency of algorithms and determine how well an algorithm will scale

Question 8

What is a tractable algorithm?

Answer 8

An algorithm that can be solved within polynomial time: O(n^k)

Question 9

What are all the time complexities?

Answer 9

• Constant complexity: O(1)
• Logarithmic Complexity: O(logn)
• Linear Complexity: O(n)
• Polynomial Complexity: O(n^k)
• Exponential Complexity: O(xⁿ)
• (Factorial Complexity: O(n!) )

Question 10

What is an intractable algorithm?

Answer 10

An algorithm that does not have a solution within polynomial time so is not practical for anything other than small n.

Question 11

What are the properties of an algorithm with constant complexity?

Answer 11

• Time Taken is constant so is independent of size of the dataset
• As n increases the time taken stays the same

Question 12

What are some examples of algorithms with a constant complexity?

Answer 12

• Accessing an index in an array
• Looking up a value in a hash table (assuming no collisions)
• Popping from a stack or dequeueing from a queue

Question 13

What are the properties of an algorithm with logarithmic complexity?

Answer 13

• Time taken increases logarithmically with respect to the size of the database
• The size of the problem set is halved after each iteration or recursive call

Question 14

What are some examples of algorithms with a logarithmic time complexity?

Answer 14

• Binary Search
• Merge Sort

Question 15

What are the features of an algorithm with a linear time complexity?

Answer 15

Time taken increases proportionally with the size of the dataset

Question 16

What are some examples of algorithms with a linear time complexity?

Answer 16

• Linear Search
• Traversing a linked list

Question 17

What are the properties of an algorithm with a polynomial complexity?

Answer 17

• Time taken increases exponentially with the size of the dataset
• At the limit of the tractability

Question 18

What are some examples of algorithms with a polynomial time complexity?

Answer 18

• Bubble Sort
• Dijkstra’s shortest path

Question 19

What are the properties of an algorithm with exponential complexity?

Answer 19

• Time taken increases exponentially with size of dataset
• Intractable

Question 20

What are some examples of algorithms with an exponential time complexity?

Answer 20

• Brute force password cracking
• Travelling Salesman Problem

Question 21

What are the number of different permutations for a set with size n?

Answer 21

n!

Question 22

How to identify O(1)

Answer 22

No iteration or number of steps doesn’t depend on n

Question 23

How to identify O(n)

Answer 23

Single iteration that depends on n

Question 24

How to identify O(n^k)

Answer 24

Nested iteration where each iterative structure depends on n and k is the iterative depth

Question 25

How to identify O(logn)

Answer 25

Breaking down the problem into halves

Question 26

How to identify O(xⁿ)

Answer 26

Number of iterative structures/ recursive calls depends on n

Question 27

What do you do if an algorithm has a combination of time complexities?

Answer 27

You select the worst Big O factor

Question 28

What is a heuristic?

Answer 28

Rules based on the knowledge of a problem that can be used to find an approximate solution by changing some constraints in the problem or reducing the problem space. A heuristic approach employs a method of finding a solution that might not be the best. (reducing problem space or changing constraints)

Question 29

What is the halting problem?

Answer 29

Determining whether a program will halt for a particular input without running the problem However, an algorithm cannot be written that can determine whether another algorithm will finish with a given input

Question 30

What did the Halting Problem prove?

Answer 30

There was an example of a problem that is unsolvable

Question 31

What was the significance of the Halting Problem?

Answer 31

Demonstrated that there are problems that are non computable - unsolvable by computers and even AI algorithms

Question 32

Why are heuristics used?

Answer 32

A solution will arise within a reasonable time. However this may not be the best solution.

Question 33

What is a heuristic approach

Answer 33

A heuristic approach employs a method of finding a solution that might not be the best. (reducing problem space or changing constraints)

Question 34

What problems cannot be solved computationally?

Answer 34

Problems where there is no certain outcome or because limits of hardware make solving the problem with a certain outcome impractical

Question 35

What is an unsolvable (non-computable) problem

Answer 35

A problem that can't be solved no matter how much time or computing power is devoted to it