CMPS 102 Practice Midterm 3 June 01, 2017 Quiz 3 on June 07, 2019; counts like the other midterms.
1 Estimating Sums, Recurrences (Big Θ)
Mainly, similar in format to midterms 1 and 2. The Master Theorem will be stated, as it has been.
MASTER THEOREM, ETC. — OK TO TEAR THIS PAGE OFF.
As on midterm 1 and midterm 2.
2 NP Completeness (8–16 pts)
Multiple-choice questions about definitions: NP, NP-complete, reduction.
Also, what is known and what is unknown, about relationships between NP, NP-complete, and P (the polynomial-time problems).
What are some well-known problems like Satisfiability, Independent Set, Vertex Cover, Clique, Graph Coloring, Hamiltonian Cycle, Set Cover, Hitting Set.
You should know boundaries between versions of a problem that are NP-complete and those that are polynomial.
That is, if budget part of the input is T what values of T make the problem NP-complete and what values of T permit polynimial solutions?
3 Network Flow and Min Cut (20–40 pts)
Algorithm problems like those on 5th homework.
Identify a minumum-weight cut.
Multiple-choice questions about Ford-Fulkerson and Edmonds-Karp and minimum-weight cuts may be asked as well.
4 Bipartite Matching (10–15 pts)
Show knowledge of the alternating path algorithm by following the steps to find a maximum bipartite matching.
Three copies of the bipartite graph are given so you can clarify the order in which you do steps. Write comments for further clarifications, if needed.
Proceed in alphabetical order to match a vertex on the left (if possible) that is so-far unmatched.
A1A1A1
@@@@ @@@@ @@@@
@ @ @
B2B2B2 H @ H @ H @
HH @ HH @ HH @
HHH @ HHH @ HHH @ H@ H@ H@
HH@ HH@ HH@ @@@
C H3 C H3 C H3
H H H
HH HH HH
HHHHH HHHHH HHHHH
H H H H H H
D4D4D4
@@@ @@@ @@@
@ @ @ @@@
E @5E @5E @5
H H H
HH @ HH @ HH @
HHH@@ HHH@@ HHH@@
HH @ HH @ HH @
H H H @@@
H H H
F6F6F6