Algorithms

Question 1

What type of data structure does a depth-first traversal use?

Answer 1

1) Stack
2) When a node is visited place it on the stack
3) Once every node connected to that node has been visited, pop that node from the stack
4) In theory, should reach the bottom of the graph before coming back up to the start (LIFO)

Question 2

What type of data structure does a breadth-first traversal use?

Answer 2

1)Queue
2)Place the first node onto the queue and every node connected to that onto the queue
3)That node has then been fully discovered, so dequeue it
4) Repeat this process until the whole thing is traversed

Question 3

What is a Pre-Order Traversal used for?

Answer 3

Copying trees - can be performed on any tree

Question 4

How do you perform a pre-order traversal?

Answer 4

Place a marker on the left side of each leaf
(Root, Left, Right)

Question 5

What is an In-Order Traversal used for?

Answer 5

To search the contents of a binary tree and output them in the correct order
(Only used on binary trees)

Question 6

How do you perform an In-Order Traversal?

Answer 6

Place a marker on the bottom of each leaf

Question 7

What is a Post-Order Traversal used for?

Answer 7

Useful for converting Infix to Reverse Polish Notation
(Can be used on any tree)

Question 8

How do you perform a Post Order traversal?

Answer 8

Place a marker on the right of each leaf

Question 9

What is an algorithm?

Answer 9

A set of instructions which completes a task in a finite time and always terminates

Question 10

What is a linear search?

Answer 10

A search to find an item in an unordered list. You search each item until you find the one you are searching for

Question 11

What are the Pros/Cons of Linear Search?

Answer 11

Pros -
Easy to program

Cons -
Very inefficient so rarely used in the real world

Question 12

What is the time complexity of a linear search?

Answer 12

O(N)

Question 13

What is a binary search?

Answer 13

A search to find an item in an ordered list. Works by looking at the midpoint of a list and determining if the target is higher or lower

Question 14

What is the time complexity of a binary search?

Answer 14

O(logN)

Question 15

What is a bubble sort?

Answer 15

An algorithm that sorts a list of data by swapping the position of adjacent items to order them

Question 16

What is the time complexity of a bubble sort?

Answer 16

O(N^2) - Very Inefficient

Question 17

What is a merge sort?

Answer 17

An algorithm that sorts arrays by splitting them into smaller lists and reforming them - Divide and Conquer Method

Question 18

What is the time complexity of a merge sort?

Answer 18

O(nlogn)

Question 19

What is Dijkstra’s shortest path algorithm?

Answer 19

An algorithm used to find the shortest path from a starting node to each other node in a network

Question 20

What is meant by a recursive subroutine?

Answer 20

A subroutine which calls itself

Question 21

What is Reverse Polish Notation?

Answer 21

A postfix way of writing expressions, eliminating any brackets and order of execution.

Question 22

What are the uses of RPN?

Answer 22

They are used on a stack, meaning it is used in any interpreters based upon a stack

Question 23

Describe how a stack is used to evaluate an RPN expression

Answer 23

1) Algorithm moves along the expression, pushing each operand onto the stack
2) When an operator is reached, two items are popped off the stack and applied to the operator
3) The result is then stored on the stack
4) This repeats until the end of the expression, in which the answer should be calculated - pop the answer off the stack

Question 24

Explain why Reverse Polish Notation is used over infix

Answer 24

Brackets aren’t required, so its easier to write the program
Operators appear in the order required by computation, makes it easier for the computer to evaluate

Question 25

Why does a bubble sort have the time complexity O(N^2)

Answer 25

Because in each pass through there are n items, and there will be at most n passes through the list

Question 26

Why does a linear search have the time complexity O(N)

Answer 26

As the list gets bigger, the time taken to search the list increases at the same rate
It looks at each item in the list, so if there are n items in the list - at worst there are n comparisons

Question 27

What is the usage of Dijkstra’s shortest path algorithm?

Answer 27

1) Routers deploy the algorithm when trying to route packets by using the shortest path
2) Also used in satelite systems that display the fastest route to a location

Question 28

Pseudocode for Linear Search

Answer 28

Do Until Found == True or Count == Array[Count]
If Target == Array[Count]
Found = True
Else
Count = Count +1
END IF

If Found = True
OUTPUT Target

ELSE
  OUTPUT Target Not Found

Question 29

Pseudocode for Binary Search

Answer 29

Do until Found = TRUE or TopPointer < BottomPointer
If Array(MidPoint) = Target
Found = True
If Array(MidPoint) > Target
THEN TopPointer = MidPoint - 1

If Array(MidPoint) < Target
BottomPointer = MidPoint + 1