Sorting
What method do Merge Sort and Quicksort use to sort?
A: Divide and Conquer
What property does Stack use?
A: FILO /LIFO
What are the 3 Cases for Master's Theorem?
A: Case 1 if a<1
Case 2 if a=1
Case 3 if a> 1
What symbol/ name do we use for Worst Case?
A: Big O
What is Inheritance?
A: Having a derived class be able to use functions from a superClass.
What is the Worst Case for QuickSort?
A: O(n^2)
What property does Queue use ?
A: FIFO/LILO
What is the complexity of T(n) = .5T(n-4) + n
A: n
What symbol/ name do we use for Best Case?
A: Big Omega
What functions do we typically use in classes?
A: Constructor,Destructor, Setters/getters
What is the 3rd pass of Bubble Sort:
Array: [9,2,4,5,12,5 17]
A: [2,4,5,9,5,12,17]
[2,4,5,5,9,12,17]
[2,4,5,5,9,12,17]
What functions does Queue use?
A:enqueue dequeue, Is empty
What is the complexity of T(n) = T(n-6) + n^2
A: n^3
What symbol/ name do we use for Average Case?
A: Big Theta
How can we organize class variables/ functions?
A: We can use public,protected and private
What is the 3rd pass of Selection sort:
Array: [9,5,32,1,0,35,5]
A [0,5,32,1,9,5]
[0,1,32,5,9,5]
[0,1,5,32,9,5]
What functions does Stack use?
A:push pop top, Is empty
What is the complexity of T(n) = 4T(n-1) + n
A: n 4^n
What Strategy can we use to solve recurrence relation?
A: Typically we substitute T(n__) until we see a pattern
What does a pointer hold?
A: Memory address
What is the 3rd pass of Insertion Sort:
Array: [9,7,6,15,16,5,10,11]
A: [7,9,6,15,5,1610,11]
[6,7,9,15,5,16,10,11]
[5,6,7,9,15,16,10,11]
If we insert HELLO in a stack and a queue, what will each output?
A: Stack: OLLEH
Queue: HELLO
What equation do we use for Decreasing of T(n) = aT(n/b) + f(n)
(n) = O(nklogpn)
FInd the Recurrence Relation:
fun(x){
if(x>0){
for(int i=0;i<x;i++){
cout<< x<<endl;
}
}
func(n-1)
A: T(n-1) + 2n+2 or T(n-1)+n
What is the difference between pass by reference and pass by value?
A:in pass by value, values are copied to another variable and terminates after function
In pass by reference, we pass the memory address of a variable therefore after the function that variable can be changed.