2.3 Algorithms Flashcards
What is the Big O Notation?
A measure of the complexity of an algorithm.
State all the Big O Notations from worst to best in terms of efficiency.
O(n!) - Factorial
O(2^n) – Exponential
O(n^2) – Polynomial
O(n) – Linear
O(log n ) – Logarithmic
O(1) – Constant
Which Big O Notation has the smallest complexity?
O(1) – Constant
Which Big O Notation has the largest complexity?
O(n!) - Factorial
What is the definition of Dijkstra’s Shortest Path?
An algorithm for finding the shortest path between nodes in a graph.
What are some key facts of Dijkstra’s Shortest Path? ( 3 points)
- Originally depth first (Finds quickest route to one node
- Then it finds the distances to all nodes
- It is iterative
What are the steps of Dijkstra’s Algorithm? (6 points !)
- Set distance to first node to 0. Set all others to infinity.
- Record the distance from first node to all connected nodes. Mark first node as visited.
- Repeat this until done:
- Pick next unvisited node with smallest distance.
- Record the distance from this node to all connected nodes.
- Mark as visited, record the last node we visited.
What is the definition of the A* Algorithm?
A graph traversal algorithm that finds the shortest path between two nodes using heuristics
A* vs Dijkstra’s, Advantages and Disadvantages comparing them:
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.
What is a Linear search and what is its complexity?
A searching algorithm that checks all items in order.
Time Complexity: O(n)
Space complexity is constant O(1)
Why should you use Linear search?
List doesn’t need to be sorted.
Can be very quick (if you’re lucky)
Doesn’t require additional memory.
How does a linear search work? ( 3 points)
Iterate through all items.
When sough item found, record index.
Return index.
What is a Binary Search and what is its complexity?
A divide and conquer algorithm that splits data until it finds the sought item.
Complexity: O(log n)
What are some key facts of the Binary Search?
List must be sorted.
Scales very well with large data sets
Doesn’t require extra memory
Runs on a loop ( not recursion)
What is the Quick Sort Algorithm and what is its complexity in both the normal and worst case?
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)
What is a pivot?
A chosen point in a list. We aim to have all larger numbers to the right and all smaller numbers to the left.
What are some key facts of Quick Sort Algorithm? ( 3 points)
- 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
What is the Bubble sort and what is it’s time and space complexity?
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)
How does the bubble sort work? ( 3 points)
- Looks at every number in the array
- Swaps the numbers
- Checks if one of the numbers is greater than another
What is an insertion sort and what is it’s time and space complexity?
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)
What is the Merge Sort what is it’s time and space complexity?
A recursive, divide and conquer algorithm that sorts a list
Time – Logarithmic O(n * log n)
Space – Linear O(n)
How does the Merge Sort work?
- Divides lists into two sub-lists until the length is 1
- Combines sub-lists together in order
Merge sort vs Bubble sort, Advantages and Disadvantages comparing them:
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
What is a Stack?
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]
What is the call stack?
A structure to hold the active subroutines and their data
What is abstract data structure?
A data structure made by the programmer
What is a Queue?
A static, first in first out structure for ordering data.
TIP:
[Think of a store, first come first served]
What does enQueue(item) do?
Adds an item to the rear of the list
What does deQueue() do?
Removes the item from the front of the list
What does isEmpty()/ isFull() do?
Checks if the list is empty/full
