practice_exam_2018-solutions

COSC 1105/1107 - Computing Theory Mock Exam (100 marks) Page 1 of 4 DISCLAIMER: This is a mock exam for practice purposes only. It may not represent the real exam, may have mistakes, or under- developed solutions. Doing well/bad on this exam does not guarantee success/failure on the real exam. The sample questions do not cover the entire course examination syllabuses. Students are strongly advised to study each and every part of the syllabus. Use this exam to find your strengths and weaknesses and to see how long it takes to do certain problems. One of the main obstacles of any CT exam is time management. Questions are not worth equal marks; attempt the easiest questions first. GOOD LUCK! Question 1; ComPlexity . .. ..ottt e et e e e e e 15 marks (a) (3 marks) Briefly explain the difference between approximation and heuristic algorithms. In which problems would you use such algorithms? Solution: An approximation algorithm is one that solves a simpler problem than the original and provides answers that may not be solutions but are “close” to being solutions. A heuristic algorithm always returns a correct solution and takes reasonable amount of time for most inputs. Such algorithms are used for problems which are intractable. (b) (2 marks) It is known that 3SAT is an NP-complete problem. What does that mean? Solution: It means that it is in NP and it is also NP-hard. Being in NP means there is a NDTM that solves the problem in poly time; being in NP-hard means that every NP problem can be reduced (in poly time) to 3SAT. (¢) (2 marks) Can a decision problem be NP-hard but not in NP? Briefly explain your answer. Solution: Yes, NP-hard requires only that all NP problems be reduced to the problem of concern. For example, a problem can be in EXPTIME and still be NP-hard but beyond NP, because no poly-time NDTM that can solve it. (d) (4 marks) Prove that 4SAT is NP-complete. Solution: We must show that 4SAT is in NP and in NP-hard. 4SAT is in NP: build a NDTM that first guesses (non- deterministically) a truth valuation for each: variable and then checks, in poly time, that it makes the whole 4SAT formula true. 4SAT is NP-hard (reduce 3SAT to 4SAT): given a 3SAT formula c, build formula o by extending each clause in o with a copy of an existing literal in the clause. Formula o has 4 literals in each clause, and « is satisfiable iff o’ is satisfiable. (e) (4 marks) Prove thatif f(n) € O(g(n)), then 10 x f(n) € O(g(n)). Solution: We know that there exist ¢ and ng such that f(n) < ex g(n), forall n > ng. Then, 10x f(n) < 10x (ex g(n)), and s0 10 X f(n) < (10 x ¢) X g(n)). So, we take ¢/ = 10 x ¢ and it follows that 10 x f(n) € O(g(n)). Question 2: ChomsKy HIerarchy .. ... i i e et e et it et o niaeans 21 marks (2) Classify the languages below as either regular (R); context-free but not regular (CF); or recursively enumerable but not context-free (RE). You must give a brief (one sentence) justification of your choice. i. (2 marks) {a®h?ic% |i >0} Solution: RE. Have to match 7 twice so one stack won’t be enough. ii. (2 marks) {wicws | w1, we € {a,b}*} U {widwsy | w1, ws € {a,b}*} Solution: R. Union of two regular languages, equivalent to L((a|b)*(¢|d)(a|b)*) fuy (2 marks) {wewiws | w, w1, ws € (a|b)*, |w| # |wi| + |wal} Solution: CFE. A PDA can push X for each letter in w and pop for each in w; and ws, and stack must end non-empty. iii. — (b) For each of the following statements, is the statement true or fulse? Briefly explain each answer in one or two sentences. i. (2 marks) Regular expressions are as powerful as non-deterministic push-down automatas. Solution: False. Regular expressions are equivalent to NFAs, which are strictly less powerful than PDA. — ii. (2 marks) Context-sensitive languages can be recognised by a TM with semi-infinite tape. Solution: True. Context-sensitive languages can be recognised by a linear-bounded TM, and semi-infinite tapes do not add power to TMs. iii. (2 marks) Non-deterministic Turing Machines are more powerful than deterministic ones. Solution: False. Non-determininism do not add expressivity power to Turing Machines. iv. (2 marks) Context-sensitive grammars are more powerful than PDAs. Solution: True. CS grammars are equivalent to linear-bounded TMs which are strictly more powerful than PDAs. (7 marks) Show, using the Pumping Lemma, that the language L = {(a | ¢)"b™ | n < m} is not regular. Solution: Assume that L is regular. Then the Pumping Lemma applies, i.e. that 3n such that for all w € L with |w| > n,w = 1Yz, Yy # e, |vy| < nand zy*z € Lforall 1 > 0. Let w = a™b™*!. Then w € L and |w| > n, and so w = zyz. As |zy| < n, y is of the form o’ for some 1 < j < n. Hence zyyyz € L, i.e. a®T27b™*! € L, which is a contradiction, as 7 > 1. Hence L is not regular. (c S—’ COSC 1105/1107 - Computing Theory Mock Exam Page 2 of 4 Question 3: Nondeterministic Finite Automata (NFAS) ... ..ottt ans 23 marks Consider the NFA M below over the alphabet 3 of English letters. Note that € stands for the empty string. ._> 6 b 0%z ()—=()—{=) (a) (3 marks) Provide two strings accepted by M and one string rejected by M. Solution: See next question. (b) (3 marks) Describe informally the language L(A]) of M. Solution: Strings containing either the world “hello” or “hi” (c) (3 marks) Briefly explain how the language of Al changes if ¢3 is made a final state. Solution: Strings containing either the world “hello” or “hi”, or ending with “h”. (d) (6 marks) Using the subset construction, build a Deterministic Finite Automaton (DFA) for the language of M. You can use abbreviations on transitions, such as a-z or £ \ {h}. Solution: >\ {h} (e) (8 marks) A decimal number consists of: (A) an optional + or — sign; (B) a string of digits; (C) a decimal point; and (D) another string of digits.. Also, either the string of digits in (B) or (D) can be empty, but at least one of the two strings of digits must be nonempty. Finally, the decimal point appears if and only if the string of digits (D) is not empty. Draw the state diagram of an NFA which accepts decimal numbers. For example, the NFA should accept 132.424, 18888, and .87, but should reject 32.3.23, 187., and .98.1. You can use abbreviations such as 0-9 on transitions if you wish. Solution: Note that more compact (nicer) solutions exist.