CSE 347 Analysis of Algorithms
Homework 7: More Practice with NP-Completeness
NP-Completeness代写 This homework must be completed and submitted electronically. Formatting standards, submission procedures, and (optional)…
This homework must be completed and submitted electronically. Formatting standards, submission procedures, and (optional) document templates for homeworks may be found at
https://classes.engineering.wustl.edu/cse347/ehomework/ehomework-guide.html
Advice on how to compose homeworks electronically, with links to relevant documentation for several dif- ferent composition tools, may be found at
https://classes.engineering.wustl.edu/cse347/ehomework/composing-tips.html
Please remember to NP-Completeness代写
- typesetyour homework;
- includea header with your name, 6-digit student ID, and the homework number at the top of each page;
- includeany figures (typeset or hand-drawn) inline or as floats;
- uploadand submit your PDF to Gradescope before class time on the due date;
- selectthe pages corresponding to each problem after uploading the PDF.
Always show your work. NP-Completeness代写
- SolveKleinberg and Tardos, Problem 19. Note that you have to prove whatever you answer for each part.
- Professor Papageno is offering two sections of his class, “Brain Surgery for Poets.” He has N studentssigned up for the class and must place each student in exactly one of the two sections. To avoid having very imbalanced sections, the professor wants to place students so that no one section gets all the freshmen, all the women, all the engineers, etc.
To generalize, let S be the set of all students signed up for the class. the professor has identified k groups G1 . . . Gk ⊆ S, each of size at least two, and he wants to allocate the members of S to sections so that every group Gi has at least one member in each section.
Show that it is NP-complete to decide whether such an allocation exists. I suggest that you reduce from the known-to-be-NP-complete problem Not-All-Equal-3SAT : given a 3CNF formula ψ, is there a satisfying assignment for ψ in which at least one literal of each clause is false? (You don’t need to prove NAE-3SAT itself NP-complete – it’s actually a bit tricky to do so.) NP-Completeness代写
