Homework 7. Grouping Friends

EE3980 Algorithms
Homework 7. Grouping Friends

A social scientist is studying a group of N people. It is known that some of these N people
are good friends with constant communications among them. However, the contents of the communications are not available to the scientist. All the scientist has is a list of the sender-receiver
information. Your assignment is to help this scientist analyzing the list to divide the people into
friend subgroups. The definition of a friend subgroup is the following: Given any two persons
belong to a friend subgroup if
1. They have sent and received messages directly between them.
2. They have sent and received messages through one or more friends between them.
For example, four persons, A, B, C, and D, belong to a friend subgroup if the following communication records were found.
A → B, B → C, C → D, and D → A.
If, however, one of the people has sent messages to others but not receiving any, then apparently
he is not a friend to any one. And, thus, he is a friend subgroup by himself.
On the other extreme, a friend subgroup can contain a single person who received messages but
not sending out any.
Ten communication lists are available for your analysis . They are c1.dat – c10.dat. The
first line of each file consists of two integers: the total number of people being studied, and the
number of communication records. It then followed by the names of all the people, and the
communication records. The content of file c1.dat is attached at the end.
And your program should generate output as the following:
$ a.out < c1.dat
N = 10 M = 25 Subgroup = 3 CPU time = 3.09944e-06
Number of subgroups: 3
Subgroup 1: 谷慎林 左優一 鄭談佶
Subgroup 2: 張殊媗 ⺩遐科 李政女
Subgroup 3: 廖絜筱 陳因萱 周慶讚 韓竟浩
Your program should read in the data file, generate the subgroups and then print out the results.
For this homework, the CPU time measures only the subgroup generation, i.e., read in the data
and write out the results need not be counted in the CPU time reported. And, no repetition is
needed to take the average CPU time.
As before, please write a C program to process these communication records and generate
necessary outputs. In addition, please analyze the complexities of your program and turn in your
report.
1
Notes.
1. One executable and error-free C source file should be turned in. This source file should be
named as hw07.c.
2. A report file in pdf format is also needed. This file should be named as hw07a.pdf.
3. Submit your hw07.c and hw07a.pdf on EE workstations using the following command:
∼ee3980/bin/submit hw07 hw07.c hw07a.pdf
where hw07 indicates homework 7.
4. Your report should be clearly written such that I can understand it. The writing, including
English grammar, is part of the grading criteria.
5. The CPU time per iteration of the second algorithm, if any, may be used to determined
part of the grades of this homework.
2
The content of the file c1.dat is shown below.
10 25
谷慎林
鄭談佶
左優一
張殊媗
李政女
⺩遐科
廖絜筱
韓竟浩
周慶讚
陳因萱
⺩遐科 -> 張殊媗
李政女 -> ⺩遐科
張殊媗 -> ⺩遐科
左優一 -> 陳因萱
張殊媗 -> 李政女
陳因萱 -> 廖絜筱
谷慎林 -> 陳因萱
左優一 -> 谷慎林
左優一 -> 廖絜筱
韓竟浩 -> 周慶讚
張殊媗 -> 廖絜筱
李政女 -> 周慶讚
⺩遐科 -> 陳因萱
鄭談佶 -> 左優一
谷慎林 -> 韓竟浩
谷慎林 -> 張殊媗
谷慎林 -> 鄭談佶
⺩遐科 -> 韓竟浩
左優一 -> 張殊媗
廖絜筱 -> 周慶讚
⺩遐科 -> 廖絜筱
鄭談佶 -> 周慶讚
鄭談佶 -> ⺩遐科
廖絜筱 -> 韓竟浩
周慶讚 -> 陳因萱
3