Algorithms Flashcards

(39 cards)

1
Q

What is an algorithm?

A

A set of instructions that when followed can solve a specific problem

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

What are the two ways of traversing a graph?

A

Breadth first and depth first

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

How does breadth first traversal work?

A

A method for traversing a graph that explores nodes closest to the starting node first before progressively exploring nodes that are further away

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

What is depth first traversal?

A

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

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

Why do we traverse a tree?

A

To extract data in a particular order ; pre-order, in-order, post-order

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

What does it mean to visit a node?

A

Extracting the data at that node

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

What is a pre-order traversal?

A

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

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

What is in-order traversal?

A

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

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

What is post-order traversal?

A

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

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

What is traversal?

A

The process of reading data

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

What is a recursion?

A

When the function calls itself

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

How does recursion work?

A

After the procedure has been called for the first time the program will check if theres a node to the left. If there is then it goes left and the procedure calls itself.

Keeps repeating the process until there are no more nodes to visit on the left ; reaches terminating case

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

What is a terminating case?

A

The point at which the recursive function will stop calling itself

(AKA base case)

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

What is Dijkstra’s algorithm?

A

An algorithm that calculates the shortest path between two vertices/nodes on a graph

[can only be used in weighted graphs]

12
Q

What type of queue do you use in Dijkstra’s algorithm?

A

A priority queue

12
Q

Steps to do dijkstra’s algorithm

A

set a to 0 and evrything to infinity

12
Q

What do you use to keep a note of the path travelled of the nodes?

A

A trace table

12
Q

What are some uses of Dijkstra’s algorithm?

A
  1. Satnav
  2. Logistics and scheduling: where there is a large network of vehicles eg planes and buses, the algorithm can be used to calculate the optimum routes
  3. Telephone and computer network planning ; where the vertices are network devices and the edges are the connections between them? Algorithm is used to find the shortest route to send data packets
13
Q

What is a linear search?

A

A search technique that looks through every single item of data until the search item is found; one at a time

[best for small datasets]

[Big O notation is O(n)]

13
What is a binary search?
A technique for searching data that works by splitting datasets in half repeatedly until the search data is found [eliminates half of the items you would need to search through immediately]
13
What is a binary tree search?
A technique that searches for the wanted item by traversing a binary tree
13
Why are binary tree searches used?
Because binary trees are often used in programs where data is dynamic meaning that data is constantly entering and leaving the tree. Therefore, the best and perhaps only way to find a data of item in the tree is to traverse it
14
What are the factors that determines which the best search algorithm to use? [3]
1. Space complexity; how much data being searched 2. Time Complexity 3. How the data is organised
14
What is Polish Notation?
A way of simplifying mathematical expressions developed in 1924, before computers was invented ; re-arranges the expression so that all of the operators are on the left and then operators are on the right [eg 7+3 becomes 73+]
14
What is Reverse Polish Notation?
An adaptation of of the polish notation; re-arranges the expression so that all the operators are on the right hand side of the operands . [eg 7+3 becomes 73+]
14
What are the advantages of Reverse Polish Notation?
14
14
15
15
16
17
17
18