Final Review Flashcards
What does it mean to say that a problem is in the complexity class P?
Solved in polynomial time by determinstic algorithms.
What does it mean to say that a problem is in the complexity class NP?
Solved in polynomial time by nondeterminstic algorithms.
What does it mean to say that a problem is NP-Complete?
List 3 NP-complete algorithms.
Its is NP Hard and NP.
- Graph Coloring
- Generalized minesweeper
- Travelling Salesman Problem.
Why do most computer scientists believe that these P and NP are not the same? What evidence do they have for this.
If you have the algorithm to solve on NP problem in polynomial time, you could solve all NP problems in polynomial time.
Evidence: No one was done it yet lol.
Name some greedy algorithms
Prim’s Minimal Spanning tree.
Fractional Knapsack
Huffman’s Compression Algorithm.
What is a, b, and d for the master’s theorm.
a = number of subproblems
b = sub-problem size
d = overhead price
When a priority queue is implemented using a binary heap, what is the complexity of insertion and removal.
Both O(log n) for insertion and removal.
When a priority queue is implemented using an unsorted array, what is the complexity of insertion and removal.
Insertion: O(1)
Removal: O(n)
Name 3 algorithms that use a priority queue.
- Huffman’s Compression Algorithm.
- Heap Sort
- Dikjstra’s
- Prim’s
What is the complexity of the traditional grade-school algorithm for adding two n-bit numbers?
O(n)
What is the complexity of the traditional grade-school algorithm for multiplying two n-bit numbers?
O(n^2)
What is the recurrence for the complexity of Karatsuba’s divide and conquer algorithm for multiplication two n-bit numbers?
T(n) = 3T(n/2) + n
What is the solution of Karatsuba’s recurrence in O notation as a function of n?
O(n ^ log2(3))
Most efficient algorithm for solving single source shortest path problem in an unweighted graph and its worst case complexity in a sparse graph.
Bread First Search
O(V+E)
Most efficient algorithm for solving single source shortest path problem in a graph with non-negative weights and its worst case complexity in a sparse graph.
Dijkstra’s
O(V log V)
