Unit 12 - Algorithms

Question 1

What are the properties of a good algorithm? (4/6)

Answer 1

• has clear steps
• produces a suitable output for every input
• allows for invalid inputs
• will always terminate
• should execute in as few steps as possible
• others should understand and be able to modify (if necessary)

Question 2

What is time complexity and space complexity?

Answer 2

Time complexity: a measure of the time taken for an algorithm to complete, given as an upper bound to ensure the algorithm’s performance is predictable and scalable

Space complexity: a measure of the amount of memory space an algorithm uses, which accounts for the space needed for the input and the space needed for the algorithm’s code

Question 3

What is Big-O notation?

Answer 3

A measurement of how the runtime or space requirements of an algorithm grow as the input size grows

Question 4

How are linear searches performed?

Answer 4

• Start with the first item
• If this item is not the target item, continue moving sequentially through the list until the target is found
• If this item is the target item, then the target has been found and the search terminates

Question 5

What are the advantages and disadvantages of the linear search?

Answer 5

Adv.
- Easy to program
- Easy to understand
- Easy to trace
- List does not need to be sorted

Disadv.
- Takes n comparisons in the worst case scenario
- Has time complexity of O(n) which is worse than the binary search time complexity

Question 6

How are binary searches performed?

Answer 6

1) Take a sorted list as an input
2) Check the middle item in the list
3) If this is the target item, the search terminates and the item is returned
4) If this is not the target item, the item and the target are compared
5) If the item is smaller than the target, the item and all items smaller than it are discarded
6) If the item is larger than the target, the item and all items larger than it are discarded
7) This process is repeated until the target or found or if there are no items left (target is not in the list)

Question 7

What are the advantages and disadvantages of a binary search?

Answer 7

Adv.
- Time complexity O(log n) which is very good
- Suited to large data sets

Disadv.
- Harder to program
- Harder to trace
- List must be sorted

Question 8

How are bubble sorts performed?

Answer 8

1) Start with the first item in a list
2) Compare this item with the next one
3) If the first item is bigger/smaller (depends on ascending/descending order) than the next item, then swap the items
4) If not, then do not change the items
5) Continue comparing pairs of items until the end of the list, where the largest/smallest (depends on ascending/descending order) will be at the final position
6) After this first pass, continue iterating through the list and comparing items until the list is sorted

Question 9

What are the advantages and disadvantages of the bubble sort?

Answer 9

Adv.
- Easy to understand and trace
- Easy to program
- Constant space complexity O(1), since all changes are within the same list
- O(n) time complexity in the best case scenario (list is mostly sorted)

Disadv.
- Average time complexity of O(n^2)

Question 10

How are merge sorts performed?

Answer 10

1) A list is recursively broken down into smaller sublists until each sublist contains only a single item
2) Each sublist is merged together with its adjacent list while being sorted. The items in the sublist are compared and inserted into their sorted position.
3) Sublists are repeatedly merged and sorted until they form a single list with the sorted items

Question 11

What are the advantages and disadvantages of the merge sort?

Answer 11

Adv.
- Efficient for large arrays
- Time complexity of O(n log n)

Disadv.
- Difficult to program
- Used more memory (because of recursion)

Question 12

How are insertion sorts performed?

Answer 12

1) A list is logically partitioned into sorted and unsorted parts
2) The list is iterated through and each item is inserted into the sorted list
3) Items are compared with each item in the sorted list, starting from the first until it finds an item greater than it
4) This is repeated until there are no more items in the unsorted part

Question 13

What are the advantages and disadvantages of the insertion sort?

Answer 13

Adv.
-?

Disadv.
- Time complexity of O(n^2)

Question 14

How are quick sorts performed?

Answer 14

1) Select the first element in a list as the pivot
2) Go through each item after the pivot and place numbers smaller than the pivot behind it in the order they appear
3) The pivot now becomes fixed in place

Question 15

What are the advantages and disadvantages of the quick sort?

Answer 15

Adv.
- O(n log n) time complexity

Disadv.
- high memory use (due to recursion)
- time complexity in worst case is O(n^2)
- difficult to program

Question 16

How is Djikstra’s Algorithm performed?

Answer 16

1) Initialise two tables called visited nodes and unvisited nodes with the columns node, distance, previous
2) All distances should be filled with an arbitrarily large number (infinite) as a placeholder value, except for the source node which has distance 0
3) Find the node with the smallest distance and see which other nodes it connects to
4) Check the distance between the current and each connected node
5) If this distance is less than the connected node’s stored distance, then replace it with the smaller value
6) Replace the value in the connected node’s previous node column with the current node
7) If the distance is greater than or equal to the connected node’s stored distance, then continue to the next node
8) Repeat for all connected nodes then move the current node to the visited nodes table
9) Repeat this process for every node in the graph until all nodes have been moved to the visited nodes table
10) The shortest distances can be read from the visited nodes table using backtracking

Question 17

What are the advantages and disadvantages of Dijkstra’s algorithm?

Question 18

How is the A* Algorithm performed?

Question 19

What are the advantages and disadvantages of the A* Algorithm?

Question 20

What are the differences between Dijkstra’s and the A* algorithms?

Answer 20

• Dijkstra’s finds the shortest distance between a start node and all other nodes; A* finds the shortest distance between only two nodes
• Dijkstra’s doesn’t use heuristics; A* does