Test Bank for Discrete Mathematics and Its Applications, 8th
Edition by Rosen, 9781259676512, Covering Chapters 1-13 |
Includes Rationales
When is a function g(n) in Big O of f(n)? - ANSWER: If there exists a c>0 and an N such that g(n)≤c*f(n)
for all n>N.
When is a function g(n) in Big Omega of f(n)? - ANSWER: If there exists a c>0 and an N such that
g(n)≥c*f(n) for all n>N.
When is a function g(n) in Big Theta of f(n)? - ANSWER: If there exist constants c1 > 0, c2 > 0, and N
such that c1|f(n)| ≤ |g(n)| ≤ c2|f(n)| for all n > N. This is the same as saying g(n)=O(f(n)) and
g(n)=Ω(f(n)).
When is a function g(n) in little o of f(n)? - ANSWER: If for every event c>0, there exists an N such that
g(n)≤c*f(n) for all n>N.
When is a function g(n) in little omega of f(n)? - ANSWER: If for every event c>0, there exists an N such
that g(n)≥c*f(n) for all n>N.
What is the harmonic series asymptotically equal to? - ANSWER: Θ(logn)
What does a computational problem consist of? - ANSWER: -A collection of inputs
-Output (a set of valid solutions)
What is an algorithm? - ANSWER: A step-by-step procedure such that given an input I, outputs are a
valid solution for I.
What is worse-case asymptotic running time? - ANSWER: -Is a feature of an algorithm, independent of
programming language, specific input and machine, that allows us to compare two different
algorithms for the same problem.
-An example is that an O(nlog(n)) time algorithm is better than an O(n^2) algorithm. So given a
computational problem, our goal is to find an algorithm with the smallest possible worst case
asymptotic runtime.
What is a bubble sort algorithm? - ANSWER: It is an algorithm to sort the array in the correct order by
comparing successive entries and swapping them if they are in the wrong order. This stops when all
are in the correct order.
What is the bubble sort algorithm pseudocode? - ANSWER: For i=1 to n−1:
For j=n down to i+1
If A[j−1] >A[j], THEN
X ← A[j − 1];·
A[j−1]←A[j];
A[j]←X;
What is the runtime of a bubble sort algorithm? - ANSWER: O(n^2)
What are divide and conquer algorithms? - ANSWER: A divide and conquer algorithm
-Divides the given problem into smaller subproblems
-Recursively solves each subproblem and,
-Combines the solution of these subproblems to get a solution for the original problem.
, What is a merge sort? - ANSWER: It is an algorithm that uses divide and conquer to place the array in
order.
-Need to divide the input and use mergesort on each one individually.
-Then for each sorted array, A1 and A1, you compare the first element from A1 to the first one from
A2 and place the smallest one first in the new array A (wlog let that one come from A1) then you
compare the other one to the next element in A2 and plase the smallest one as the second element in
A.
-Carry this on until you have run out of elements in one of the arrays and then fill the rest of the
places in A using those elements.
What is the psuedocode for merge? - ANSWER: i←1, j←1.
For r=1 to (k+t):
IF (i≤k) AND (j ≤t), THEN
IF B[i] ≤ C[j], THEN
D[r] ← B[i].
i ← i + 1.
ELSE
D[r] ← C[j].
j ← j + 1.
ELSE IF i > k, THEN D[r] ← C[j], j ← j + 1.
ELSE IF j > t, THEN D[r] ← B[i], i ← i + 1.
RETURN the array D[1,...,(k+t)].
What is the runtime of merge sort algorithm? - ANSWER: O(nlog(n))
What is the Master Theorem for solving Recurrences? - ANSWER: If T(n)=a*T(⌈n/b⌉) + O(n^d) for some
constants a > 0, b > 1, d≥0, and let T(c)=O(1) for any constant c>0, then
1. T(n)=O(n^d) if a/(b^d)<1
2. T(n)=O((n^d)*log(n)) if a/(b^d)=1
3. T(n)=O(n^(logb(a))) if a/(b^d)>1
What is binary search? - ANSWER: An algorithm to find a value in a sorted list where you check the
middle first, then cut the list in half depending on the value of the item. You repeat the process until
you find the value.
What is the run time of binary search? - ANSWER: O(logn)
What is a System of Direct Representatives? - ANSWER: Consider a universe X of elements, and n sets
A1,..., An⊆X.
An SDR in the set system is a collection {x1,...,xn}⊆X of n distinct elements s.t ∀i ∈[1,n], we have
xi∈Ai.
What is Hall's condition? - ANSWER: Consider a universe X and n sets A1,..., An ⊆X. This set system
satisfies Hall's condition iff ∀ k∈[1,n] and every collection of k indices {i1,..., ik} ∈[1,n], we have
IAi1UAi2U...UAikI≥k.
What is Hall's Theorem? - ANSWER: An SDR exists iff Hall's condition is satisfied.
What are graphs in graph theory? - ANSWER: G=(V,E) where V is the set of nodes (vertices) and E is
the set of edges.
When are two nodes u,v∈V adjacent? - ANSWER: Iff (u,v)∈E
What are the endpoints of an edge e? - ANSWER: The nodes u,v such that e=(u,v)∈E
If a node v∈V is an endpoint of an edge e∈E, then what are v and e? - ANSWER: They are incident.
Edition by Rosen, 9781259676512, Covering Chapters 1-13 |
Includes Rationales
When is a function g(n) in Big O of f(n)? - ANSWER: If there exists a c>0 and an N such that g(n)≤c*f(n)
for all n>N.
When is a function g(n) in Big Omega of f(n)? - ANSWER: If there exists a c>0 and an N such that
g(n)≥c*f(n) for all n>N.
When is a function g(n) in Big Theta of f(n)? - ANSWER: If there exist constants c1 > 0, c2 > 0, and N
such that c1|f(n)| ≤ |g(n)| ≤ c2|f(n)| for all n > N. This is the same as saying g(n)=O(f(n)) and
g(n)=Ω(f(n)).
When is a function g(n) in little o of f(n)? - ANSWER: If for every event c>0, there exists an N such that
g(n)≤c*f(n) for all n>N.
When is a function g(n) in little omega of f(n)? - ANSWER: If for every event c>0, there exists an N such
that g(n)≥c*f(n) for all n>N.
What is the harmonic series asymptotically equal to? - ANSWER: Θ(logn)
What does a computational problem consist of? - ANSWER: -A collection of inputs
-Output (a set of valid solutions)
What is an algorithm? - ANSWER: A step-by-step procedure such that given an input I, outputs are a
valid solution for I.
What is worse-case asymptotic running time? - ANSWER: -Is a feature of an algorithm, independent of
programming language, specific input and machine, that allows us to compare two different
algorithms for the same problem.
-An example is that an O(nlog(n)) time algorithm is better than an O(n^2) algorithm. So given a
computational problem, our goal is to find an algorithm with the smallest possible worst case
asymptotic runtime.
What is a bubble sort algorithm? - ANSWER: It is an algorithm to sort the array in the correct order by
comparing successive entries and swapping them if they are in the wrong order. This stops when all
are in the correct order.
What is the bubble sort algorithm pseudocode? - ANSWER: For i=1 to n−1:
For j=n down to i+1
If A[j−1] >A[j], THEN
X ← A[j − 1];·
A[j−1]←A[j];
A[j]←X;
What is the runtime of a bubble sort algorithm? - ANSWER: O(n^2)
What are divide and conquer algorithms? - ANSWER: A divide and conquer algorithm
-Divides the given problem into smaller subproblems
-Recursively solves each subproblem and,
-Combines the solution of these subproblems to get a solution for the original problem.
, What is a merge sort? - ANSWER: It is an algorithm that uses divide and conquer to place the array in
order.
-Need to divide the input and use mergesort on each one individually.
-Then for each sorted array, A1 and A1, you compare the first element from A1 to the first one from
A2 and place the smallest one first in the new array A (wlog let that one come from A1) then you
compare the other one to the next element in A2 and plase the smallest one as the second element in
A.
-Carry this on until you have run out of elements in one of the arrays and then fill the rest of the
places in A using those elements.
What is the psuedocode for merge? - ANSWER: i←1, j←1.
For r=1 to (k+t):
IF (i≤k) AND (j ≤t), THEN
IF B[i] ≤ C[j], THEN
D[r] ← B[i].
i ← i + 1.
ELSE
D[r] ← C[j].
j ← j + 1.
ELSE IF i > k, THEN D[r] ← C[j], j ← j + 1.
ELSE IF j > t, THEN D[r] ← B[i], i ← i + 1.
RETURN the array D[1,...,(k+t)].
What is the runtime of merge sort algorithm? - ANSWER: O(nlog(n))
What is the Master Theorem for solving Recurrences? - ANSWER: If T(n)=a*T(⌈n/b⌉) + O(n^d) for some
constants a > 0, b > 1, d≥0, and let T(c)=O(1) for any constant c>0, then
1. T(n)=O(n^d) if a/(b^d)<1
2. T(n)=O((n^d)*log(n)) if a/(b^d)=1
3. T(n)=O(n^(logb(a))) if a/(b^d)>1
What is binary search? - ANSWER: An algorithm to find a value in a sorted list where you check the
middle first, then cut the list in half depending on the value of the item. You repeat the process until
you find the value.
What is the run time of binary search? - ANSWER: O(logn)
What is a System of Direct Representatives? - ANSWER: Consider a universe X of elements, and n sets
A1,..., An⊆X.
An SDR in the set system is a collection {x1,...,xn}⊆X of n distinct elements s.t ∀i ∈[1,n], we have
xi∈Ai.
What is Hall's condition? - ANSWER: Consider a universe X and n sets A1,..., An ⊆X. This set system
satisfies Hall's condition iff ∀ k∈[1,n] and every collection of k indices {i1,..., ik} ∈[1,n], we have
IAi1UAi2U...UAikI≥k.
What is Hall's Theorem? - ANSWER: An SDR exists iff Hall's condition is satisfied.
What are graphs in graph theory? - ANSWER: G=(V,E) where V is the set of nodes (vertices) and E is
the set of edges.
When are two nodes u,v∈V adjacent? - ANSWER: Iff (u,v)∈E
What are the endpoints of an edge e? - ANSWER: The nodes u,v such that e=(u,v)∈E
If a node v∈V is an endpoint of an edge e∈E, then what are v and e? - ANSWER: They are incident.
