1.3 Fundamentals of algorithms

Question 1

Define implementation

Answer 1

Creating code to produce a programmed solution

Question 2

Define depth first graph traversal

Answer 2

A method for traversing a graph that starts at a chosen node and explores as far as possible along each branch away from the starting node before backtracking to visit unvisited nodes. It is often implemented with a recursive algorithm

Question 3

Define breadth first graph traversal

Answer 3

A method for traversing a graph that explores nodes closest to the starting node first before progressively exploring nodes that are further away. A queue is used to keep track of the nodes to visit

Question 4

What are the 3 ways of traversing a binary tree and their uses?

Answer 4

• Pre-order: Can be used with expression trees to evaluate the expression using prefix notation
• In-order: The equivalent of a binary search of the tree
• Post-order: Will produce Reverse Polish Notation

Question 5

Define traversal

Answer 5

The process of reading data from a tree or graph by visiting all of the nodes

Question 6

Define pre-order traversal

Answer 6

A method of traversing a tree by visiting the root, traversing the left subtree, and traversing the right subtree

Question 7

Define in-order traversal

Answer 7

A method of traversing a tree by traversing the left subtree, visiting the root, and traversing the right subtree

Question 8

Define post-order traversal

Answer 8

A method of traversing a tree by traversing the left subtree, traversing the right subtree, and then visiting the root

Question 9

What are base and general cases of recursion?

Answer 9

A base case of a recursive function is the point at which the function will stop calling itself. The general cases of a recursive function are all the other cases of the function where it calls itself

Question 10

Define single source

Answer 10

In the Dijkstra’s algorithm it means that the shortest path is calculated from a single starting point

Question 11

Define shortest path

Answer 11

The shortest distance between two vertices based on the weighting of the edges

Question 12

Define linear search

Answer 12

A simple search technique that looks through data one item at a time until the search term is found

Question 13

Define binary search

Answer 13

A technique for searching ordered data that works by splitting datasets in half repeatedly until the search data is found

Question 14

Define binary tree search

Answer 14

A technique for searching a binary tree that traverses the tree until the search term is found - it will move down the tree depending on if the target node is expected to be found on the left or right of the current node

Question 15

Define infix notation

Answer 15

Expressions that are written with the operators within the operands

Question 16

Define postfix notation

Answer 16

Expressions that are written with the operators after the operands - this is also known as Reverse Polish Notation

Question 17

Define prefix notation

Answer 17

Expressions that are written with the operators before the operands - this is also known as Polish Notation

Question 18

Why is Reverse Polish Notation used?

Answer 18

An interpreter has no inherent undersanding of the order of mathematical operations, so by using RPN, the need for brackets is removed, and operations can be processed

Question 19

How do the locations of operands in expressions link to binary trees?

Answer 19

• In-order traversal of a binary tree of an expression would give an expression in infix format
• Post-order traversal of a binary tree of an expression would give an expression in RPN
• Pre-order traversal of a binary tree of an expression would give an expression in Polish Notation

Question 20

How do you evaluate RPN?

Answer 20

Commonly RPN is evaluated using a stack

Question 21

Define bubble sort

Answer 21

A technique for putting data in order by repeatedly stepping through an array, comparing adjacent elements and swapping them if necessary until the array is in order

Question 22

Define merge sort

Answer 22

A technique for putting data in order by splitting lists into single elements and then merging them back together again