Question: [38] Consider the stronger offline deterministic Turing machine model with a two-way read-only input tape. Given an l l matrix A, with l =

[38] Consider the stronger offline deterministic Turing machine model with a two-way read-only input tape. Given an l × l matrix A, with l = n/ log n and element size O(log n), arranged in row-major order on the two-way (one-dimensional) input tape,

(a) Show that one can transpose A (that is, write AT on a work tape in row-major form) in O(n log n) time on such a Turing machine with two work tapes.

(b) Show that it requires Ω(n3/2/
√log n) time on such a Turing machine with one work tape to transpose A.

(c) From Items

(a) and (b), obtain a lower bound on simulating two work tapes by one work tape for the machines.
Comments. Source: [M. Dietzfelbinger, W. Maass, and G. Schnitger, Theoret. Comput. Sci., 82:1(1991), 113–129].

Step by Step Solution

There are 3 Steps involved in it

1 Expert Approved Answer

Step: 1 Unlock blur-text-image

Question Has Been Solved by an Expert!

Get step-by-step solutions from verified subject matter experts

Step: 2 Unlock

Step: 3 Unlock

Students Have Also Explored These Related Elementary Probability For Applications Questions!

Let r and s be solutions to the quadratic equation x 2 b x + c = 0. For n N, define d0 = 0 d1 = r s dn = b dn1 c dn2 (n 2) Prove that dn = r n s n for all n N. [4 marks] (b) Recall that a commutative...

can someone solve this Modern workstations typically have memory systems that incorporate two or three levels of caching. Explain why they are designed like this. [4 marks] In order to investigate...

CST.20assign data Extract = dataStore; endmodule (a) What would be suitable comments on the behaviour of the code at points "comment A" to "comment D"? [4 marks] (b) In the synthesised...

Let A, B be sets. Define: (a) the Cartesian product (A B) (b) the set of relations R between A and B (c) the identity relation A on the set A [3 marks] Suppose S, T are relations between A and B, and...

A certain program has to maintain an array, count, of N counters which are all initialised to zero. The value of counter i can be incremented by one by the call: increment(i), and this is the only...

Briefly describe ASCII and Unicode and draw attention to any relationship between them. [3 marks] (b) Briefly explain what a Reader is in the context of reading characters from data. [3 marks] A...

QUIZ... Let D be a poset and let f : D D be a monotone function. (i) Give the definition of the least pre-fixed point, fix (f), of f. Show that fix (f) is a fixed point of f. [5 marks] (ii) Show that...

For monotone functions f, f0: P Q between posets (P, vP ) and (Q, vQ), let f v f(i) Prove that the binary relation v is a partial order. [3 marks] (ii) For monotone functions between posets p : P 0...

List three specific parts of the Case Guide, Objectives and Strategy Section (See below) that you had the most difficulty understanding. Describe your current understanding of these parts. Provide...

multiple choice questions from 32-41 32. This question consists of an assertion (statement) in the left-hand column and a reason in the right-hand column Assertion Reason Chlorine will cause iodine...

4. A block of mass m is attached to a wall by a massless spring, as shown. The spring is initially neither stretched nor compressed, and there is no friction between the block and the surface. At...

Describe who is suing who and for what? And why? What rights are being violated? Such as due process and equal protection.....quote text from the attached file to support the explanation... the...

Brendan borrows $ 1 5 0 , 0 0 0 from Countywide Credit Union to buy a home. The loan is a fixed - rate mortgage at 5 . 5 percent with a thirty - year term secured by Brendan s home, which is his...

a. Financial statements should aid the user of the statements in making decisions. In your opinion, would the user of the statements be aided if there were a distinction between financial reporting...