Unit 12 - Algorithms Flashcards

You may prefer our related Brainscape-certified flashcards:
1
Q

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

A
  • 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)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What is time complexity and space complexity?

A

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

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

What is Big-O notation?

A

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

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

How are linear searches performed?

A
  • 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

What are the advantages and disadvantages of the linear search?

A

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

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

How are binary searches performed?

A

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)

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

What are the advantages and disadvantages of a binary search?

A

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

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

How are bubble sorts performed?

A

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

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

What are the advantages and disadvantages of the bubble sort?

A

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)

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

How are merge sorts performed?

A

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

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

What are the advantages and disadvantages of the merge sort?

A

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

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

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

How are insertion sorts performed?

A

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

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

What are the advantages and disadvantages of the insertion sort?

A

Adv.
-?

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

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

How are quick sorts performed?

A

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

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

What are the advantages and disadvantages of the quick sort?

A

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

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

How is Djikstra’s Algorithm performed?

A

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

17
Q

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

A
18
Q

How is the A* Algorithm performed?

A
19
Q

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

A
20
Q

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

A
  • 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