Notices
Results 1 to 1 of 1

Thread: Difficult questions

  1. #1 Difficult questions 
    New Member
    Join Date
    Jan 2011
    Posts
    1
    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.


    Reply With Quote  
     

  2.  
     

Bookmarks
Bookmarks
Posting Permissions
  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •