Problem 4: Describe a (n) algorithm to find a stable matching in the following special case: every welder has the same preference list, and every machinist has one of two preference lists (so perhaps welders are ranked by either speed or accuracy and some machinists prefer fast welders while others prefer accurate welders). The inputs will be:

• n, the number of machinists (equal to the number of welders),
• a 1-D array prefW where prefW[i] gives the index of the machinist ranked ith by all the welders;
• a 2-D array prefM where prefM[i][j] gives the index of the welder ranked jth according to machinist preference list i (i=1 or i=2 so that row 1, for example, could store the ordering by speed and row 2 the ordering by accuracy); and
• a 1-D array type where type[i] gives either 1 or 2, corresponding to the preference list for machinist i.

For example, if the preference lists are:

Machinist	pmpm	Welder	pwpw
m1	w1,w2,w3,w4	w1	m1,m3,m2,m4
m2	w2,w1,w4,w3	w2	m1,m3,m2,m4
m3	w2,w1,w4,w3	w3	m1,m3,m2,m4
m4	w1,w2,w3,w4	w4	m1,m3,m2,m4

Then n = 4, prefW = [1, 3, 2, 4], prefM = [ [1, 2, 3, 4], [2, 1, 4, 3] ], and type = [1, 2, 2, 1] (note that the arrays use 1-based indexing).

You needn't prove that your algorithm is correct, but you should explain why your algorithm runs in (n) time.

Problem 4: Describe a (n) algorithm to find a stable matching in the following special case: every welder has the same preference list, and every machinist has one of two preference lists (so perhaps welders are ranked by either speed or accuracy and some machinists prefer fast welders while others prefer accurate welders). The inputs will be n, the number of machinists (equal to the number of welders), a 1-D array prefw where prefw[i] gives the index of the machinist ranked ith by all the welders; a 2-D array prefm where prefM[i]j] gives the index of the welder ranked jth according to machinist preference list i (i = 1 or i = 2 so that row 1, for example, could store the ordering by speed and row 2 the ordering by accuracy); and a 1-D array type where type[i] gives either 1 or 2, corresponding to the preference list for machinist i. For example, if the preference lists are Machinist pm Welder pw mi W1, W2, W3, W4||W1 mi, m3, m2, m4 m2 m3 W2, W1, W4, W3 ||W1 mi, m3, m2, m4 W2, W1, W4, W3 | W1 mi, m3, m2, m4 W1, W2, W3, w4|w1 mi, m3, m2, m4 4, prefw [1, 3, 2, 4], prefM [ [1, 2, 3, 4], [2, 1, 4, 3] ], and type m4 Then n = [1, 2, 2, 1] (note that the arrays use 1-based indexing). You needn't prove that your algorithm is correct, but you should explain why your algorithm runs in (n) time