Describe the algorithm to draw the dependency graph?  

Ans: Algorithm to draw Precedence Graph is like this:

a.  For every transaction T_i participating in schedule S, make a node labeled T_i in the precedence graph.

b.  For every case in S where T_j executes a read_item(X) after Ti executes a write_item(X), create an edge (T_i→T_j) in the precedence graph.

c.  For every case in S where T_j executes a write_item(X) after T_i executes a read_item(X), create an edge (T_i→T_j) in the precedence graph.

d.  For every case in S where T_j executes a write_item(X) after Ti executes a write_item(X), create an edge (T_i→T_j) in the precedence graph.

e.  The schedule S is serializable if and only if the precedence graph has no cycles.