1. [5 marks] Give the big-Oh for the following functions:
(a) f (n) = 13n3 + 42n4 + 100n + 105
n
(b) f (n) = 1000n + 10n2 log (n) + log2 (n)
3
2
log (100n)
(c) f (n) = 100n
+ 100n
2n +
n3
2
(d) f (n) = 32n log (n) + 23n2 log (n)
n
2
n
(e) f (n) = 8 log2(n)2 + 16 2n2 + 32 2nn
2. Consider the following algorithm on a single-tape deterministic Turing machine that decides
the language L = {? ? {0, 1}? : ? = ? r }. I.e., all words that are palindromes
Main Loop: Sweep back and forth, comparing the end-points of the string and
removing them each round.
(1) Read the symbol, store value in state, write #, and move right.
(2) Sweep right until a # is encountered.
f there were no 0àor 1ì accept.
lse, move left one cell.
(3) Read the symbol to the left of the #.
f the symbol is not the same as the one read in Step (1), reject.
lse, write a # and move left.
(4) Read the symbol, store value in state, write #, and move left.
(5) Sweep left until a # is encountered.
f there were no 0àor 1ì accept.
lse, move right one cell.
(6) Read the symbol to the right of the #.
f the symbol is not the same as the one read in Step (4), reject.
lse, write a # and move rightŠ(a) [5 marks] Give the space complexity of this algorithm in big-Oh. Explain your answer.
(b) [5 marks] Give the time complexity of this algorithm in big-Oh. Explain your answer.
1
3. Consider the following algorithm on a RAM that decides language L = {? ? {0, 1}? : ? = ? r }.
nitialize r0 to 10 and r1 to 9
oop: Load the palindrome into the RAM into r10, r11, … r10 + n
ead symbol from input tape into r2
f r2 contains # break
ncrement r1

ove r2 into [r1]
oop: Verify palindrome
f r0 ? r1, accept
f [r0] 6= [r1], reject
ncrement r0
ecrement r1
(a) [5 marks] Give the space complexity of this algorithm in big-Oh. Explain your answer.
(b) [5 marks] Give the time complexity of this algorithm in big-Oh. Explain your answer.
Marking Scheme
1. Marking scheme for Question 1.
1 points
Correctness
Correct answer
0.5 points
Correct order, not big-Oh
0 points
Incorrect answer
2. Marking scheme for Question 2a, 2b, 3a, and 3b.
3 points
Correctness
Explanation
Correct
given
explanation
2 points
1 points
0 points
Correct answer
Correct order, not big-Oh
Incorrect answer
Mostly correct explanation
Somewhat correct explanation
Incorrect explanation
2

Purchase answer to see full
attachment