[SOLVED] COMP90057 Advanced Theoretical Computer Science Assignment 2

COMP90057 Advanced Theoretical Computer Science

Assignment 2
Second (Spring) Semester 2017

Posted on LMS: Friday, 22 September 2017 Due: Friday, 13 October 2017 [9:00am]

Important: Your submissions for this assignment must be your own individual work. There is a further notice about this below. This document has two pages. Expect to spend about 10 hours on this assignment.

Questions
Part A (10 marks)

Question 1 (3 marks) Let M be a k-tape non-deterministic Turing machine that runs in time t(n). Show that there is some 2-tape non-deterministic Turing machine that decides L(M) in time proportional to kt(n).

Question 2 (4 marks) Let a subset of the nodes of a graph G be called a friendly set whenever every node is either in the subset or is adjacent to some node in the subset (or both). Let

FRIENDLY-SET = {G, k | G has a friendly set with k nodes} . Show that FRIENDLY-SET is NP-complete.

Question 3 (4 marks) Consider the language 2-SAT on propositional formulas in conjunctive normal form: { : has at most two literals per clause, and is satisfiable}

Show that 2-SAT is in P. Hint: A clause with two literals, such as x y can be expressed as two implications: x y and yx.

Part B (5 marks)

Your task is to prepare a five-minute presentation suitable for delivery to the COMP90057 class (but, regrettably, you are not going to have the opportunity to deliver it). The idea is to present to the class a new topic, that builds on what has been learned in the subject, and is relevant to the study of time and space complexity. Please focus your presentation on (part of) the material of one of the following papers, a copy of each of which is available on the LMS.

• Baetz, Bradley and Wood, David R. Brooks vertex-colouring theorem in linear time, 2014. arXiv:1401.8023.
• Eppstein, David. Improved algorithms for 3-coloring, 3-edge-coloring, and constraint satisfaction. Symposium on

  Discrete Algorithms (SODA), 2001, pages 329337. [arXiv cs/0009006 is a cleaner copy]

• Even, Shimon and Tarjan, Robert Endre. A combinatorial problem which is complete in polynomial space. Journal

  of the ACM (JACM), 23(4), 1976, pages 710719.

• Monien, Burkhard and Speckenmeyer, Ewald. Solving satisfiability in less than 2n steps. Discrete Applied Mathe-

  matics, 10(3), 1985, pages 287295.

• Storer, James A. On the complexity of chess. Journal of Computer and System Sciences, 1983, pages 77100.
• Walsh, Toby. Candy Crush is NP-hard. arXiv:1403.1911, 2014.

  Your submission for this Part should comprise a single PDF file that incorporates a maximum of five display slides, plus a narrative companion. The final slide is to be a reference list and needs no commentary. Each of the other slides requires a commentary of 80150 words. Note that a five-minute speech is at most 600 words! Your reference list would typically include two to six items.

  The Part B submission will be marked according to the following criteria, and it will be processed by Turnitin before being marked.

1

Submissions

Submit your answers to these assignment questions on the LMS. There are separate submission arrangements for Part A and Part B as described on the relevant page. Each file must be in .pdf format. You are expected to test for yourself that the document you submit can be printed! If necessary, carry out a trial run with a preliminary version of your submission.

For Part A, the submission should be prepared with standard word processing software or be a scan of a (neatly) handwritten document. The University offers scanning facilities for students. A raw photograph of a handwritten solution is not sufficient.

For Part B you should generate the file using standard office applications (i.e., scanned handwritten solutions are not acceptable). The Part B submission will be processed by Turnitin before being marked.

You may submit multiple versions of your solutions. Your final on-time submission will be the one that is assessed for the purpose of determining a mark. However, for the purpose of ensuring academic honesty, any material that is submitted, regardless of when it was submitted, or whether further or previous submissions were made, may be inspected and will be regarded as an attempt to submit that material for assessment.

Administrative issues

When is late? What do I do if I am late? The due date and time are printed on the front of this document. The lateness policy for this assignment, subject to CIS Department policies, is that ten percent of the available marks for this assignment are lost for each day (or part thereof) that the submission is late.

Should you decide to make a late submission, send an email directly to Elena Kelareva ([email protected]) no later than 24 hours before the due date and time and he will provide instructions for making a late submission.

Should you experience circumstances affecting your study, as soon as possible: consult the Universitys Assessment and Results Policy (MPF1326) and let the relevant lecturer know that you are experiencing such circumstances. The following page also has relevant pointers to information. http://ask.unimelb.edu.au/app/answers/detail/a_id/5667/~/applying-for-an-extension

What are the marks? Recall that this assignment is worth 15% of your final score. There is also a hurdle requirement: to pass this subject, you must earn at least 15 marks out of a subtotal of 30 for the assignments and in-class quiz.

Individual work You are reminded that your submission for this assignment is to be your own individual work. Where there is suspicion of plagiarism or collusion, the University policy and procedures for responding to academic misconduct will apply. The LMS submission process requires you to make a statement regarding academic honesty.

Finally We are here to help! Frequently asked questions about the assignment will be answered in the LMS discussion group. For confidential questions, please contact the lecturer directly.

Elena Kelareva
22 SEPTEMBER 2017

2