CSCI 3333 final
Call Kai
Learn
Practice Test
Spaced Repetition
Match
Flashcards
Knowt Play1/27
There's no tags or description
Looks like no tags are added yet.
Name | Mastery | Learn | Test | Matching | Spaced | Call with Kai |
|---|
No analytics yet
Send a link to your students to track their progress
28 Terms
(13 points) Basic Knowledge 1 What is the big-Oh run time of Merge Sort on n items?
O(n log n)
What is the big-Oh run time of Heap Sort on n items?
O(n log n)
What is the big-Omega lower bound for comparison based sorting of n items?
O(n log n)
What is the worst case big-Oh run time to insert 1 item into an AVL-tree that contains n items?
O(log n)
What is the worst case big-Oh run time to insert 1 item into a min-heap?
O(log n)
What is the worst case big-Oh run time to remove the minimum value from a min-heap?
O(log n)
What is the run time of breadth-first search (in terms of IVI and IEI)?
O(IVl+IEI)
What is the run time of Dijkstra's algorithm (in terms of I VI and IEI) assuming a min-heap based implementation?
O((IVI + IEI) log IVI)
What is the run time of Dijkstra's algorithm (in terms of IVI and IEI) assuming a Fibonacci-heap based implementation?
O(IVI log IVI + IEI)
What is the run time of the Bellman-Ford single-source shortest path algorithm (in terms of IVI and IEI)?
O(IVI • IEI)
What is the run time of the Floyd-Warshall "all-pairs" shortest path algorithm (The one that uses dynamic programming)?
O(IVl^3)
What is the run time of the Edmonds-Karp maximum flow algorithm?
O(IVI • IEl^2)
log(n) = O(n)
T
n = O(log n)
F
log^2 (n) = O(n)
T
n = O( log^2 n)
F
log(n) = Ω(n)
F
n = Ω(log n)
T
5n^3 + 7n + 13 = O(n^5)
T
5n^3 + 7n + 13 = Ω(n^5)
F
5n^3 + 7n + 13 = Ω(n)
T
log(n!) = Θ( nlog(n) )
T
n^(1/2) = O( log n)
F
2^n = Ω( n! )
F
bool hasPathSum(node* p int sum) {
if(p == nullptr) return false //Base Case //leaf node: check if remaining sum equals this node’s value If(p -> left == nullptr && p-> right == nullptr) Return sum == p-> data; Return hasPathSum(p-> left
Write a method ‘levelOrderTraversal
Void levelOrderTraversal(node * r){
If(r == nullptr) return;
Queue q; qpush(r);
while(!q.empty()){
node* curr = q.front();
q.pop();
cout << curr -> data << “ “;
if(curr -> left) q.push(curr -> left);
if(curr -> right) q.push(curr ->right); } }
Int numEntries(node * p}
If(p == nullptr) return 0; Int count = p->marked If (p -> marked){ count = 1; } For (int i = 0; i < 256; i++){ if(p-children[i] != nullptr){ Count += numEntries(p->children[i])); } } Return count; }