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.

Reads rather like homework questions? If so have a go and show your attempts.

Edited January 20, 201114 yr by TonyMcC

You need to show you attempts first, then we will help you ...

 

I won't offer anything, but I will give you a hint ...

 

on Q1: you can use Linked-Lists and Counters ...

 

on Q2: you can define a graph using 2D Matrix ...