UIT2201: CS & the IT Revolution
Tutorial Set 12 (Spring 2008)

(D-Problems discussed on Thursday, 17-Apr-2008)
(No Q-Problems, YEAH!!)

Practice Problems: (not graded)
(If you have difficulties with these, please see your classmates or the instructor for help.)

T12-PP1: (Simple TM programs)
(a) Practice Prob 2 on Section 11.3 of [SG3].
(b) Practice Prob 3 of Section 11.5 of [SG3].
(c) Problem 8,13 on Chapter 11 of [SG3] (Prob 7,12 of [SG2]).

Discussion Problems: -- Prepare (individually) for tutorial discussion.

(IMPORTANT NOTE: When writing TM algorithms (eg: D3, Q'1, Q'2), include comments for each instruction or related group of instructions. The comment should convey information in terms of the algorithm the TM is accomplishing. (See examples of these comments in the TM algorithms given in Sect. 11.5 for Bit Inverter, Parity Bit and Unary Incrementing.)

T12-D0: (FunQ ) Why was minor censorship done on your responses to Quiz 2 Fun Question?

T12-D1: (TM) Problem 10 of Chapter 11 of [SG3]. (Problem 9 of [SG2])

T12-D2: (TM) Problem 16 of Chapter 11 of [SG3]. (Problem 15 of [SG2])

T12-D3: (TM) Problem 17 of Chapter 11 of [SG3]. (Problem 16 of [SG2])

Review: (Review of Topics 4-6)
You can freely ask question on the topics tested in Quiz 2.

No Q-problems to hand in this week!
(Note: But some Q-like problems for you to try on TM. For this tutorial, I call them Q'-questions. No need to turn in solutions for Q'-questions.)

T12-Q'1: (TM) Problem 24 of Chapter 11 of [SG3]. (Problem 23 of [SG2])
(Note: This is related to the previous one (Problem 17).)

T12-Q'2: (10 points) (TM)
Problem 24 of Chapter 11 of [SG2]. (Problem 25 of [SG3])

T12-Q'3: (10 points) (TM, modified from past final exam.)
Draw a state diagram for a Turing machine that takes a binary string as input and inverts all the bits in the string—that is, changing the 0s to 1s and the 1s to 0s (as in a bit inverter seen in the lectures) and also append an odd parity bit at the end of the inverted string. (The output string consists of the inverted input string and an extra parity bit. The output string has odd parity.) 

       sample input string:   ...b01101b... 
      sample output string:   ...b100101b...

A-Problems: OPTIONAL Challenging Problems for Further Exploration

A11: (Cross-linking ideas and exponential time algorithms.)
(a) You are given a bit-array B = (b[n-1], b[n-2], ... b[1] b[0]), where each b[i] is 0 or 1. Given an algorithm for incrementing B by 1.
(b) Suppose you are given a set A = {A1, A2, ..., An} of n objects, and a subset X of A. How can we use the bit-vector B to represent the subset X?
(c) Using (a) and (b) above, or otherwise, give a simple algorithm to generate all subsets of A.
(d) What is the running time of your algorithm?
[Note: Recall that there are 2n subsets altogether. (A proof is provided by (a) and (b) above.)]

UIT2201: CS & IT Revolution; (Spring 2008); A/P Leong HW