graph coloring

Question

7 var occurs in a loop of computer programm.The variable nd step during which they must be stored are

t: step 1 through 6;u:step2;:steps 2 through 4 ;w:step 1 ,3 and 5;x:step 1 and 6;y:step3 through 6; nd z:step 4 nd 5. How many different index registers are needed to store these variables during execution?

Answer 1

sorry i dint get ur question.but in ur question is u from 2 to 4? if yes then

I got it  5 as the allocation graph is 5 colorable

SOMEONE PLEASE RECTIFY ME IF M WRONG AND MAKE ME UNDERSTAND

Comments

the ans is correct can u describe ur soln... the q is from roshen ( last chapter of graph theory )

---

The variable that are live/executed at same statement or steps is as follows:
S1 : t,w,x
S2: u,t
S3:u,t,w,y
S4:u,t,y,z
S5:t,w,y,z
S6:t,x,y
now drawing a graph with each variables as the vertices and edge would be there between two vertices if they are live in same statement/step
now the k-colorable problem has to be applied as we have joined the vertices that were live in same step so they can't be allocated same temporary/register at the same time(in graph coloring color vertices such that adjacent node are of different colros).
if we color the graph we notice it is 5 colorable ,

Answer 2

register allocation is application of graph coloring

steps	variables
1	t x w
2	t u v
3	t v w  y
4	t v y z
5	t w y z
6	t x y

here vertices represent variables 

there is edge between variables if they are reqd at same time.

t	v	w	y	x	z	u
6	5	5	5	4	4	2
c1	c2	c3	c4	c2	c4	c3

5 registers are required

Comments

i think in step 3 y is also used .

thank u for ur help

Answer 3

I am getting 3 color