Fundamentals Flashcards
Explain: logbx = n
n is how often I need to multiply b by itself to get x
logbx = n
Name the most common runtimes.
- O(log(n))
- O(n)
- O(n * log(n))
- O(n2)
- O(n!)
Runtime of binary search?
O(log(n))
Runtime of linear search?
O(n)
Runtime of quicksort?
O(n * log(n))
Runtime of selection sort?
O(n2)
Runtime of traveling salesman problem?
O(n!)
How many permutations exist for n elements?
n!
What is recursion?
When a function calls itself.
Explain partially completed.
A function that calls another function is ‘paused’ until the called function returns. During this time its values are stored on the call stack in its own stack frame.
This “paused state” is called partially completed.
Name the two cases that need to be considered in a recursive function.
- Base case (for termination)
- Recursive case (loop)
It needs to be shown that the recursive case progresses towards the base case.
How are recursion and induction similar?
- both have a base case
- the recursive case corresponds to the inductive case
What is Divide-and-Conquer?
A recursive technique to solve algorithmic problems.
- Figure out a simple case as the base case
- Figure out how to reduce the problem to the base case
e.g. Quicksort
Name 1 Algorithm Design Strategy.
- Divide-and-Conquer
What is the runtime of Breadth-First-Search?
O(V + E)
How can you solve the shortest path problem?
Breadth-First-Search (BFS)
Describe how Breadth-First-Search works.
- Start at the start node/vertex
- If current node == search node => end
- Put current node in the visited set
- Enqueue all children of the current node that are not contained in the visited set in the to search queue
- If the search queue is empty return “not found”
- Dequeue the next node in the search queue and go to (2)
Name the most common FIFO data structure.
Queue.
Name the most common LIFO data structure.
Stack.
