Fundamentals of Algorithms Flashcards

1
Q

What is an algorithm?

A

A set of instructions that completes a task in a finite time and always terminates

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

What is Graph Traversal?

A

Visiting each vertex in a graph

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

Two types of Graph Traversal?

A

Depth first search and breadth first search

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

Which traversal is best for navigating a maze?

A

Depth-first search

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

What is Breadth-first traversal useful for?

A

Shortest path on an unweighted graph

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

What abstract data type is used for breadth-first traversal?

A

Queue

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

What abstract data type is used in depth-first traversal

A

Stack

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

What types of graphs can be traversed?

A

Connected graphs

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

Can a tree undergo depth-first traversal?

A

Yes, but you might want to use tree-traversal instead

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

Can a graph traversal start from any node?

A

Yeah

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

What is tree-traversal?

A

Visiting/outputting each node in a tree; it’s an algorithm

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

Three types of tree-traversal

A

Preorder, inorder and postorder

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

Name a use of post-order traversal

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

TRICK: Where does the dot go for you to trace the tree for post-order traversal?

A

To the right

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

TRICK: Where does the dot go for you to trace the tree for in-order traversal?

A

Below

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

TRICK: Where does the dot go for you to trace the tree for pre-order traversal?

A

To the left

17
Q

Traversal used for copying a tree?

A

Pre-order traversal

18
Q

Name a use of inorder traversal

A

Output the contents of a binary search tree in ascending order

19
Q

Can inorder traversal be performed on any tree?

A

NO! Only binary trees

20
Q

Can preorder traversal be performed on any tree?

21
Q

Can postorder traversal be performed on any tree?

22
Q

Where does tree traversal start?

A

At the root

23
Q

How do traversals work their way through the tree?

A

Anti-clockwise

24
Q

What is true about RPN?
A. Uses queue
B. Eliminates needs for brackets
C. Based on graph

25
Convert infix expression to RPN: 14 + 6
14 6 +
26
Convert infix expression to RPN (12 - 4) x (3 + 5)
12 4 - 3 5 + x
27
Convert the following RPN to infix 13 6 + 4 -
(13 + 6) - 4
28
Convert the following infix expression to RPN 3(4 - 2) + 9
4 2 - 3 x 9 +
29
Convert the RPN 4 6 7 + - to Infix
4 - (6 + 7)
30
Which of the following is not an example where reverse Polish is used? A. PreScript B. Bytecode C. PostScript
A
31
What is the result of this reverse Polish expression? 4 6 8 - -
6
32
What is the purpose of an optimisation algorithm?
To find the best possible solution to the problem posed
33
Purpose of Dijkstra's algorithm?
Find the shortest path between two nodes in a network
34
Where is Dijkstra's algorithm used?
Satellite navigation and packet routing
35
Which is the most time efficient: bubble sort or merge?
Merge sort
36
Which sorting algorithm is an example of a "divide and conquer" algorithm?
Merge sort
37
Time complexity of a bubble sort algorithm?
O(n^2)
38
Time complexity of the merge sort algorithm?
O(nlogn)