Algorithm Design, Analysis & Complexity, Fall 2017
Posted November 13, 2017: Assignment 3 .
Note that the new due date is Monday, December 4 at 10:00 AM. Note: Question 5 had a typo in that the formula is a CNF formula and the connective should have been a conjunction ^ and not a disjunction v.
Solution skteches will be found here.
Posted October 23, 2017: Assignment 2 is now complete..
Note: The points for each of the questions and subquestions has been clarified.
Solution skteches can be found here. Note My initially posted solution for Q5(a) was incorrect. I then provided a dynamic programming algorithm. Then a student sent me his correct greedy solution for this problem. I also corrected a typo in Q2(a) As stated on piazza and in class, since I made a mistake, everyone gets the 10 points for Q5(a). If you said "I don't know, you get a 2 point bonus. If you procided a correct solution with proof, you get a bonus of 10 points.
Posted on September 14, 2017: Assignment 1.
Note question 3, part (a) has been re-formulated. Also there was a typo in qustion 6. The objective is to maximize V(\sigma).
Solution skteches can be found here..