Algorithms

Question 1

what is recursion

Answer 1

the ability of a subroutine to call itselff

Question 2

characteristics of a recursive subroutine

Answer 2

• a stopping condition/base case must be included, which when met, the routine will not call itself
• for input values other than the stopping condition, the routine must call itself
• system keeps pending calls on a stack
• parameters are also passed on a stack
• system needs a lot of memory to handle recursion
• the stopping condition must be reached after a finite number of calls

Question 3

what is the algorithm for an in order traversal

Answer 3

• traverse the left subtree
• visit the root node
• traverse the right subtree

Question 4

algorithm for post order traversal

Answer 4

• traverse the left subtree
• traverse the right subtree
• visit the root node

Question 5

algorithm for pre order traversal

Answer 5

• visit the root node
• traverse the left subtree
• traverse the right subtree

Question 6

why is time complexity important when coding

Answer 6

helps design algorithms that will run quickly while taking up the minimal amount of resources such as memory

Question 7

how does depth first traversal work

Answer 7

• uses a stack
• starts at root, follows one branch as far as it’ll go, then backtracks

Question 8

how does breadth first search work

Answer 8

Start from the source node and mark it as visited.
Add the source node to a queue.
While the queue is not empty:
Remove the node from the front of the queue.
Visit all its unvisited neighbors and add them to the queue.
Mark them as visited.

Question 9

how to do depth first traversal

Answer 9

• PUSH the first vertex onto the stack
• Mark vertex as visited
• REPEAT
• visit next unvisited vertex to the one on top of the stack
• mark as visited
  If no vertex to visit, POP vertex off stack
• Until stack is empty

simplified:

Start from the source node.
Visit a neighbor and recursively continue the search as far as possible along this path.
When you reach a dead-end (no unvisited neighbors), backtrack and explore other paths.

Question 10

how to do breadth first search

Answer 10

• PUSH the first vertex onto the queue
• mark vertex as visited
• Visit unvisited vertex’s connected to the first vertex
• PUSH vertex’s onto queue
• Until all vertex’s have been visited
• Repeat
• Visit the unvisited vertex’s
• PUSH vertex onto queue
• Until all vertex’s visited
• Until queue is empty

Question 11

what is the objective of dijkstras algorithm

Answer 11

to find the shortest path between a starting vertex and any other vertex in a graph

Question 12

how does dijkstras algorithm work

Answer 12

• we use 2 lists : one to keep track of the vertices we have visited, and one to keep track of unvisited vertices
  1. visit the unvisited vertex with the smallest known distance from the start vertex (would be the start vertex)
  2. for the current vertex, examine it’s unvisited neighbours
  3. for the current vertex, calculate the distance of each neighbour from the starting vertex
  4. update the distance in the table
  5. update the previous vertex for each of the updated distances
  6. add the previous vertex to the list of visited vertex
  7. repeat until all vertices are visited

Question 13

what do we label the distances from the starting vertex in dijkstras algorithm and why

Answer 13

infinity, as the distances are unknown

Question 14

what is an algorithm

Answer 14

a finite sequence of instructions that can be followed to complete a task and that always terminates

Question 15

what is a mealy machine

Answer 15

an FSM with an output
- the outputs are determined by both its current state and the current input
- there can only be one possible transition

Question 16

what are FSMs

Answer 16

a computational model that consists of a finite number of states.

Question 17

how do finite state machines operate

Answer 17

Having a set of states (one state at a time).

Starting in an initial state.

Transitioning between states based on input symbols.

Reaching either a final/accepting state

Question 18

FSMs consist of:

Answer 18

States: These are the individual steps that the machine can be in at any time.

Transitions: These are the changes between states based on an input symbol.

Start State: The state where the FSM begins.

accept States: The states that represent successful completion of the process.

dead states - a state from which there is no possible transition to an accepting or final state.

Question 19

uses of FSMs and mealy machines

Answer 19

FSM - Digital circuits: FSMs help design systems that react to inputs
Compilers: FSMs help parse regular expressions and check whether sequences of characters are valid.

Mealy machines - Embedded systems: Devices that need to respond to external stimuli (like sensors)
- Telecommunication protocols: Machines that need to send signals or receive them

Question 20

what is bubble sort

Answer 20

a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order.

Question 21

bubble sort example - Sorting the list [4, 3, 2, 1]

Answer 21

First pass: [3, 2, 1, 4] (4 moves to the end)
Second pass: [2, 1, 3, 4]
Third pass: [1, 2, 3, 4]

Question 22

bubble sort time complexity

Answer 22

• Best case (O(n)): When the list is already sorted, only one pass is needed.
• USUALLY (O(n²)): In the worst scenario, every element needs to be compared and swapped, leading to n passes, with n-1 comparisons per pass.

Question 23

merge sort Example: Sorting the list [8, 4, 6, 1]:

Answer 23

Divide into [8, 4] and [6, 1].

Recursively sort both halves:
Sort [8, 4] into [4, 8]
Sort [6, 1] into [1, 6]

Merge the two sorted halves:
[4, 8] and [1, 6] → [1, 4, 6, 8]

Question 24

summarise merge sort

Answer 24

• a more efficient sorting algorithm that uses the Divide and Conquer approach:
• Divide: Split the list into two halves.
• Conquer: Recursively apply the merge sort algorithm to each half.
• Combine: Merge the two sorted halves back together into a single sorted list.

Question 25

how to carry out a binary tree search

Answer 25

Start at the root of the tree.

Compare the target value with the value at the current node:

If the target is equal to the node’s value, you’ve found the item.

If the target is less than the node’s value, move to the left child.

If the target is greater than the node’s value, move to the right child.

Repeat the process until you find the value or reach a leaf (end of a branch).

Example: For a binary search tree:

Question 26

what is a set

Answer 26

an unordered collection of values in
which each value occurs at most once.

Question 27

what is a regular expression

Answer 27

a way of describing a set

Question 28

regular expression examples and what they mean

Answer 28

• asterix - (0 or more repetitions)
• plus sign - (1 or more repetitions)
• ? (0 or 1 repetitions, ie optional)
• | (alternation, ie or)
• ( ) to group regular expressions.

Question 29

a language is called regular if

Answer 29

it can be represented by a regular expression.

Question 30

what is the Halting problem

Answer 30

• determines if a program will halt
• for a particular input
• without running the program

Question 31

Significance of the Halting Problem

Answer 31

The Halting Problem is significant because it shows that there are some problems that no computer, no matter how powerful, can solve

Question 32

What is a Turing Machine?

Answer 32

a theoretical machine which can stimulate any computer algorithm, no matter how complex

• the Turing machine consists of two parts : the tuple that the machine can read and write, and the controller(the program) which determines what happens at each cell
• the controller is an FSM
• the tape is indefinitely long, with marked off squares
• It has a read-write head that can read symbols from the tape

Question 33

features of a Turing machine

Answer 33

• has a finite set of states
• has a set of transition rules
• had a read/write head that can move along the tape, one square at a time
• has accepting/halting states
• has a state register/current state

Question 34

importance of a Turing machine

Answer 34

• proves a definition of what is computable
• it can compute anything that is computable

Question 35

transition function for a Turing machine

Answer 35

δ(current_state, current_symbol) = (new_state, new_symbol, direction)

Question 36

summarise a universal turing machine

Answer 36

• A Turing machine that can simulate the behaviour of any other Turing machine
• faithfully executes operations on the data precisely as the simulated Turing machine does

Question 37

benefits of reverse polish notation

Answer 37

• eliminates the need for brackets in sub expressions
• simpler for a machine/computer to evaluate
• simpler to code algorithm
• operators appear in the order required for computation
• no need to backtrack when evaluating

Question 38

how to do reverse polish notation using a stack

Answer 38

• starting from LHS, push operands onto the stack
• each time an operator is reached, pop the required number of values off the stack
• push result of applying operator onto the stack
• when the end of the expression is reached,the top item of the stack is the result

Question 39

operations from highest to lowest precedence

Answer 39

1. unitary minus ~
2. exponent ^
3. multiply *
4. divide /
5. addition
6. subtraction

Question 40

what is reverse polish notation

Answer 40

a method of writing arithmetic expressions where the operators (like +, -, *, /) come after the operands

Question 41

where is reverse Polish notation used

Answer 41

programming languages that use a stack-based interpreter, such as Postscript and bytecode for Java.

Question 42

to enable the use of recursion, a programming language must provide a stack
- explain what this stack will be used for and why a stack is appropriate

Answer 42

• to store return addresses
• to store local variables
• to store parameters
• procedures must be returned in reverse order, and a stack will help as it is a LIFO structure

Question 43

components of a stack frame

Answer 43

stores :
- local variables
- return address
- parameters
- register values

Question 44

why can a UTM be considered more powerful than any other computer you can purchase

Answer 44

because it had an infinite amount of memory/tape