8. algorithms

Question 1

recursive subroutine

Answer 1

defined in terms of itself and calls within itself.

the process of executing this subroutine is called recursion

Question 2

3 characteristics of recursive routine

Answer 2

• stopping condition or base case must be included which when met means that the routine will not call itself and will start to ‘unwind’
• for input values other than stopping condition, the routine must call itself
• the stopping condition must be reached after a finite number of calls

Question 3

in-order transversal

Answer 3

transverse the left subtree
visit the root node (middle)
visit the right subtree

Question 4

post-order family

Answer 4

transverse the left subtree
transverse the right subtree
visit the root (right)

Question 5

pre-order traversal

Answer 5

visit the root (left)
transverse the left subtree
transverse the right subtree

Question 6

big O notation in order of efficiency

Answer 6

constant
logarithmic
linear
polynomial
exponential
factorial

Question 7

constant

Answer 7

o(1)
no loops or recursion - what to look out for
e.g. accessing an element in array
linear straight line graph - what the graph looks like

Question 8

logarithmic

Answer 8

o(log n)
1/2 data sets
e.g. binary search
similar to linear graph but with a bump at the start

Question 9

linear

Answer 9

o(n)
a single loop
e.g. linear search
‘directly proportional’

Question 10

polynomial

Answer 10

o(n^2)
nested loops
e.g. bubble sort
half a u

Question 11

exponential

Answer 11

o(2^n)
recursion
e.g. recursion
half a u closer to y axis

Question 12

o n log n

Answer 12

e.g. merge sort

Question 13

permutations

Answer 13

the permutation of a set of objects is the number of ways of arranging the objects.

e.g. if you have 3 objects A B C, you can choose any of A B C to be the first object, you then have two choices for the second object.

Question 14

formula for calculating the number of permutations of 4 objects is…

Answer 14

4 x 3 x 2 x 1, written as 4!, spoke as “four factorial”

Question 15

constant time

Answer 15

same amount of time to execute regardless of the size of the input data set

Question 16

linear time

Answer 16

describes an algorithm whose performance will grow in linear time, in direct proportion to the size of the data set

Question 17

polynomial time

Answer 17

describes an algorithm whose performance is directly proportional to the square of the size of the data set

Question 18

exponential time

Answer 18

describes an algorithm where the time taken to execute will double with every additional item added to the data set.

the execution time grows in exponential time and quickly become very large.

Question 19

logarithmic time

Answer 19

the time taken to execute an algorithm of order o(log n) (logarithmic time) will grow very slowly as the size of the data set increases.

Question 20

factorial time

Answer 20

the time taken to execute an algorithm of order o(n!) will grow very quickly, faster than o(2^n).

Question 21

time complexity of linear search

Answer 21

o(n)

Question 22

time complexity of binary search

Answer 22

o(log n)

Question 23

time complexity of merge sort

Answer 23

o(n log n)

Question 24

depth-first (using a stack)

Answer 24

is implemented automatically during execution of a recursive routine to hold local variables, parameters and return addresses each time a subroutine is called. alternatively, a non-recursive routine could be written and the stack maintained as part of the routine.

start at root, follow one branch as far as it will go, then backtrack.

Question 25

breadth-first (using a queue)

Answer 25

start root, scan every node connected and then continue scanning from left to right.

Question 26

applications of depth-first search

Answer 26

• in scheduling jobs where a series of tasks is to be performed, and certain tasks must be completed before the next one begins
• in solving problems such as mazes, which can be represented as a graph

Question 27

applications of breadth-first search

Answer 27

• a major application of a breadth-first search is to find the shortest path between two points A and B. finding the shortest path is important in e.g. GPS navigation systems and computer networks
• facebook, each user profile is regarded as a node or vertex in the graph, and two nodes are connected if they are each others friends
• web crawlers. a web crawler can analyse all the sites you can reach by following links randomly on a particular website

Question 28

we increasingly rely on computers to find the optimum solution to a range of different problems. for example…

Answer 28

• scheduling aeroplanes and staff so that air crews always have the correct minimum rest time between flights
• finding the nest move in a chess problem
• timetabling classes in schools and colleges
• finding the shortest path between two points - for building circuit boards, route planning, communication networks and many other application

Question 29

dijkstra’s algorithm

Answer 29

is designed to find the shortest path between one particular start node and very other node in a weighted graph.

uses priority queue rather than FIFO queue

Question 30

dijkstra (pronounced dike-stra)

Answer 30

lived from1930 to 2002
dutch computer scientist
received the turing award in 1972 for fundamental contributions to developing programming languages

Question 31

weights

Answer 31

e.g. could represent distances or time taken to travel between towns or the cost of travel between airports

Question 32

brute-force method

Answer 32

testing out very combination of routes

Question 33

traceable problem

Answer 33

has a polynomial time solution 0(n^k)

e.g. problems which have solutions with time complexities of o(n), o(n log n) and o(n^10) are all traceable

Question 34

untraceable problem

Answer 34

is one that does have a polynomial-time solution
e.g. problems of time complexity o(2^n) and o(n!) are examples of intractable problems.

Question 35

heuristic approach

Answer 35

an approach to problem solving which employs an algorithm or methodology not guaranteed to be optimal or perfect, but is sufficient for the purpose.

an adequate solution may be achieved by trading optimality, completeness, accuracy or precision for speed.

Question 36

the halting problem

Answer 36

is the problem of determining whether for a given input, a program will finish running or continue for ever.

what the halting problem shows is that there are some problems that cannot be solved by computer.

Question 37

david hilbert

Answer 37

1920s mathematician proposed any problem defined properly could be solved by writing an appropriate algorithm - i.e. that every problem was computable.

Question 38

turing 1936

Answer 38

was able to prove david wrong. some problems are simply non-computable. the fact that some problems have no solution is significance to computer scientists.

one definition of computer science is “the study of problems that are and that are not computable”, or the study of the existence and the non existence of algorithms.