Section 12 - Algorithms Flashcards
Bubble Sort and Insertion Sort
Use a bubble sort to sort the following list:
[9, 5, 4, 15, 3, 8, 11]
Check online textbook for answer
Search 350 in page number
Bubble Sort and Insertion Sort
Use an insertion sort to sort the following list:
[9, 5, 4, 15, 3, 8, 11]
Check online textbook for answer
Search 352 in page number
Merge Sort and Quick Sort
Use a merge sort to sort the following list:
[5, 3, 2, 7, 9, 1, 3, 8]
Check online textbook for answer
Search 354 in page number
Merge Sort and Quick Sort
Use a quick sort to sort the following list:
[9, 5, 4, 15, 3, 8, 11]
heck online textbook for answer
Search 356-357 in page number
Bubble Sort and Insertion Sort
What is the definition of a bubble sort?
A sorting algorithm that repeatedly steps through the input list, element by element, comparing the current element with the one after it, and swapping their values if needed
Bubble Sort and Insertion Sort
What is the definition of an insertion sort?
A sorting algorithm that builds the final sorted array one item at a time via comparisons
Merge Sort and Quick Sort
What is the definition of a merge sort?
A comparison-based sorting algorithm that uses divide and conquer to break down the input list into smaller parts before merging them together
Merge Sort and Quick Sort
What is the definition of a quick sort?
A sorting algorithm that picks an element as a pivot and partitions the input array around the selected pivot by placing the pivot in its correct position in the sorted array
Searching Algorithms
When should a linear search be used?
When data is not in a particular sequence / order
Searching Algorithms
What is the time complexity of a linear search?
O(n)
Linear
Searching Algorithms
What is the definition of a binary search?
A search algorithm that repeatedly divides the data list in half, discarding the half that cannot contain the requested data, until there is only one item in the list
Searching Algorithms
What is the definition of a linear search?
A search algorithm where data items have to be searched one by one until the required one is found / the end of the list is reached
Graph-Traversal Algorithms
What is the difference between depth-first and breadth-first travsersal?
- A depth-first traversal uses a stack
- A breadth-first traversal uses a queue
//// - In depth-first traversal, we go as far down one route as we can before backtracking and taking the next route
- In breadth-first travseral, we first visit all the nodes adjacent to A before moving to B and repeating the process for each node at this ‘level’, before moving to the next level
Optimisation Algorithms
What is Dijksrta’s algorithm?
Dijkstra’s algorithm is designed to find the shortest path between one particular start node and all other nodes in a weighted graph
Optimisation Algorithms
What is the A* algorithm?
The A* algorithm focuses only on reaching the goal node
