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
            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?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.