## CPS616 |
## W2017 Lab 4 | |

## Worth: 5% |
## Exhaustive Search |
## Due: Monday February 27 |

## Team sizeThis lab can be done in teams of 1 or 2.## Lab DescriptionThis 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 SEARCHESPart 1 is fully described on the marking sheet.## Part 2 - MYFRIENDSPart 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 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 friendYou can now answer questions about Part 2 directly in the marking sheet. Question D is refering to these Facebook statistics: - Facebook active users
- Average number of Facebook friends - US 2014. Note that this statistic is local to the US and is somewhat dated, but it does provide useful ballpark information.
## Additional Material- Textbook chapter 3.4, 3.5
- Class handout on Brute Force algorithms.
## Hand InThis lab is a paper submission to be handed in at the Computer Science office. |

Last modified Monday, 13-Feb-2017 03:04:07 EST