DSA EXAM 1 QUESTIONS AND
ANSWERS
Base case - Correct Answers -which can be solved without recursion
Making progress - Correct Answers -each recursive call makes progress towards the
base case
Design rule - Correct Answers -assume recursive calls work without tracing it all out
Compound interest rule - Correct Answers -don't duplicate work already performed in a
previous call
Generic Objects - Correct Answers -we want to write a class that can store some data,
but we may wish to use it with different types
Double Hashing - Correct Answers -a second hash function is applied
Rehashing - Correct Answers -build another table twice as large and use a new hash
function to move everything from the original table to the new table
separate chaining - Correct Answers -the more lists there are, the shorter the lists will
be
autoboxing - Correct Answers -automatically inserts a wrapper
If a method has a parameter which accepts collections of type Person, could you pass it
a collection of type Student? - Correct Answers -No, because collections are not
covariant.
type erasure - Correct Answers -Generic classes are seen by the compiler but are
converted to regular classes (called raw classes) during compilation.
Comparator - Correct Answers -allows the comparison rule to be separate from the
object
algorithm - Correct Answers -a set of steps to solve a problem
, O Big O - Correct Answers -Upper bound (possibly equal).
Θ Theta - Correct Answers -Growth rates are equal.
Ω Omega - Correct Answers -Lower bound (possibly equal).
o Little o - Correct Answers -Upper bound (not equal).
log N - Correct Answers -Logarithmic
log^2 N - Correct Answers -Log-squared
N - Correct Answers -Linear
N^2 - Correct Answers -Quadratic
N^3 - Correct Answers -Cubic
2^N - Correct Answers -Exponential
For-loops - Correct Answers -Number iterations (n) times the statements inside
Nested for-loops - Correct Answers -Statements inside times the product of loop sizes
Consecutive statements add - Correct Answers -the maximum one is the one that
counts
If-else statements - Correct Answers -test plus the larger of the two branches
"Divide and Conquer" strategy runtime - Correct Answers -O(NLogN)
If an algorithm (repeatedly) takes constant time to reduce the problem size by a fraction,
its runtime is... ? - Correct Answers -O(logN)
If an algorithm (repeatedly) takes constant time to reduce the problem size by a
constant, its runtime is... ? - Correct Answers -O(N)
Binary Search runtime - Correct Answers -O(log N)
Euclid's Algorithm - Correct Answers -Finds greatest common divisor (gcd) of two
values.
O(log N)
abstract data type - Correct Answers -set of objects with a set of operations
ANSWERS
Base case - Correct Answers -which can be solved without recursion
Making progress - Correct Answers -each recursive call makes progress towards the
base case
Design rule - Correct Answers -assume recursive calls work without tracing it all out
Compound interest rule - Correct Answers -don't duplicate work already performed in a
previous call
Generic Objects - Correct Answers -we want to write a class that can store some data,
but we may wish to use it with different types
Double Hashing - Correct Answers -a second hash function is applied
Rehashing - Correct Answers -build another table twice as large and use a new hash
function to move everything from the original table to the new table
separate chaining - Correct Answers -the more lists there are, the shorter the lists will
be
autoboxing - Correct Answers -automatically inserts a wrapper
If a method has a parameter which accepts collections of type Person, could you pass it
a collection of type Student? - Correct Answers -No, because collections are not
covariant.
type erasure - Correct Answers -Generic classes are seen by the compiler but are
converted to regular classes (called raw classes) during compilation.
Comparator - Correct Answers -allows the comparison rule to be separate from the
object
algorithm - Correct Answers -a set of steps to solve a problem
, O Big O - Correct Answers -Upper bound (possibly equal).
Θ Theta - Correct Answers -Growth rates are equal.
Ω Omega - Correct Answers -Lower bound (possibly equal).
o Little o - Correct Answers -Upper bound (not equal).
log N - Correct Answers -Logarithmic
log^2 N - Correct Answers -Log-squared
N - Correct Answers -Linear
N^2 - Correct Answers -Quadratic
N^3 - Correct Answers -Cubic
2^N - Correct Answers -Exponential
For-loops - Correct Answers -Number iterations (n) times the statements inside
Nested for-loops - Correct Answers -Statements inside times the product of loop sizes
Consecutive statements add - Correct Answers -the maximum one is the one that
counts
If-else statements - Correct Answers -test plus the larger of the two branches
"Divide and Conquer" strategy runtime - Correct Answers -O(NLogN)
If an algorithm (repeatedly) takes constant time to reduce the problem size by a fraction,
its runtime is... ? - Correct Answers -O(logN)
If an algorithm (repeatedly) takes constant time to reduce the problem size by a
constant, its runtime is... ? - Correct Answers -O(N)
Binary Search runtime - Correct Answers -O(log N)
Euclid's Algorithm - Correct Answers -Finds greatest common divisor (gcd) of two
values.
O(log N)
abstract data type - Correct Answers -set of objects with a set of operations
