EECS 281 || with Complete Solutions.

EECS 281 || with Complete Solutions.
Runtime Factors correct answers Algorithm, Implementation, CPU/Memory Speed,
Compiler, Parallel Programs, Input Size

Primitive Operations correct answers Variable assignment, arithmetic operation, comparison,
array indexing, pointer reference, function call , function return

Amortized Complexity correct answers Time of average step in a sequence

Tail recursion correct answers Recursion that reuses the stack frame

Binary Search Recurrence Equation correct answers T(n) = T(n/2) + c

Binary Search Complexity correct answers O(log n)

Sequential Search Recurrence Equation correct answers T(n) = T(n-1) + c

Sequential Search Complexity correct answers O(n)

Tree Traversal Recurrence Equation correct answers T(n) = 2*T(n/2) +c

Tree Traversal Complexity correct answers O(n)

Selection/etc. Sorts Recurrence Equation correct answers T(n) = T(n-1) +c*n + c

Selection/etc. Sorts Complexity correct answers O(n^2)

Merge/Quick Sorts Recurrence Equation correct answers T(n) = 2T(n/2)+c*n+c

Merge/Quick Sorts Complexity correct answers O(n log n)

When can you not use the Master Theorem? (3 ways) correct answers If T(n) is not
monotonic, if T(n) is not a polynomial, if b cannot be expressed as a constant

2D Array Index = correct answers row * num_columns + column

2D Column = correct answers index % num_columns

2D Row = correct answers index / num_columns

Container Class Operations correct answers Constructor, Destructor, Add, Remove,
GetElement, GetSize, Copy, Assignment

Big 3 correct answers Destructor, Copy, Operator

Arrays vs Linked Lists correct answers Arrays better for smaller data items, wastes memory
if too large, Arrays require reallocation if too small, Linked lists allocate memory as needed,
but require memory for pointers