prosper

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.