Classification of Algorithms

Question 1

What is abstraction?

Answer 1

The process of making a problem simpler by removing or hiding features.

Question 2

What is representational abstraction?

Answer 2

what remains after unnecessary details are removed e.g. the London underground map in which geographical details are all hidden.

Question 3

what is generalisation abstraction?

Answer 3

identifying key features of a problem to identify the problem as a more general set of problems.

Question 4

How does OOP implement information hiding?

Answer 4

a class encapsulates all of its private attributes and methods which are exposed only through its interface which could be the public methods.

Question 5

What is procedural abstraction?

Answer 5

ensures that subroutines are as generalised and as re-usable as possible.
- using a more general subroutine name
-splitting the user interface and processing of data into separate subroutines.

Question 6

What is functional abstraction?

Answer 6

aims to hide the complexity of an algorithm or how a part of the program works using subroutines.

Question 7

What is data abstraction?

Answer 7

allows you to separate how a complex data structure is used from how it is constructed.

Question 8

What is problem reduction?

Answer 8

removing unnecessary detail from a problem to reduce the problem to one that has already been solved.

Question 9

What is decomposition?

Answer 9

Breaking a large problem into smaller sub problems.

Question 10

What is composition?

Answer 10

combining parts of a solution together to form a solution made up of component part

Question 11

Automation

Answer 11

Designing, implementing and executing a solution to solve a problem automatically.
done by
- Implementing the data structures to store the data
- Implementing the algorithms to process the data

Question 12

Time wise complexity

Answer 12

algorithms that have a lot of steps or comparisons will take longer to compute

Question 13

Space wise complexity

Answer 13

algorithms that store a lot of temporary values while the processes take place will take up a lot of memory

Question 14

Example of constant time O(1)

Answer 14

• finding the first item in a list
• jumping straight to a value at a given index

Question 15

Example Logarithmic time O(logn)

Answer 15

Binary search

takes very little time because the possible list of remaining values os halved each time

Question 16

Example of linear time O(n)

Answer 16

linear search

Question 17

example loglinear time O(n log n)

Answer 17

merge sort
very efficient like binary search but sort is more complex than search so time wise complexity is larger

Question 18

example of polynomial time O(n^2)

Answer 18

Bubble sort
insertion sort
selection sort

Question 19

Exponential time O(k^n)

Answer 19

trying every possible value of a passcode

Question 20

order the time wise complexities from most to least efficient

Answer 20

O(1), O(logn), O(n), O(nlogn), O(n^2), O(k^n), O(n!)

Question 21

What is a tractable problem?

Answer 21

A problem which can be solved in a reasonable amount of time - polynomial or less

Question 22

What is an intractable problem?

Answer 22

A problem that can be solved but not in a reasonable amount of time - exponential or factorial time

Question 23

what is the tike complexity of a recursive algorithm?

Answer 23

O(2^n)

Question 24

Heuristic

Answer 24

an approach to solving intractable problems in a reasonable amount of time by accepting an imperfect solution

Question 25

strategies for tackling an intractable problem

Answer 25

-reducing the complexity of the problem
- accepting a close to optimal solution
- using algorithm that used a best guess or estimate based on experience

Question 26

Computable

Answer 26

a problem that can be solved by a computer

Question 27

Non- computable

Answer 27

problem that cannot be solved by a computer

Question 28

The halting problem

Answer 28

it is not possible to come up with a method that, given a program and its inputs, but without running the program, can tell if the program will halt.

Question 29

What is the significance of the halting problem?

Answer 29

demonstrates that there are some problems that cannot be solved using a computer

Question 30

Components of a Turing machine

Answer 30

• a finite set if states
• a finite alphabet if symbols
• an infinite length of tape with marked off squares
• a read write head that can travel across the tape one square at a time
• a set of rules

Question 31

Importance of Turing machines:

Answer 31

Turing machines provide a (general/formal) model of computation and provide a definition of what is computable.

Question 32

Universal Turing Machine

Answer 32

A turing machine that can simulate any turing machine due to it being given a standard description/transition rules at the start.