{"content":[{"text":"COSC-311 Fall 2018 Final Exam Topics \n This is not a comprehensive study guide. There may be topics that we have discussed in class \n or that have come up on homework that are not on this list. You are responsible for all of the \n course material up to this point, including both in-class material and homework. The exam \n is cumulative, and this study guide only includes topics from the last third of the course. \n Please refer to the study guides for Midterms 1 and 2 to remind yourself of earlier topics.","bbox":{"left":0.117647,"top":0.079248,"width":0.764704,"height":0.13356600000000002}},{"text":"1. Network Flow","bbox":{"left":0.141252,"top":0.228311,"width":0.13691800000000004,"height":0.01818900000000001}},{"text":"(a) Deﬁnitions: ﬂow, capacity and conservation constraints, residual graph, forwards and \n backwards edges, augmenting paths \n (b) Ford-Fulkerson algorithm: what it does, why it works \n (c) Max-ﬂow = min-cut theorem","bbox":{"left":0.175204,"top":0.25913,"width":0.707155,"height":0.08548699999999998}},{"text":"(a) Problems we’ve solved using network ﬂow: \n • Bipartite matching \n • Baseball elimination \n • Blood transfusions (on HW4) \n Complexity","bbox":{"left":0.165475,"top":0.361021,"width":0.38327199999999995,"height":0.12008000000000002}},{"text":"2.","bbox":{"left":0.141252,"top":0.462912,"width":0.014650999999999997,"height":0.01818900000000001}},{"text":"(a) Deﬁnitions: P, NP, polynomial-time reducibility, efﬁcient veriﬁcation, NP-hard, NP- \n complete \n (b) Reductions: what does it mean if Y ≤P X? what does this tell us about the relative \n hardness of X and Y ? \n (c) Reductions we’ve seen: \n • Independent Set ≤P Vertex Cover \n • Vertex Cover ≤P Independent Set \n • 3-SAT ≤P Independent Set \n • 3-SAT ≤P Graph Coloring \n • All problems Y in NP ≤P Circuit-SAT (and ex: Independent Set ≤P Circuit-SAT) \n • Circuit-SAT ≤P 3-SAT \n • 3-SAT ≤P Hamiltonian Cycle \n • Independent Set ≤P Set Packing (on HW5) \n • Set Packing ≤P Multiple Interval Scheduling (on HW5) \n • Something about Not-All-Equal-3-SAT and k-Cut (on HW5, part of the assign- \n ment involves choosing the correct direction for the reduction) \n (d) What to do if we need a solution to an NP-complete problem \n • Polynomial-time approximation schemes \n – MST-Approx for Traveling Salesman","bbox":{"left":0.175204,"top":0.49373,"width":0.707155,"height":0.4103049999999999}}],"images_bbox":[],"images_bbox_not_text_overlap":[]}