CPS616

W2017 Lab 4

Ryerson University

Worth: 5%

Exhaustive Search

Due: Monday February 27


Team size

This lab can be done in teams of 1 or 2.

Lab Description

This lab has two parts, both of which deal with exhaustive search of graphs.

This lab should be done directly in the marking sheet (docx or pdf).

Part 1 - GRAPH SEARCHES

Part 1 is fully described on the marking sheet.

Part 2 - MYFRIENDS

Part 2 deals with a social media site called “MyFriends” where members look for “friends”. Once people are friends, they spend a lot of time communicating and exchanging information with each other, and MyFriends profits from these interactions: the more interactions, the bigger the profit. Therefore MyFriends wants to encourage members to have more friends.

A strategy for accomplishing this is to suggest potential new friends to members. However, members often do not want to become friends with complete strangers, so MyFriends has figured that the best strategy is to propose to members potential new friends that they are likely to already know in person, or that they are likely to eventually meet, or that they think that they might like if they were to meet them: in other words friends of friends.

MyFriends has also figured that members are more likely to accept new friends who are already clearly an integral part of their social network than people who are on the periphery, in other words, members are more likely to become friends with people who already befriend many of their friends rather than people who are only friends with a few.

Part 2 is about a brute force algorithm that MyFriends can use to propose potential new friends to their members.

MyFriends keeps a graph that represents the friendships between its members: Each member is a vertex in that graph, and there is an edge between two members if and only if they are friends. This graph is stored as a adjacency matrix of Booleans called Friends where Friends[x,y] = True if and only if members x and y are friends.

Here is a very crude brute force pseudocode algorithm to encourage members to befriend the friends of their friends:

int Population  // number of members

int CommonFriends[population,population]
  // CommonFriends[x,y] = 0 if x=y or x and y are friends
  // Otherwise CommonFriends[x,y] = # of friends x and y have in common
  // This matrix is initialized with all elements being 0

MakeNewFriends ()
  {  
  CalculateCommonFriends()
  SuggestFriends()
  }

CalculateCommonFriends()
  {
  int i, j, k
  for i from 1 to Population
    for j from 1 to Population
      if j!=i for k from 1 to Population
        if k!=i and !Friends[i,k] and Friends[i,j] and Friends[j,k]
          CommonFriends[i,k]++
  }
  
SuggestFriends()
  {
  int i, j,bestcandidate  
  for i from 1 to Population
    {
    bestcandidate = i
    for j from 1 to Population
      if CommonFriends[i,j] > CommonFriends[i,bestcandidate]
        bestcandidate = j
    ProposeNewFriend(i,bestcandidate,CommonFriends[i,bestcandidate])
    }
  }

ProposeNewFriend(member,bestcandidate,commonfriends)  
  // will tell member that s/he has commonfriends friends in common
  // with bestcandidate and will ask him/her if they would like to 
  // invite bestcandidate to be their friend      
You can now answer questions about Part 2 directly in the marking sheet.

Question D is refering to these Facebook statistics:

Additional Material

Hand In

This lab is a paper submission to be handed in at the Computer Science office.
  • Hand in a printout of your marking sheet and written solution (docx or pdf).
  • In addition to the lab itself you will need to also submit the Lab Submission Declaration on D2L. This lab will not be graded unless this declaration has been submitted


This page is maintained by Sophie Quigley (cps616@scs.ryerson.ca)
Last modified Monday, 13-Feb-2017 03:04:07 EST