Solution Manual For Finite Mathematics and Its
Applications, 13 Edition by Larry J. Goldstein
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)
Applications, 13 Edition by Larry J. Goldstein
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)
