1. Bob has n friends: a1,a2,...,an,

Bob has also a list L which is a subgroup of {a1,...,an}x{a1,...,an}

which specify which of the friends knows each other (i.e. the pair (ai,aj)

belongs to L if and only if ai knows aj, ai knows aj if aj knows ai).

Bob organize a party and he wants to invite as many friends he can but

each friend has to know at least 5 of the people who are invited.

write an algorithm which returns a list S who is a subgroup of the friends group

and represents the friends which are invited to the party, so that S is legal

and it's size is maximal. prove the correctness of the algorithm and

analyze it's run time.

2. Given a undirected graph G=<V,E> and given k>=2, we want to find a distribution

of V in to k groups: V1,V2,...,Vk such that the number of edges between the groups

is maximal. Write an algorithm which give a proximity of (k-1)/k to the optimal

solution. Prove the correctness of the proximity and analyze the run time.

Thanks a lot. :)