(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.