Input : Adjacency-list representation of Directed acyclic graph (Boolean circuit). see Complexity theory by Arora and bark, page no- 104

Find : Adjacency matrix representation of DAG (Boolean circuit).

My attempt :

Let us assume that DAG has $n$ vertices.

First of all create a $n \times n$ table for adjacency matrix. As we have given the list representation, just go through the each list and enter 1 in the adjacency matrix $1$ corresponding to each edge. At the end make all untouched entries of matrix 0's.

My Question : I want to design an algorithm that uses only $O(\log n)$ space.

Any time you have a problem parameterized by a number $$n$$ and you need an algorithm whose space usage is logarithmic in $$n$$, you should immediately think "loop counter". You can store numbers in the range $$0$$$$n$$ in $$\Theta(\log n)$$ bits.

So, in this case, you can use an algorithm along the lines of

for i = 1 to n
for j = 1 to n
if j is in i's adjacency list
write 1 to the output
else
write 0 to the output


The loop counters take $$\log n$$ bits each, and you might need a small amount of extra storage for book-keeping but you only need to store a constant number of data items, and none of those will be anything bigger than a number in the range $$0$$$$n$$, so that's still only $$O(\log n)$$.

The algorithm you suggest uses too much space. You are looking for an algorithm that can output the entire adjacency matrix while using only $O(\log n)$ additional space. Equivalently, you need an algorithm that given an index $i$, determines the $i$th bit of the adjacency matrix (serialized in some fixed way).

Can you think of a way of doing this using only $O(\log n)$ space?

Do you see why the two problems are equivalent?