As you might know already, the final exam is on Thu 12 Nov 2015 from 08:45 am – 12:00 noon in room Mathews 307.
If you can use some results from the literature, there is no need to copy the proofs. Stating the results and giving a reference is enough. For example, the NP-completeness result from the following paper might be useful.
David Eppstein: Finding Large Clique Minors is Hard. J. Graph Algorithms Appl. 13(2): 197-204 (2009).
The final mark for this course will be computed as follows:
final_exam/2 + midterm/4 + (a1+2*a2+a3 - min(a1,a2,a3))/12
which is then rounded to the nearest integer (in your favour if the fractional part is 0.5) and capped at 100.
Good luck with the third assignment (for those of you who attempt it)!
In addition to the three changes announced a few days ago, in Question 5 of the theoretical assignment there will be no penalty for considering the parameter $k+\Delta^+(D)+\Delta^-(D)$ instead of $k+\Delta^+(D)$.
There are 3 changes to Assignment 2. The first two changes affect both the applied and the theoretical assignment and the third one affects the theoretical assignment.
1. The deadline is extended by 2 days, to Thursday, 8 October 2015, 23:59 AEST.
2. There is a new Bonus Question worth 10 bonus points: Show that, parameterized by |R| + maximum in-degree of D, Defendable Extension is not FPT, under standard complexity-theoretic assumptions, such as P is not equal to NP or FPT is not equal to W[1]. Defendable Extension is defined in the theoretical assignment, but the Bonus question counts for both the theoretical and the applied assignment.
3. Question 4 in the theoretical assignment is replaced by: Show that Defendable Extension parameterized by k + |R| + maximum in-degree of D is fixed-parameter tractable.
There is a small amendment to the permitted material for the final exam:
All textbooks and notes will be allowed.
In the survey, most students did not have a strong opinion about this, but some students, who base their learning principally on textbooks, strongly preferred access to textbooks. The only concern about having access to textbooks was that the difficulty of the exam might increase; I will ensure that this will not be the case.
See you on 7 October (there is no class next week), and I wish you a smooth completion of Assignment 2.
Please remember to bring your student card to the midsession quiz, which is next Wednesday at 1pm and lasts one hour. We have a normal lecture afterwards.
You can also bring printouts of all PDFs on the
Lectures page
, your own notes, and a UNSW approved calculator. Let me repeat that the trial midsession quiz is a very good preparation for the actual midsession quiz.
Several students asked about large inputs in Assignment 1. For instance, the size of the bit-representation of the numbers in Question 1 might be exponential in n, or the number of clauses in Question 2 might be exponential in n if we allow duplicate clauses. Note that in these cases, O(c^n) is polynomial in the instance size for any constant c.
Therefore, feel free to assume that the size of the encoding each number in Question 1 is at most n (so, they all have value at most 2^n) and that the problem instances in Question 2 have no duplicate clauses (Note that duplicate clauses can be removed in time polynomial in the instance size).
This is a friendly reminder that we will solve the exercise on Max 2-CSP in class tomorrow (see the end of the lecture notes on "3. Branching algorithms"). If you haven't done so yet, you might try and come up with a solution yourself before we see a solution in class.
Assignment 1 has been posted and is due on Tue 25 August 2015 at 11:59 PM.
Lecture recordings are available here .
Welcome to COMP6741.
The course outline and the lecture notes for Week 1 are available on the course website .
See you tomorrow at the first lecture.