T Naughton, CS NUIM, Back to SE307 home

Remove everything from your desk except pens/pencils. Paper will be provided. Answer all questions. You have 100 minutes in total. Answer Section A first. After 40 minutes you will be given the Section II questions.

Use the usual web-based simulator for Section A. Your programs will be graded by running them at the end of the lab (after 100 minutes). Full marks for a fully working solution, half marks for a partial solution, one tenth marks for a very poor attempt.

Use the MCQ answer sheet for Section B. Write both your name and student id. number the MCQ sheet. Each MCQ question has only one fully correct option. Negative marking will be enforced: +1 for a correct answer, -0.25 for an incorrect answer, 0 for a non attempt. This means that randomly guessing answers will average a mark of zero.

Hand up all material, including a printout of your program at the end of the exam. Ensure your name appears on everything.

Section A – Turing machine programming (40% of total test marks)

Q1 Write a Turing machine to double a unary number. Initially the TM head will be at the beginning of the input. At halt, the TM head must be at the beginning of the output. For example, input "11" would be transformed into "1111".

Q2 Write a Turing machine to divide a unary number by two (rounding down). Initially the TM head will be at the beginning of the input. At halt, the TM head must be at the beginning of the output. For example, input "1111" would be transformed into "11", and input "111" would be transformed into "1".

Section B – Computability (60% of total test marks)

Q1 Who invented the Turing machine?

(a) Alan Mathison Turing
(b) N. P. Completeness
(c) E. Post
(d) The halting problem
(e) None of the above

Q2 Who did not invent the Turing machine?

(a) Alan Turing
(b) A. M. Turing
(c) Turing
(d) Alan Mathison Turing
(e) None of the above

Q3 The theory of computation has at its foundations the concept of (I) leading to that of (II) and to that of (III) problem. (I), (II), and (III), in that order, could be

(a) computability, algorithm analysis, an algorithmically solvable
(b) a model of computation, a formal algorithm, an efficient
(c) efficiency, algorithm analysis, an effectively computable
(d) all of the above
(e) none of the above

Q4 The theory of computational complexity has at its foundations the concept of (I) leading to that of (II) and to that of (III) problem. (I), (II), and (III), in that order, could be

(a) algorithm analysis, efficiency, an effectively solvable
(b) computational resources, an efficient algorithm, a computationally tractable
(c) efficiency, algorithm analysis, an effectively computable
(d) all of the above
(e) none of the above

Q5 Computational complexity theory aims to

(a) introduce classes of problems that have similar complexity (require a similar quantity of computational resources)
(b) study the intrinsic properties of complexity classes
(c) identify algorithmic feasibility and efficiency
(d) two from (a) through (c)
(e) all of (a) through (c)

Q6 Measurement of something requires a comparison. What scale do we use for algorithms?

(a) sample inputs
(b) attributes such as worst/best/average performance
(c) ensuring a correct algorithm
(d) all of the above
(e) an infinite number of algorithms requires an infinite number of scales in the worst case

Q7

Q8 When n doubles

(a) log n increments
(b) a linear function in n doubles
(c) a quadratic function in n quadruples
(d) a quadratic function in n squares
(e) an exponential function in n squares

Q9 Which of the following functions has the largest growth rate?

(a) n^1/2
(b) n^1/10
(c) n¹⁰⁰
(d) 2^n/2
(e) 2^n!

Q10 The `strongest' of the following statements we can make about the sum 1 + 2 + 3 + ... + n is

(a) = O(n²)
(b) = ¹/₂ n² + O(n)
(c) = O(n²) + O(n)
(d) = O(n²) - n
(e) = n² + O(n)

Q11 The sum 1² + 2² + 3² + … + n² = ¹/₃n (n + ¹/₂)(n + 1) would also be

(a) = O(n³)
(b) = ¹/₃n + O(n³)
(c) = O(n⁴)
(d) all of the above
(e) none of the above

Q12 We can reduce our number of unique tape symbols in a TM table of behaviour by

(a) increasing the size of the set of symbols
(b) writing more symbols on the tape
(c) increasing the number of states of mind
(d) a method requiring both (b) and (c)
(e) either (b) or (c)

Q13 The minimum number of states we can reduce our set of states of mind to without changing the functionality of any possible TM is

(a) 0
(b) 1
(c) 2
(d) greater than 2
(e) no limit

Q14 The minimum number of symbols we can reduce our set of symbols to without changing the functionality of any possible TM is

(a) 0
(b) 1
(c) 2
(d) greater than 2
(e) no limit

Q15 Which of the following are not one of the `unrestricted' models of computation?

(a) TMs with only one tape
(b) k-tape TMs with a finite set of symbols
(c) k-tape TMs whose tapes are infinite in one direction only
(d) RAMs with fixed sized registers
(e) none of the above