Algorithms Difficult questions

[prosperr]

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. :)

[darkagn]

Hi prosperr and welcome to DaniWeb,

Unfortunately we aren't allowed to do your homework for you. We need to see that you have at least thought about these questions before we can even give you a point in the right direction. How do you think these questions should be tackled? What have you come up with so far in your solutions?

[mrnutty]

For the first one, the person a_i is in the subgroup iff there are 5 pairs such that an element from the pair is a_i. So you can use that as a clue.