## Notices

#### Posted by Serge Gaspers Sunday 18 October 2015, 10:07:40 PM.

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.

#### Posted by Serge Gaspers Sunday 18 October 2015, 10:04:20 PM.

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).

#### Posted by Serge Gaspers Tuesday 13 October 2015, 04:17:52 PM.

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)!

#### Posted by Serge Gaspers Thursday 08 October 2015, 12:35:40 AM.

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)\$.

#### Posted by Serge Gaspers Saturday 03 October 2015, 07:34:02 AM, last modified Saturday 03 October 2015, 11:11:40 AM.

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.

#### Posted by Serge Gaspers Thursday 24 September 2015, 12:08:36 PM.

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.

#### Posted by Serge Gaspers Wednesday 02 September 2015, 04:38:25 PM.

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.

#### Posted by Serge Gaspers Thursday 20 August 2015, 12:30:39 PM.

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).

#### Posted by Serge Gaspers Tuesday 18 August 2015, 10:04:32 AM.

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.

#### Posted by Serge Gaspers Wednesday 05 August 2015, 09:47:02 AM.

Assignment 1 has been posted and is due on Tue 25 August 2015 at 11:59 PM.

#### Posted by Serge Gaspers Thursday 30 July 2015, 02:05:04 PM.

Lecture recordings are available here .

#### Posted by Serge Gaspers Tuesday 28 July 2015, 06:17:58 PM.

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.