Algorithm Design, Analysis & Complexity, Winter 2017
Was posted on March 17, 2017: problem statements.
Due on April 3, 2017, 11 am on MarkUs. Submit a PDF file with your solutions. NOTE: nonstandard day of the week.
Late submissions will not be accepted.
Marks posted on MarkUs on April 15, 2017
Legitimate regrade requests are due by 8PM on April 20, 2017
Clarifications: there used to be a typo in problem 3 in the definition of coloring --- it should be c : V -> [k], rather than c : E -> [k]. This typo was fixed on March 26, 2017.
Was posted on February 17, 2017: problem statements.
Due on March 10, 2017, 11 am on MarkUs. Submit a PDF file with your solutions.
Late submissions will not be accepted.
Marks posted on MarkUs on March 25, 2017
Legitimate regrade requests are due by 8PM on March 31, 2017
Clarifications: in problem 5 you may assume that the given maximum flow f is integral.
Was posted on January 18, 2017: problem statements.
Due on February 3, 2017, 11 am on MarkUs. Submit a PDF file with your solutions.
Late submissions will not be accepted.
Marks posted on MarkUs on February 18, 2017
Legitimate regrade requests are due by 11 am on March 2, 2017
Clarifications: in problem 2 you may not hash images, the only way you may access images is through the comparison interface A[i]==A[j].
In problem 2, divide and conquer refers to the most general form that also includes the case where the number of subproblems solved recursively is allowed to be 1.
In problem 5, running time of the form O(W^2 H^2 poly(n)) (EDIT: Feb 1, 2017) is okay, but the more efficient the better the grade (provided it is correct). Anything depending exponentially on n is going to get a grade of 0.