COMPSCI 311 Midterm: CMPSCI 311 UMass Amherst mt2_prac1
31 Jan 2019
School
Department
Course
Professor
Document Summary
Instructions: answer the questions directly on the exam pages, show all your work for each question. Providing more detail including comments and expla- nations can help with assignment of partial credit: if you need extra space, use the back of a page, no books, notes, calculators or other electronic devices are allowed. Indicate whether each of the following statements is true or. In lectures we proved that p = n p . In any max ow in any graph, the ow along every edge equals the capacity. 1. 3 (2 points): given a graph, the size of the min vertex cover plus the size of the max independent set always equals the number of nodes. will not be covered. 1. 4 (2 points): the formula (x1 x2) ( x1 x2) has a satisfying assignment. 1. 5 (2 points): the nodes of a bipartite graph can always be colored with two colors such that endpoints of each edge get di erent colors.
