EECS 281: Midterm || with Actual Answers.
things that affect runtime correct answers the algorithm, implementation details,
CPU/memory speed, compiler (-g3 / -O3), other programs running in parallel, input size
things that affect rate of runtime growth correct answers primarily input size. Independent of
most other factors.
things that count as "one step" in a program correct answers variable assignment, arithmetic
operation, comparison, array indexing, pointer reference, function call (excluding data),
function return (excluding data)
steps taken during execution of a loop that executes n times correct answers 1 for
initialization, n + 1 for test, n for update, plus contents of loop
Big-O definition correct answers f(n) = O(g(n)) iff there are constants c > 0 and n0 > 0 such
that f(n) <= c * g(n) whenever n >= n0. Defines asymptotic upper bound.
Rules of thumb when determining if Big-O correct answers lower order terms can be ignored,
coefficient of the highest-order term can be ignored
Big-O sufficient correct answers if [(lim n -> infinity) (f(n) / g(n)) = d < infinity], then f(n) =
O(g(n)).
Big-Theta correct answers Defines asymptotic tight bound.
Big-Omega correct answers f(n) = [omega](g(n)) iff there are constants c > 0 and n0 > 0 such
that f(n) >= c * g(n) whenever n >= n0. Defines asymptotic upper bound.
Best-case performance correct answers when program executes the least number of steps,
given ideal input. (Example: data is found in the first place you look). Analysis performed
over inputs of a given size.
Worst-case performance correct answers when program executes the most number of steps,
given ideal input. (Example: data is found in the land place you could possibly look) Analysis
performed over inputs of a given size.
Average-case performance correct answers when program executes the average number of
steps required, given any input.
amortized complexity correct answers alternative way to measure the cost of an operation.
Excess steps from expensive operations averaged out over the cheap operations; total cost is
essentially constant.
analytical method to measure complexity correct answers involves analysis of the code itself
and recognizing common algorithms and patterns Based on a recurrence relation
empirical method to measure complexity correct answers involves measuring runtime
programmatically / using external tools (e.g. C++ timers). Tests are run on inputs of a variety
of sizes
, profiling tool correct answers a tool which measures where a program spends its time (e.g.
perf)
explanations if empirical results for runtime are worse than predictions correct answers error
in complexity analysis, error in implementation (e.g. extra loop, unintended operations)
explanations if empirical results for runtime are better than predictions correct answers
experiment may not have fit worse case scenario, error in complexity analysis, error in
analytical measurements, incomplete algorithm implementation, algorithm implemented is
better than one analyzed
explanations if empirical results for runtime matches asymptotic prediction but runs too slow
correct answers performance bug, -O3 not used, more optimizations needed to improve the
constant factor
recurrence relation correct answers describes the way a problem depends on a subproblem.
We can write for a computation, or for the time taken.
substitution method for solving recurrences correct answers 1. Write out T(n) = ... + T (n - 1)
+ ... + T (n - 2) + ...
2. Substitute T(n-1), T(n-2) with equation for T(n)
3. Look for a pattern
4. Use a summation formula
makefile correct answers a file that specifies at set of compilation rules that makes compiling
a lot easier
valgrind correct answers a tool that is used to detect undefined behaviors (e.g. use of
uninitialized values, out-of-bounds reads, out-of-bounds writes, memory leaks)
getopt_long correct answers a function that is used to automate command line parsing
vec.resize(new_size) correct answers changes size of a vector, and it's capacity if needed
vec.reserve(new_capacity) correct answers changes capacity of a vector
behavior of vec.push_back(val) when size exceeds capacity correct answers all existing
values are copied to vector of twice the capacity, original vector is deleted
behavior of program stack when function call is made correct answers all local variables are
saved on stack, and argument values are pushed onto the stack
behavior of program stack when function call is received correct answers function arguments
are popped off the stack
behavior of program stack when return is issued within the function correct answers the
return value is pushed to the program stack
things that affect runtime correct answers the algorithm, implementation details,
CPU/memory speed, compiler (-g3 / -O3), other programs running in parallel, input size
things that affect rate of runtime growth correct answers primarily input size. Independent of
most other factors.
things that count as "one step" in a program correct answers variable assignment, arithmetic
operation, comparison, array indexing, pointer reference, function call (excluding data),
function return (excluding data)
steps taken during execution of a loop that executes n times correct answers 1 for
initialization, n + 1 for test, n for update, plus contents of loop
Big-O definition correct answers f(n) = O(g(n)) iff there are constants c > 0 and n0 > 0 such
that f(n) <= c * g(n) whenever n >= n0. Defines asymptotic upper bound.
Rules of thumb when determining if Big-O correct answers lower order terms can be ignored,
coefficient of the highest-order term can be ignored
Big-O sufficient correct answers if [(lim n -> infinity) (f(n) / g(n)) = d < infinity], then f(n) =
O(g(n)).
Big-Theta correct answers Defines asymptotic tight bound.
Big-Omega correct answers f(n) = [omega](g(n)) iff there are constants c > 0 and n0 > 0 such
that f(n) >= c * g(n) whenever n >= n0. Defines asymptotic upper bound.
Best-case performance correct answers when program executes the least number of steps,
given ideal input. (Example: data is found in the first place you look). Analysis performed
over inputs of a given size.
Worst-case performance correct answers when program executes the most number of steps,
given ideal input. (Example: data is found in the land place you could possibly look) Analysis
performed over inputs of a given size.
Average-case performance correct answers when program executes the average number of
steps required, given any input.
amortized complexity correct answers alternative way to measure the cost of an operation.
Excess steps from expensive operations averaged out over the cheap operations; total cost is
essentially constant.
analytical method to measure complexity correct answers involves analysis of the code itself
and recognizing common algorithms and patterns Based on a recurrence relation
empirical method to measure complexity correct answers involves measuring runtime
programmatically / using external tools (e.g. C++ timers). Tests are run on inputs of a variety
of sizes
, profiling tool correct answers a tool which measures where a program spends its time (e.g.
perf)
explanations if empirical results for runtime are worse than predictions correct answers error
in complexity analysis, error in implementation (e.g. extra loop, unintended operations)
explanations if empirical results for runtime are better than predictions correct answers
experiment may not have fit worse case scenario, error in complexity analysis, error in
analytical measurements, incomplete algorithm implementation, algorithm implemented is
better than one analyzed
explanations if empirical results for runtime matches asymptotic prediction but runs too slow
correct answers performance bug, -O3 not used, more optimizations needed to improve the
constant factor
recurrence relation correct answers describes the way a problem depends on a subproblem.
We can write for a computation, or for the time taken.
substitution method for solving recurrences correct answers 1. Write out T(n) = ... + T (n - 1)
+ ... + T (n - 2) + ...
2. Substitute T(n-1), T(n-2) with equation for T(n)
3. Look for a pattern
4. Use a summation formula
makefile correct answers a file that specifies at set of compilation rules that makes compiling
a lot easier
valgrind correct answers a tool that is used to detect undefined behaviors (e.g. use of
uninitialized values, out-of-bounds reads, out-of-bounds writes, memory leaks)
getopt_long correct answers a function that is used to automate command line parsing
vec.resize(new_size) correct answers changes size of a vector, and it's capacity if needed
vec.reserve(new_capacity) correct answers changes capacity of a vector
behavior of vec.push_back(val) when size exceeds capacity correct answers all existing
values are copied to vector of twice the capacity, original vector is deleted
behavior of program stack when function call is made correct answers all local variables are
saved on stack, and argument values are pushed onto the stack
behavior of program stack when function call is received correct answers function arguments
are popped off the stack
behavior of program stack when return is issued within the function correct answers the
return value is pushed to the program stack
