(P1) Fundamentals of Algorithms

Question 1

What is graph traversal?

Answer 1

The process of visiting each vertex in a graph.

Question 2

What are the two graph traversals?

Answer 2

Depth-first and breadth-first.

Question 3

Describe depth-first traversal.

Answer 3

A branch is fully explored before backtracking.
Uses a stack and is used navigating mazes.

Question 4

Describe breadth-first traversal.

Answer 4

A node is fully explored before venturing on the next node.
Uses a queue.
Used for determining the shortest path on an unweighted graph.

Question 5

What is an algorithm?

Answer 5

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

Question 6

What is a tree?

Answer 6

A connected acyclic graph.

Question 7

Describe tree traversal.

Answer 7

Process of visiting each node in a tree.
Unique to trees and must start at the root.

Question 8

Where should the dot be drawn for a pre-order traversal?

Answer 8

Left.

Question 9

Where should the dot be drawn for a in-order traversal?

Answer 9

Bottom.

Question 10

Where should the dot be drawn for a post-order traversal?

Answer 10

Right.

Question 11

What can pre-order traversal be used for?

Answer 11

Copying trees.

Question 12

What can an in-order traversal be used for?

Answer 12

Used in binary trees to outputs the contents of a binary tree in ascending order.

Question 13

What can post-order traversals be used for?

Answer 13

Infix to RPN conversions.
Producing a postfix expression from an expression tree.
Emptying a tree.

Question 14

How are Infix to RPN and binary trees related?

Answer 14

Infix to RPN involve the making and traversing of a binary tree.

Question 15

What is an opcode?

Answer 15

An operator.

Question 16

What is an operand?

Answer 16

Data which is applied to the operator.

Question 17

When creating an expression tree, what should always be the parent node and the child nodes?

Answer 17

Parents should be the opcode.
Children should be the operands.

Question 18

What is produced from performing an in-order traversal on an expression tree?

Answer 18

Infix expression.

Question 19

What is produced from performing an post-order traversal on an expression tree?

Answer 19

Postfix expression.

Question 20

How do you work out a postfix expression?

Answer 20

Perform the calculation of the opcode and only the two preceding operands and put back into expression. Repeat.

Question 21

What notation do humans use?

Answer 21

Infix notation.

Question 22

What does RPN stand for?

Answer 22

Reverse Polish Notation.

Question 23

What is RPN?

Answer 23

A postfix way of writing expressions.
Eliminates need for brackets and any confusion of the order of execution.
Opcode is written after the operands.

Question 24

What data structure can be used to evaluate postfix equations?

Answer 24

Stacks.

Question 25

Why is RPN ideal for interpreters?

Answer 25

RPN can be executed on a stack, making it ideal for interpreters which are based on a stack such as Bytecode or PostScript.

Question 26

What is the pseudocode for a RPN calculation?

Answer 26

Stack1 <— Stack
RPN <— Array
Op2 <— Single
Op1 <— Single
Result <— Single
For i = 0 to RPN.count - 1
If RPN (i) = operand
Stack1.push (RPN(i))
ElseIf RPN (i) = opcode
Op2 = Stack1.pop
Op1 = Stack1.pop
Result = Perform(RPN(i), Op1, Op2)
End If
End For
Print Stack1.peek

Question 27

What are the three different searching algorithms?

Answer 27

Linear search, binary search and binary tree search.

Question 28

Describe a linear search.

Answer 28

Conducted on an unordered list.
Hugh time complexity.
Has one loop.
Time complexity of O(n).

Question 29

What is pseudocode for a Linear search?

Answer 29

LinearSearch(Target, ArrayofValues)
Boolean Found
Integer Count
Found <— FALSE
Count <— 0
Do Until Found == TRYE or Count == ArrayofValues Count
If Target == ArrayofValues(Count)
Found <— True
Else
Count <— Count + 1
End If
Loop
If Found = True
Output Target found at Count
Else
Output Target not found
End if

Question 30

Describe a binary search.

Answer 30

Used on any ordered list.
Works by looking at the midpoint of a list and determining if the target is higher or lower.
Time complexity is O(log(n))

Question 31

What sorting algorithms can be used to order a list?

Answer 31

Merge or bubble sort.

Question 32

What is the pseudocode for a binary search?

Answer 32

BinarySearch(Target, ArrayorValues)
Integer TopPointer
Integer BottomPointer
Integer Midpoint
Boolean Found
Found <— FALSE
BottomPointer <— 0
TopPointer <— ArrayorValues Count - 1

Do Until Found = True or TopPointer < BottomPointer
Midpoint = int mid TopPointer, BottomPointer
If ArrayofValues(Midpoint) = Target
Found = TRUE
ElseIf ArrayofValues(Midpoint) > Target
TopPointer = Midpointer - 1
ElseIf ArrayofValues(Midpoint) < Target
BottomPointer = Midpoint + 1
End If
Loop
If Found = TRUE
Output Target found at Midpoint
Else
Output Target not found
End if

Question 33

What method can a binary search be completed through?

Answer 33

Recursion.

Question 34

What is the time complexity for a binary tree search?

Answer 34

O(log(n))

Question 35

What is Big O notation?

Answer 35

A way of classifying algorithms based on time and space complexity.

Question 36

Describe bubble sort.

Answer 36

The idea of swapping the position of adjacent items to order them.
Time complexity of O(n^2)
Very inefficient.

Question 37

What is pseudocode for a bubble sort?

Answer 37

Integer Max
String Temp
Boolean Swapped
Integer Passes
Max <— List.Count - 1
Swapped <— TRUE
Passes <— 0

Do Until Swapped == FALSE or Max == 0
Swapped <— FALSE
Max <— Max - 1
Passes <— Passes + 1
For a = 0 to Max
If List(a) > List(a + 1)
Temp <— List(a)
List(a) <— List(a + 1)
List(a + 1) <— Temp
Swapped <— TRUE
End If
Next
Loop

OUTPUT Passes
OUTPUT List

Question 38

Describe merge sort.

Answer 38

Orders arrays by splitting them into smaller lists and them reforming them
Divide and conquer
Quicker than bubble sort
Time complexity of O(nlog(n))

Question 39

What is an optimisation algorithm?

Answer 39

Finds the best possible solution to the problem posed.

Question 40

Give an example of an optimisation algorithm.

Answer 40

Dijkstra’s algorithm.

Question 41

What is the purpose of Dijksta’s algorithm?

Answer 41

Finds the shortest path between two nodes in a graph.