Algorithms Flashcards

You may prefer our related Brainscape-certified flashcards:
1
Q

what is recursion

A

the ability of a subroutine to call itselff

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

characteristics of a recursive subroutine

A
  • 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

what is the algorithm for an in order traversal

A
  • traverse the left subtree
  • visit the root node
  • traverse the right subtree
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

algorithm for post order traversal

A
  • traverse the left subtree
  • traverse the right subtree
  • visit the root node
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

algorithm for pre order traversal

A
  • visit the root node
  • traverse the left subtree
  • traverse the right subtree
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

why is time complexity important when coding

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

how does depth first traversal work

A
  • uses a stack
  • starts at root, follows one branch as far as it’ll go, then backtracks
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

how does breadth first search work

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

how to do depth first traversal

A
  • 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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

how to do breadth first search

A
  • 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

what is the objective of dijkstras algorithm

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

how does dijkstras algorithm work

A
  • 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

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

A

infinity, as the distances are unknown

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

what is an algorithm

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

what is a mealy machine

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

what are FSMs

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

how do finite state machines operate

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

FSMs consist of:

A

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.

19
Q

uses of FSMs and mealy machines

A

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

20
Q

what is bubble sort

A

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

21
Q

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

A

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

22
Q

bubble sort time complexity

A
  • 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.
23
Q

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

A

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]

24
Q

summarise merge sort

A
  • 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.
25
Q

how to carry out a binary tree search

A

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:

26
Q

what is a set

A

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

27
Q

what is a regular expression

A

a way of describing a set

28
Q

regular expression examples and what they mean

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

a language is called regular if

A

it can be represented by a regular expression.

30
Q

what is the Halting problem

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

Significance of the Halting Problem

A

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

32
Q

What is a Turing Machine?

A

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
33
Q

features of a Turing machine

A
  • 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
34
Q

importance of a Turing machine

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

transition function for a Turing machine

A

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

36
Q

what is a universal turing machin

A
  • 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
37
Q

benefits of reverse polish notation

A
  • 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
38
Q

how to do reverse polish notation using a stack

A
  • 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
39
Q

operations from highest to lowest precedence

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

what is reverse polish notation

A

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

41
Q

where is reverse Polish notation used

A

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

42
Q

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

A
  • 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
43
Q

components of a stack frame

A

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

44
Q

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

A

because it had an infinite amount of memory/tape