0
$\begingroup$

I am trying to understand Divide and Conquer algorithm, I learnt it through the Skyline problem and I was able to understand that quite well, however the below problem is giving me troubles. I was able to come up with a recursive algorithm for the same as shown below but I am unable to split it into smaller chunks and derive Divide and Conquer Algorithm, could someone please help me with the same?

You work at a school with $n$ students. Each student is initially in a group by themselves. The school would like to combine everyone into a single large group, but school policy says only two groups can be combined at a time. Every time two groups are combined, everyone from both groups must shake the hand of everyone else from both groups.
(Note that since each member of the two groups shakes hand with everyone in both groups being combined including those in their own group, one may end up shaking hands with the same student multiple times before all are combined)


Recursive Algorithm:

procedure $\mathrm{Group}(1, n)$
$ \quad $ if $n ==1$ then
$ \qquad $ return $P_1$
$ \quad $ else
$ \qquad $ return $\operatorname{Add}\bigl(\operatorname{Group}(1, n-1), P_n\bigr)$

where $P_1,\dots,P_n$ denotes $n$ initial groups of individual students and $\operatorname{Add}(a,b)$ denotes procedure which combines groups $a$ and $b$.

$\endgroup$
11
  • $\begingroup$ You can combine the groups in many different ways, are you looking for a particular grouping? $\endgroup$
    – kingW3
    Commented Oct 13, 2021 at 0:42
  • $\begingroup$ Yes, using Divide and conquer, i have a tough time splitting them into smaller chunks, i mean i guess it should be split into 1...n/2 and n/2...n groups, but not sure how to go ahead $\endgroup$
    – Grim0419
    Commented Oct 13, 2021 at 0:48
  • $\begingroup$ Just write what you wrote in the comment but using Group and Add, think about what's the base case for Group(a, b). $\endgroup$
    – kingW3
    Commented Oct 13, 2021 at 0:53
  • $\begingroup$ procedure Group(1, n) if n ==1 then return P1 else firsthalf= Add(Group(1, n/2-1), Pn/2) secondhalf = Add(Group(1, n/2-n), Pn) finalRes = firsthalf+secondhalf ---base case should be a=1 and b =1 considering that they start as groups of single individual? sorry if am bluntly wrong $\endgroup$
    – Grim0419
    Commented Oct 13, 2021 at 0:56
  • $\begingroup$ This is better, but in the explanation above you didn't use n/2-1 and Pn/2, you used 1..n/2 and n/2+1..n don't overcomplicate. Also it's not entirely clear from your usage but Group(a, b) is the group of people from a to? $\endgroup$
    – kingW3
    Commented Oct 13, 2021 at 1:06

1 Answer 1

1
$\begingroup$

You probably want to focus on the general function $Group(a, b) $and then call it with $a=1,b=n$

Now you want to split the interval into halfs the middle happens at $(a+b) /2$ so you basically just add the two halfs $Group(a, b) = Add(Group(a, (a+b)/2,(a+b)/2+1,b)$

Now think about the base case of Group(a, b)?

It's when there's only one person in the group so $a=b$

So you add the rule if $a==b$ then$Group(a, b) = P_a$.

$\endgroup$
5
  • $\begingroup$ so i am trying to understand this using a case where n = 10, so the total number of handshakes involved using the above algorithm will be 32? shouldn't b = n -1? $\endgroup$
    – Grim0419
    Commented Oct 13, 2021 at 1:51
  • $\begingroup$ @ShashankL If there are $n$ people then no, as for number of handshakes that depends on the add function, if I'm correct it's actually 60. $\endgroup$
    – kingW3
    Commented Oct 13, 2021 at 2:03
  • $\begingroup$ Anyway there are a few things that need to be changed if you want the total number of handshakes, it is unclear from the question if that's what you want or even if you wanted to minimize the number of handshakes. Anyway I'll add more information tomorrow, I'm too tired right now. $\endgroup$
    – kingW3
    Commented Oct 13, 2021 at 2:09
  • $\begingroup$ i am sorry for pestering so much. Yeah ultimately i wanted to validate the algo by finding the total number of handshakes. oh 60? then i am terribly going wrong. $\endgroup$
    – Grim0419
    Commented Oct 13, 2021 at 2:13
  • $\begingroup$ @ShashankL Basically after $Add(Group(a, (a+b) /2),Group((a+b)/2+1,b))$ you have $b-a+1$ people, the 1st people shook hands with $b-a$ people, 2nd shook with $b-a-1$ (not including the 1st person since we counted his handahake), 3rd shook with $b-a-2$ (not including 1st,2nd) etc. so we have $(b-a)+(b-a-1)+\cdots+2+1=(b-a+1)(b-a)/2$. So every Add operation adds $(b-a+1)(b-a)/2$ handshakes. I think $85$ is the correct answer I've hastily checked last time. $\endgroup$
    – kingW3
    Commented Oct 13, 2021 at 10:14

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .