Exam (elaborations)
Discrete Mathematics and Its Applications, 8th Edition by Rosen
- Course
- Institution
- Book
Discrete Mathematics and Its Applications, 8th Edition by Rosen
[Show more]
Connected book
Book Title:
Author(s):
- Edition:
- ISBN:
- Edition:
More summaries for
-
Discrete Mathematics and Its Applications, 8th Edition by Rosen
-
Discrete Mathematics and Its Applications, 8th Edition by Rosen
-
Complete Solution Manual Discrete Mathematics and Its Applications 8th Edition Questions & Answers with rationales (Chapter 1-13)
Seller
Follow
phinta004
Reviews received
Content preview
Test Bank for Discrete Mathematics and Its Applications, 8thEdition 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.
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller phinta004. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $17.99. You're not tied to anything after your purchase.
Can Stuvia be trusted?
4.6 stars on Google & Trustpilot (+1000 reviews)
78121 documents were sold in the last 30 days
Founded in 2010, the go-to place to buy study notes for 14 years now