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.
