2.3 Algorithms

Question 1

What is the Big O Notation?

Answer 1

A measure of the complexity of an algorithm.

Question 2

State all the Big O Notations from worst to best in terms of efficiency.

Answer 2

O(n!) - Factorial
O(2^n) – Exponential
O(n^2) – Polynomial
O(n) – Linear
O(log n ) – Logarithmic
O(1) – Constant

Question 3

Which Big O Notation has the smallest complexity?

Answer 3

O(1) – Constant

Question 4

Which Big O Notation has the largest complexity?

Answer 4

O(n!) - Factorial

Question 5

What is the definition of Dijkstra’s Shortest Path?

Answer 5

An algorithm for finding the shortest path between nodes in a graph.

Question 6

What are some key facts of Dijkstra’s Shortest Path? ( 3 points)

Answer 6

• Originally depth first (Finds quickest route to one node
• Then it finds the distances to all nodes
• It is iterative

Question 7

What are the steps of Dijkstra’s Algorithm? (6 points !)

Answer 7

1. Set distance to first node to 0. Set all others to infinity.
2. Record the distance from first node to all connected nodes. Mark first node as visited.
3. Repeat this until done:
   1. Pick next unvisited node with smallest distance.
   2. Record the distance from this node to all connected nodes.
   3. Mark as visited, record the last node we visited.

Question 8

What is the definition of the A* Algorithm?

Answer 8

A graph traversal algorithm that finds the shortest path between two nodes using heuristics

Question 9

A* vs Dijkstra’s, Advantages and Disadvantages comparing them:

Answer 9

A*

+ Only finds route to chosen mode.

+ More efficient if good heuristic chosen.

• Heuristic must be calculated.

Dijkstra’s

+ Finds distance to all nodes.

• Slower/ less efficient.

+ Guaranteed to find the best solution.

Question 10

What is a Linear search and what is its complexity?

Answer 10

A searching algorithm that checks all items in order.
Time Complexity: O(n)
Space complexity is constant O(1)

Question 11

Why should you use Linear search?

Answer 11

List doesn’t need to be sorted.

Can be very quick (if you’re lucky)

Doesn’t require additional memory.

Question 12

How does a linear search work? ( 3 points)

Answer 12

Iterate through all items.

When sough item found, record index.

Return index.

Question 13

What is a Binary Search and what is its complexity?

Answer 13

A divide and conquer algorithm that splits data until it finds the sought item.
Complexity: O(log n)

Question 14

What are some key facts of the Binary Search?

Answer 14

List must be sorted.

Scales very well with large data sets

Doesn’t require extra memory

Runs on a loop ( not recursion)

Question 15

What is the Quick Sort Algorithm and what is its complexity in both the normal and worst case?

Answer 15

A recursive, divide and conquer algorithm that sorts a list
Time Complexity: O(n log n)
Time Worse Case: O(n^2)
Space is O(log n)

Question 16

What is a pivot?

Answer 16

A chosen point in a list. We aim to have all larger numbers to the right and all smaller numbers to the left.

Question 17

What are some key facts of Quick Sort Algorithm? ( 3 points)

Answer 17

• Recursively splits the list until the length is 1
• Requires a little extra memory space ( not as much as merge sort)
• It’s Very quick

Question 18

What is the Bubble sort and what is it’s time and space complexity?

Answer 18

A sorting algorithm that swaps pairs of data until a list is in order.

Time complexity – polynomial O(n^2)
Space complexity – Constant O(1)

Question 19

How does the bubble sort work? ( 3 points)

Answer 19

• Looks at every number in the array
• Swaps the numbers
• Checks if one of the numbers is greater than another

Question 20

What is an insertion sort and what is it’s time and space complexity?

Answer 20

A sorting algorithm that sorts data by placing items into a new list in the correct order

Time complexity – polynomial O(n^2)
Space complexity – Constant O(1)

Question 21

What is the Merge Sort what is it’s time and space complexity?

Answer 21

A recursive, divide and conquer algorithm that sorts a list

Time – Logarithmic O(n * log n)
Space – Linear O(n)

Question 22

How does the Merge Sort work?

Answer 22

• Divides lists into two sub-lists until the length is 1
• Combines sub-lists together in order

Question 23

Merge sort vs Bubble sort, Advantages and Disadvantages comparing them:

Answer 23

Merge Sort

• Scales Well
• Good for large data set
• Uses sub-lists so requires more memory space

Bubble Sort

• Easy to Code
• Uses a temporary variable when swapping
• Fast on small data sets

Question 24

What is a Stack?

Answer 24

A last in first out( LIFO)
A data structure usually used to store instructions

TIP:
[Think of water going through a pipe and coming out the other side]

Question 25

What is the call stack?

Answer 25

A structure to hold the active subroutines and their data

Question 26

What is abstract data structure?

Answer 26

A data structure made by the programmer

Question 27

What is a Queue?

Answer 27

A static, first in first out structure for ordering data.

TIP:
[Think of a store, first come first served]

Question 28

What does enQueue(item) do?

Answer 28

Adds an item to the rear of the list

Question 29

What does deQueue() do?

Answer 29

Removes the item from the front of the list

Question 30

What does isEmpty()/ isFull() do?

Answer 30

Checks if the list is empty/full