Use LEFT and RIGHT arrow keys to navigate between flashcards;
Use UP and DOWN arrow keys to flip the card;
H to show hint;
A reads text to speech;
15 Cards in this Set
- Front
- Back
what is the number of ways you can put n items in a row?
|
Number of orderings of n elements is:
n! |
|
what is the number of ways you can pick k items out of n?
|
Number of k-subsets of n elements is:
n!/[k!(n-k)!] |
|
What is the number of subsets of a set of size n?
|
Number of subsets of n elements is:
2^n |
|
What is the number of ways you can assign k colors to the vertices of a graph?
|
Number of k-colorings of a graph is:
k^n |
|
What is the number of ways you can match up n boys to n girls?
|
Number of ways to match n boys to n girls is:
n! |
|
What is the algorithm for putting n items in a row?
|
S = {s1,s2,s3....sn}
For i=1 up to n, DO - Pick an item from set S to go in position i - Delete that item from the set S |
|
What is the algorithm for the number of subsets of a set of size n?
|
S = {s1,s2,s3....sn}
For i=1 up to n, DO -Decide if you will include si |
|
What is the algorithm for k-coloring a graph?
|
Let G have vertices v1,v2,....vn
For i=1 up to n, DO -pick a color for vertex vi |
|
What is the algorithm for matching n boys and girls?
|
Let the boys be B1,B2...Bn and girls be G1,G2..Gn. Initially, all girls available.
For i=1 up to n, DO -Pick a girl for a boy Bi from the set of available girls. Remove the girl from the set of available girls. |
|
What is the algorithm for picking k items out of n?
|
S = {s1,s2,s3....sn}
For i=1 up to n, DO -Pick an item from S to include in set A -Delete that item from the set S |
|
What is the algorithm for a two pile rock game?
|
M(i,j):
-1 if M(i-1,j-1) or M(i-1,j) or M(i,j-1) is 2 -2 otherwise |
|
f(n) is O(g(n)) if
|
f(n)≤cg(n) for all n≥C'
|
|
Give the common order of function for Big O analysis
|
from smallest to largest:
O(1) constant O(log n) logarithmic O((log n)^c) polylogarithmic O(n) linear O(n log n) loglinear O(n^2) quadratic O(n^c) polynomial O(c^n) exponential O(n!) factorial O(n^n) n to the n |
|
What is the number of k-subsets of a set S=(s1,s2...sn) in which s1 and s2 are adjacent?
|
2(n-1)!
|
|
What is the number of k-subsets of a set S=(s1,s2...sn) in which s1 and s2 are not adjacent?
|
n!-2(n-1)!
|