Adjacency-list to Adjacency matrix in logarithmic space?

Question

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.

Answer 1

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)$.

Answer 2

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?