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 k·t(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 ¬y→x.
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 329–337. [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 710–719.
- Monien, Burkhard and Speckenmeyer, Ewald. Solving satisfiability in less than 2n steps. Discrete Applied Mathe-
matics, 10(3), 1985, pages 287–295.
- Storer, James A. On the complexity of chess. Journal of Computer and System Sciences, 1983, pages 77–100.
- 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 80–150 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
|
Excellent |
Satisfactory |
Inadequate |
|
|
Content (2 mark) |
Good coverage of key sup- porting concepts, explanations show a good understanding of the paper and its connection to material taught in this subject, additional supporting material beyond the initial paper used. |
Topic identified with reason- able coverage of key supporting concepts. Some ability to syn- thesise information from multi- ple sources (paper and core sub- ject material). |
Poor understanding of the cho- sen topic and its connection to the subject. |
|
Slides (1.5 marks) |
A good mix of images and text in the slides so the slides attract interest and are not too dense with information. |
Slides present a summary of the information, but may be too dense or don’t use images. |
Slides merely copy the com- mentary. |
|
Commentary (1.5 marks) |
Organisation is logical, with a clear sequence of ideas. Technical terms are used cor- rectly. Supporting informa- tion provided where appropri- ate. Commentary builds on and expands on the slides. |
Organisation follows the slides but doesn’t sufficiently expand on the material. Explanations are broadly correct, but may need more supporting informa- tion. |
Organisation is disconnected from the material in the slides. Information is provided indis- criminantly. |
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 (ekelareva@unimelb.edu.au) 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 University’s 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