Algorithms

Question 1

What is time complexity of an algorithm?

Answer 1

A measure of how long it takes an algorithm to run based on the size of the input.

Question 2

What is Big-O notation for?

Answer 2

Showing the time complexity of an algorithm, used in the form O(f(n)) where n is the input size.

Question 3

What are the search algorithms covered?

Answer 3

Linear search, binary search and binary tree search.

Question 4

How does linear search work?

Answer 4

By going through an array in order to find the wanted element.

Question 5

How does binary search work?

Answer 5

By starting in the middle of a sorted list and ignoring the half of the list that is all greater or less than the desired value.

Question 6

What is the time complexity of a linear search?

Answer 6

O(n).

Question 7

What is the time complexity of a binary search?

Answer 7

O(log n).

Question 8

What is a binary tree search?

Answer 8

Same as a binary search but a tree is used instead of a list.

Question 9

What are the sorting algorithms covered?

Answer 9

Bubble, insertion, merge and quick sort.

Question 10

What is bubble sort?

Answer 10

A sorting algorithm where you run through the list of items comparing values and moving the larger one up the list so that after each run the largest value is at the top of the list.

Question 11

What is insertion sort?

Answer 11

A sorting algorithm where items are moved from an unsorted array to a sorted array one item at a time.

Question 12

How does merge sort work?

Answer 12

The list is split into lots of sub-lists starting at length 1 which are sorted as they are joined together.

Question 13

What is the time complexity of bubble sort?

Answer 13

O(n^2).

Question 14

What is the time complexity of insertion sort?

Answer 14

O(n^2).

Question 15

What is the time complexity of merge sort?

Answer 15

O(n log(n)).

Question 16

How does quick sort work?

Answer 16

Select a pivot value from the list and place all values bigger than it in one list and all values smaller than it in another and carry out the algorithm again on each sub list until data is sorted. The placing of values into sub-lists is done by having a left and right marker, switching the values at the marker if rightleft move right down one.

Question 17

What is the time complexity of quick sort?

Answer 17

O(n log(n)).

Question 18

Advantages and disadvantages of quick sort?

Answer 18

Very fast, does not need additional memory like merge sort, however if the split points are towards the ends of the list the time complexity goes to O(n^2).

Question 19

Does depth first traversal of a graph use a stack or queue?

Answer 19

Stack as it records the order nodes were visited.

Question 20

Does breadth first traversal of a graph use a stack or queue?

Answer 20

Queue as the nodes are added in the order they were found so they are checked first for surrounding nodes.

Question 21

How does depth first graph traversal work?

Answer 21

By following a path of nodes until it can no longer continue and backtracking until there are available nodes again.

Question 22

How does breadth first graph traversal work?

Answer 22

All nodes adjacent to the current node are visited before moving to the next node.

Question 23

An example of use for a depth first traversal?

Answer 23

Finding a way out of a maze.

Question 24

An example of use for a breadth first traversal?

Answer 24

Shortest path algorithms, web crawlers.