4.3 Algorithms Flashcards

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

Name an application of breadth-first search

A

Finding the shortest path for an unweighted graph

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

Name an application of depth-first search

A

Navigating a maze

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

2 differences between depth-first traversal and breadth-first traversal

A

DF: Chooses to explore the most recent node to be discovered
BF: Chooses to explore the least recent node to be discovered

DF: Implemented using a stack (when implemented iteratively)
BF: Implemented using a queue (when implemented iteratively)

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

Depth-first traversal algorithm (beyond spec)

A

Each node has a binary flag discovered which is updated whenever we pop a node off the stack and consider its neighbours

  1. Add the start node to the stack and mark it as discovered
  2. If the stack is empty, we’re done. Otherwise, pop the top node and visit it
  3. Push each of the current node’s undiscovered neighbours to the stack, and mark them as discovered
  4. Go back to step 2
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Breadth-first traversal algorithm (beyond spec)

A

Each node has a binary flag discovered which is updated whenever we dequeue an item and consider its neighbours

  1. Add the start node to the queue and mark it as discovered
  2. If the queue is empty, we’re done. Otherwise, dequeue the front node and visit it
  3. Enqueue each of the current node’s undiscovered neighbours to the queue, and mark them as discovered
  4. Go back to step 2
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

What is tree traversal?

A

Visiting the nodes of a tree in a specific order

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

Use of pre-order traversal

A

Copying a tree

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

2 uses of in-order traversal

A
  • Outputting the contents of a binary search tree in ascending order
  • Producing infix expression from an expression tree
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

2 uses of post-order traversal

A
  • Infix to RPN conversions
  • Producing a postfix (RPN) expression from an expression tree
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Pre-order traversal operation

A
  1. Visit the node
  2. Traverse the left hand sub tree
  3. Traverse the right hand sub tree
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

In-order traversal operation

A
  1. Traverse the left hand sub tree
  2. Visit the node
  3. Traverse the right hand sub tree
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Post-order traversal operation

A
  1. Traverse the left hand sub tree
  2. Traverse the right hand sub tree
  3. Visit the node
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

3 advantages of RPN

A
  • Eliminates need for brackets in sub-expressions
  • There is no need for precedence of operators
  • The expressions are in a from suitable for evaluation using a stack, as the expression can be evaluated from left to right
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Steps for converting postfix to infix (2*)

A
  • Convert “num num op” triplets one at a time, adding brackets each time
  • Remove any unnecessary brackets
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Steps for converting infix to postfix (3•)

A
  • Add brackets around every operation
  • Draw arrow from operator to end of its bracket
  • Write expression, keeping numbers in the same order
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Steps for linear search on a list

A
  1. Start at beginning of list
  2. Compare each item to one you want until
    • you find it or
    • you reach the end of the list

(use an indefinite while loop!)

17
Q

Steps for binary search on a value X (in English)

A
  1. Look at item in centre of sorted list (or array) (sort first if needed)
  2. If it isn’t X
    2.1. If it is larger than X, you can ignore all of the items above
    2.2. If it is smaller than X, you can ignore all of the items below
  3. Check middle of halved list and repeat, until you find X or the sublist cannot be halved any more.
18
Q

What is the while condition when coding binary search?

A

lower<= upper && !found

19
Q

What does it mean if you reach a leaf node before you find X in a binary tree search?

A

X is not in the tree

20
Q

Why is space complexity important to consider when analysing binary tree search?

A

Because the algorithm is recursive, it places a demand on the call stack

21
Q

Bubble sort (ascending order) pseudocode on array A

A

N ← length(A)
swapped ← True
while swapped and N > 1:
__swapped ← False
__for position = 0, 1, ... , N-2:
____if A[position] > A[position+1]:
______swap( A[position] , A[position+1])
______swapped ← True
__N ← N-1

22
Q

Merge sort complexity

A

O(n log n)

23
Q

What is an algorithm?

A

A sequence of unambiguous steps that can be followed to complete a task and that always terminates

24
Q

2 reasons why smaller time complexity is better

A
  • A quicker program could solve more of the same problem or run more programs in the same time period
  • Computers consume electricity to run…
25
Q

2 reasons why is smaller space complexity better

A
  • A program that uses less memory could run off cheaper hardware (as less RAM is needed)
  • Or a greater number of different algorithms can run on the same hardware simultaneously
26
Q

What is the purpose of Dijkstras algorithm?
Can the graph be directed/weighted?

A
  • Calculates the shortest path between a node and all other nodes in a graph
  • Graph may be directed or undirected
  • Graph must be weighted
27
Q

What approach does merge sort take to sort a list?

A

Divide and conquer

28
Q

What is bubble sort’s time complexity? Why?

A

O(n^2). Since it involves a for loop within a for loop. You need to do n passes of the list/array, and each pass involves swapping all the way down the list.