The internet as a surveillance network

Computer Science Level 1

Government surveillance agencies have a tendency to accumulate strange new powers during times of panic. The US National Security Agency (NSA) now has the ability to monitor the communications of suspected individuals as well as the communications of people within some number of hops of any suspect. In the communication network above, which person is connected to the greatest number of people through 1 hop or less?

Details and Assumptions:

Each dot represents a person.
Each line represents communication between the people on either end.
If X communicates with Y, and Y communicates with Z, we say that X and Z have a 1-hop connection, and that X has a 0-hop connection with Y.

A D B C

2 solutions

Ben Pang
Jan 28, 2016

This is equivalent to traversing the depth-2 subtree from each person node. Here is some pseudocode for solving this problem in a computational way:

int countConnections(person p, int depth) {
    if(depth == 2)
        return 1;
    int count = 0 + depth; 
    //to make sure neighbours of the root count themselves
    for each neighbour n of p do {
        count += countConnections(n, depth + 1);
    } 
    return count;
}

@Ben Pang Why do you write "count = 0 +depth" and not "count = depth" Is there a diff ?

Joshua Daniel - 3 years, 5 months ago

Tom Dufall
Jul 27, 2014

Since 1 hop is a common connection through 1 person, it can be thought of as a 2 line distance (or less since we're counting 1 hop or less).

Then just count the number of dots within 2 lines of each user and find the largest ( $C$ with 11).

Where is the computer science can u say?? However good solution.

Shyambhu Mukherjee - 5 years, 6 months ago

Warmup problem for Graph Theory.

Kunal Verma - 5 years, 4 months ago

OK I just said a much. Thanks for informing that.

Shyambhu Mukherjee - 5 years, 4 months ago

The internet as a surveillance network

2 solutions

0 pending reports