Midterm Study Questions Flashcards
T/F
For any instance of the stable marriage problem with n men and n women, there are n! = n x (n-1) x … x 1 many possible perfect matchings.
TRUE
Proof idea:
We’ll prove this by induction on nn, the number of people of each gender that we are matching. Our base case will be n=1n=1, where it will be straightforward to show that the number of perfect matchings is 1!=11!=1. We will assume that for a set of n=k−1n=k−1 people of each gender, the total number of possible perfect matchings is (k−1)!(k−1)!. Then we will use our assumption for n=k−1n=k−1 to show that with one more man and one more woman, that our number of possible perfect matchings is k×(k−1)!=k!k×(k−1)!=k!.
Proof details:
Base case: n=1n=1 :there is one perfect matching of 1 man and 1 woman: (m,w)(m,w). (Note that 1!=11!=1.)
As the induction hypothesis, assume that for n=k−1n=k−1, the number of perfect matchings is =(k−1)!=(k−1)!.
Now consider the case n=kn=k. Consider a man m1∈Mm1∈M. There exists kk possible matches for m1m1 (to {w1,w2,…,wk}{w1,w2,…,wk}). Regardless of the choice for m1m1, k−1k−1 men and k−1k−1 women remain to be matched. We know from the inductive hypothesis that there are (k−1)!(k−1)! perfect matchings for this set of remaining people. The total number of matchings, then, is: k×(k−1)!=k!,k×(k−1)!=k!, as desired.
T/F Consider f(n) = loglogn and g(n) = 10^10^10^10. Then f(n) is O(g(n)).
FALSE g(n) is a constant (albeit a large one) and does not increase with n. f(n) does (slowly) increase with n. Thus, for some large enough n, g(n) <= f(n) and thus, g(n) is O(f(n)), not the other way around.
T/F Consider f(n) = n^n and g(n) = 2^400n. Then f(n) is omega(g(n)).
TRUE
Note that f(n) = 2^nlog2n and since nlog2n >= 400n for n>= 2^400, f(n) >= g(n) for every n, which by definition implies that f(n) is omega(g(n))
T/F
There is an algorithm that sorts n numbers a1,…,an where ai is within {0,1} for each i within [n] in O(n) time.
TRUE
Consider the following algorithm. Do a scan through a1,…,an and count the number of i within [n] such that ai=0. Let this number be n0. Then output n0 0’s followed by n-n0 1s.
T/F
BFS is a linear time algorithm.
Recall that an algorithm is a linear time algorithm if it runs in time O(N) on inputs of size N.
TRUE
Recall that we have shown that BFS runs in time O(m+n) when the graph is represented in the adjacency list format. Further, in the adjacency list format N= Theta(n+m) which implies the run time is O(N).
T/F
For any graph, there is a unique BFS tree for it.
FALSE
Consider the cycle on four vertices: v1, v2, v3, v4 such that (vi,vi+1) for 1<=i<=3 and (v4,v1) are edges. Consider a BFS run that starts from v1. Note that v3 can be discovered from either v2 or v4 and each choice leads to a different BFS tree.
T/F
Every directed graph on n vertices with at least n-1 edges is connected.
FALSE
Consider the following DAG on three vertices A,B,C with directed edges (A,B), (B,C), (A,C). In this graph C is not connected to A but it has n=3 edges.
T/F
Given a graph on n vertices in its adjacency matrix, there is an O(n^2) time algorithm to convert it into its adjacency list representations.
TRUE
In short here is an algorithm: go through the matrix row by row and for the vertex u corresponding to the current row, add a list of vertices w such that the entry for (u,w) is a 1. Each row takes O(n) time and there are n rows, which makes for a total running time of O(n^2).
T/F
Given n numbers a1,…,an such that for every i∈[n]
(we will use [n] to denote the set of integers {1,…,n}) we have ai∈{0,1}. That is, we are given n numbers each of which is a bit. Then we can sort these n numbers in O(n) time.
TRUE
It can literally be done in O(n)
We can start a loop which goes till length and a variable, last which is a reference to the last index, and a new array arr which is empty. we iterate over the array, if it’s a 1, we add it to arr at last and reduce the index of last. if it’s a 0, we just add it to arr from front. so in n iterations, well get a sorted array.
As inserting at a specified index in an array is a O(1) operation,
O(n.1) = O(n)
T/F
In every Stable Matching problem instance where a man m and woman w have each other as their least preferred partner, the following is true. There is no stable matching for the instance where (m,w) are matched.
(Note by a stable matching problem instance, we mean both the set of men and women as well as all the 2n preference lists.)
FALSE
Its false because if a particular man and woman's preferred person are all taken in by someone with a higher preference than them and they are all stable, that man and woman will be paired and it will be a stable marriage.
For clarity here is a proof of this:
m1(w1,w2,w3)
m2(w2,w3,w1)
m3(w1,w2,w3)
w1 (m1,m2,m3) w2 (m2,m1,m3) w3 (m1,m2,m3) [(m1,w1)(m2,w2)(m3,w3)] both man 3 and woman 3 are last in each others preference list but this matching is stable as everyone was already taken by heir most preferred match leaving m3 and w3 to only be paired with each other.
T/F
Every correct algorithm in the worst case on inputs of size N needs to read all the N items in the input.
FALSE
1. Because the worst case simply means that on a set of input the maximum number of times the algorithm runs to give an output. The number of times an algorithm runs may not be equal to input size as seen in case of a binary search where we always divide the set into two parts which leads to a worst case runtime of log(n) and not n.
OR
- Consider the problem where the input is an array of length n and the algorithm has to output the first entry in the array: O(1) time.
T/F If f(N) is O(g(N)), then 2^f(N) is O(2^g(N)).
FALSE
f(n)=n and g(n)=n/2.
2^f(n)=2^n and 2^g(n)=2^(n/2) =√(2^n). Hence, 2^f(n) is not O(2^g(n)).
T/F
Every directed graph on n vertices that has no cycles has at most n−1 edges.
FALSE
There are no cycles and there are more than n-1 edges.
T/F
For any connected graph G=(V,E) there is always a start vertex s∈V, such that there is always at least two distinct BFS trees possible when starting the BFS at s.
Note: Recall (and remember this for the quizzes and exams) that if not specified a graph by default is always undirected.
IDK
