# We Helped With This Python Programming Assignment: Have A Similar One?

SOLVED

## Short Assignment Requirements

The instructions to assignment are written in the "python as 4" file. The framework for the code for the 9 functions are listed in the "a4_xxxxxxxx.py" file.

## Assignment Description

import random

def create_network(file_name):

'''(str)->list of tuples where each​                                                          ​                 ​tuple has ​​2 elements the ​​first ​​is int and​​ the second is list of

int

Precondition: file_name has data on social network. In particular:

The first line in the file contains the number of users in the social network

Each line that follows has two numbers. The first is a user ID (int) in the social network, the second is the ID of his/her friend.

The friendship is only listed once with the user ID always being smaller than friend ID.

For example, if 7 and 50 are friends there is a line in the file with 7 50 entry, but there is line 50 7.

There is no user without a friend

Users sorted by ID, friends of each user are sorted by ID

Returns the 2D list representing the frendship nework as described above

where the network is sorted by the ID and each list of int (in a tuple) is sorted ​  ​(i.e.  ​each list​               of​

friends is sorted).

'''

return network

def getCommonFriends(user1, user2, network):

'''(int, int, 2D list) ->int

Precondition: user1 and user2 IDs in the network. 2D list sorted by the IDs,  and friends of user 1 and user 2 sorted

Given a 2D-list for friendship network, returns the sorted list of common friends of user1 and

user2

'''

common=[]

return common

def recommend(user, network):

'''(int, 2Dlist)->int or None

Given a 2D-list for friendship network, returns None if there is no other person who has at least one neighbour in common with the given user and who the user does not know already.

Otherwise it returns the ID of the recommended friend. A recommended friend is a person

you are not already ​ ​friends with​    and​ ​  ​with whom you​  ​                       have  ​                    ​the  ​ ​most friends​​  in​​  ​common  ​in  the​

whole network.

If there is more than one person with whom you have the maximum number of friends​ ​ in

common

return the one with the​ ​smallest ID. '''

# YOUR CODE GOES HERE pass

def k_or_more_friends(network, k):

'''(2Dlist,int)->int

Given a 2D-list for friendship network and non-negative integer k, returns the number of users who have at least k friends in the network

Precondition: k is non-negative'''

# YOUR CODE GOES HERE pass

def maximum_num_friends(network):

'''(2Dlist)->int

Given a 2D-list for friendship network, returns the maximum number of friends any user in the network has.

'''

# YOUR CODE GOES HERE pass

def people_with_most_friends(network):

'''(2Dlist)->1D list

Given a 2D-list for friendship​              ​    network,​​  returns​      a​​  list​                ​ ​     of  ​ ​people  (IDs)  ​who     ​  ​have                    ​  ​the                   ​  ​most

friends in network.'''

max_friends=[]

# YOUR CODE GOES HERE return max_friends

def average_num_friends(network):

'''(2Dlist)->number

Returns an average number of friends overs all users in the network'''

# YOUR CODE GOES HERE pass

def knows_everyone(network):

'''(2Dlist)->bool

Given a 2D-list for friendship network, returns True if there is a user in the network who knows everyone and False otherwise'''

# YOUR CODE GOES​ ​HERE pass

####### CHATTING WITH USER CODE:

def is_valid_file_name(): '''None->str or None''' file_name = None try:

file_name=input("Enter the name of the file: ").strip()

f=open(file_name)

f.close()

except FileNotFoundError:

print("There is no file with that​​ name. Try again.")

file_name=None

return file_name

def get_file_name():

'''()->str

Keeps on asking for a file name that exists in the current folder, until it succeeds in getting a valid file name.

Once it succeeds, it returns a string containing that file name'''

file_name=None

while​ ​file_name==None:           file_name=is_valid_file_name()

return file_name

def get_uid(network):

'''(2Dlist)->int

Keeps on asking for a user ID that exists in the network until it succeeds. Then it returns it'''

# YOUR CODE GOES HERE pass

##############################

# main

##############################

# NOTHING FOLLOWING THIS LINE CAN BE REMOVED or MODIFIED

file_name=get_file_name()

net=create_network(file_name)

print(" First​ ​general statistics​ ​about the social network: ")

print("This social network has", len(net), "people/users.")

print("In this social network the maximum number of friends that any one person has ​ ​is

"+str(maximum_num_friends(net))+".")

print("The average number of friends is "+str(average_num_friends(net))+".") mf=people_with_most_friends(net)

print("There are", len(mf), "people with "+str(maximum_num_friends(net))+" friends and here are their IDs:", end="​   ") for item in mf:

print(item, end=" ")

print("I now pick a number at random.", end=" ")

k=random.randint(0,len(net)//4)

print(" That number is: "+str(k)+". Let's see how many people has that many friends.") print("There is", k_or_more_friends(net,k), "people with", k, "or more friends")

if knows_everyone(net):

print(" There at least one person that knows everyone.") else:

print(" There is nobody that knows everyone.")

print(" We are now ready to recommend a friend for a user you specify.")

uid=get_uid(net) rec=recommend(uid, net) if rec==None:

print("We have nobody to recommend for user with ID", uid, "since he/she is dominating in

their connected​               component")​   else:

print("For user with ID", uid,"we recommend the user with ID",rec)

print("That is because users", uid, ​​"and",rec,  "have", len(getCommonFriends(uid,rec,net)),

"common friends​ ​ and")

print("user", uid, "does not have more common friends with anyone else.")

print(" Finally, you showed interest in knowing common friends of some pairs of users.") print("About 1st user ...")

uid1=get_uid(net)

uid2=get_uid(net)

print("Here is the list of common friends of", uid1, "and", uid2)

common=getCommonFriends(uid1,uid2,net)

for item in common:

print(item, end=" ")

## Assignment Description

Five text les have been provided for you to run your program with. Each ​ ​represents         a social​            network. Three are small test les containing a made-up set of users and their​      friendships​      (these les are net1.txt, net2.txt and net3.txt). The two are a subset of a real​ ​  Facebook​        ​               dataset, which was obtained​              from:​  fhttps://snap.stanford.edu/data/egonets-Facebook.html​        The​     format​               ​ ​of

all ve les is the same:​          The​     ​ rst line​             of​         the​       le​      is​ ​ an integer​   ​              ​representing                ​the  number​      ​  ​of         ​  ​              users in the ​ ​given network. The following lines​​  are​  of​         the​       ​​form: user_u ​​user_v where user_u and user_v are the​           (non-negative integer)​            IDs​      of​         ​  two users​   ​​              who  ​​     are  ​friends.      ​ In          ​  addition​             ​ ​user_u               is always less than​     user_v

For example, here is a very small​ ​  le​  that​              ​           has ​​5  ​ ​users  ​in  ​the     ​ ​social  ​network:           ​  ​

0

1

1

2

The above is a representation of a social network that contains 5 users.

User ID=0 is friends with ​ ​User   ​  IDs​             = ​ ​

User ID=1 ​ ​is friends with User IDs ​​= 0, 2,  8

User ID=2 is friends with User IDs = ​ ​1, 3

User ID=3 is friends with User IDs =

User ID=8 is friends with User IDs = 1

Spend time​      studying​            ​ the above small example to​   understand​      ​  the​       model.​               For​      ​ ​example, notice that since​       friendship​         is​​  ​a symmetric​           relationship​     the​        ​​              social media​    ​​networks          in​​  this assignment, if user_u is friends with user_v, that means that user_v is also friends with user_u. Such “duplicate” friendships​       are​       not​       ​               ​present in ​​the le. In particular each friendship is listed ​​once in such way​     that​      user_u​               < user_v​

Also note that, while you can assume that user IDs are sorted, you cannot assume ​ ​that    they​    are​       consecutive integers differing by one. ​ ​For     example​           ​ ​the user​​ IDs ​​above are: 0,1,2,3,8. You can also assume​               that​      in each​             le​      the​       ​               users​​  ​are           ​  sorted​                from​   ​  smallest  ​​to largest (in the above example you see​     that​      users​  appear​               as:​       ​  ​0  ​1  1 2).​        Specically,​     ​  friendships​      ​ ​of user_u appear before friendships of​          user_v​               if and​ ​  ​only     if ​​user_u  < user_v.​        ​  And​     also​     ​  for​        ​ each user its friends appear sorted, for example for user 1 friendship with friend 2 appears before friendship with friend 4.

To complete​    the​       assignment​     you​      ​ ​will       ​  have​   ​ ​to          ​                code​​     ​the following    ​ 9 ​ ​functions.  ​I  ​strongly         recommend you code the in the order given below and do not move onto coding a function until you complete all before. The function ​ ​descriptions, including what ​​they need to do, are given​​ in a4_xxxxxx.py.

1. create_network(file_name) (35​    points)​             This​     ​ ​is the ​ ​most   ​  important         ​  ​( and possibly​ ​  the​       ​ ​most difficult) function​             to​          solve. The​     ​ ​              function  ​needs               to​          read​    a ​ ​le         ​  ​and      ​  return​ ​  ​a  ​list   ​  ​of         ​  tuples representing the​          social network​            ​ from the​​ le. In particular the function returns a list​​ of tuples where each tuple has 2 elements: the rst is an integer representing an ID of a user and the​  second is the list of integers representing his/her​     friends.​              In the​        a4_xxxxxx.py​ ​  ​I refer               ​ the​       ​ ​list        ​  ​that      create_network function returns as a 2D-list for friendship​         network​            (although one​              can​      ​ argue that​         is is a 3D list). In addition the 2D-list for friendship network that must create_network function returns must be sorted by ​ ​the              ID​         ​ ​and  a​ ​ list of​              friends​               in each​             ​  ​tuple   ​ also must​​ be sorted. So​​ for the example​       above, this​      function​            ​ should ​               return the ​​following ​​2D-list for 2D-list for friendship network: [(0​        , [1]), (1​        , ​             [0,2,8]),  ​(2         ,[1,3]), (3​           ,[2]), (8,[1])]​

More examples:​

>>> net1=create_network("net1.txt")

>>> net1 [(0, [1, 2, 3]), (1, ​ ​[0  ,  4, 6, ​ ​7 , 9])​                , (2​        , [0, 3, 6,  ​8 , 9])            , (3​        ,  [0​        ,  ​2, 8 , ​ ​9])          ,  ​(4        ,  ​​[1        ,  ​6 , ​​7 ,  ​8])        , ​ ​(5        , [9]), (6, [1, 2, 4, 8]), (7, [1, 4, 8])​          , ​ ​(8, [2, ​​3, 4, 6, 7]), (9, [1, 2, 3, 5])]

>>> net2=create_network("net2.txt")

>>> net2

[(0, [1, 2, 3, 4, 5, 6, 7, 8, 9]), (1, [0, ​​ 4, 6, 7, ​ ​9]), ​ ​(2   , [0 ,  ​3 , 6,8, ​         9]), (3, [0, 2, ​​8 ,  ​9])          ,                (4,  ​[0                                           ,  1,  ​6 ,  ​7 ,  ​8])          ,

(5, [0, 9]), (6, [0, 1, 2, 4, 8]), (7, [0, ​ ​ 1,  ​​4, 8]), (8, [0, ​​2, 3, 4, 6, ​​7]), (9, [0, 1, ​​2, ​​3, 5])]

>>> net3=create_network("net3.txt")

>>> [(0, [1, 2, 3, 4, 5, 6, 7, 8, 9]), (1, [0, 4, 6, 7, 9]), (2​             , ​ ​[0        ,  ​​3 , 6,8, 9])​   , ​ ​(3,  ​[0                ,  2, ​  8, 9]),  (4​  , ​ ​[0        ,  ​1 ,  ​6 , 7, 8]), (5​           , [0​        , ​             9]), (6, ​ ​[0           , 1, 2, 4,  8]), ​​(7, [0, ​​1, 4, 8]), ​​(8, [0, 2, ​​3, ​​4, 6, ​​7]), (9, [0, 1, ​​2, 3, 5]), (100,

[112]), (112, [100, 114]), ​ ​(114 , [112])]​

>>> net4=create_network("big.txt")

>>> net4[500:502] [(500, [348, 353, 354, 355, 361, 363, 368, 373, ​ ​374,  ​376    , 378, 382,  ​388                , ​                                                                                                              391,

392, 396, 400, 402, 404, 408, 409, 410, 412, 414, 416, 417, 421, 423, 428​      , ​    431,  ​438 ,  439​               ,  444​                                                                                                               ,

445, 450, 452, 455, 463, 465, 474, 475, 483, 484, 487, 492, 493, 497, 503​      , ​    506,  ​507 ,  513​               ,  514​                                                                                                               ,

517, 519, 520​   , 521​    , 524​    ,  ​525​    ,  527, 531, 537​             ,  538​    ,  542​    , 546​    , 547​     ,  ​​548,  ​ ​553, 555 , ​ ​556    , 557, 560, 563, 565​   , 566​    , 580​    , 591​    , ​             ​601, 604             ​, 614​    , 637​    ,  645​    ,  ​            651, 683])​     ,              (501,  [198​         , 348​    ,  ​364    ,  ​393    , 399, 441, 476​              , 564])]​

### 2.​​getCommonFriends(user1,​​user2,​​network)​​(15​​points)

>>> getCommonFriends(3,1,net1) [0, 9]​

>>> getCommonFriends(0,112,net3)

[]

>>> getCommonFriends(217,163,net4) [0, 100, 119, 150]

3. recommend(user, network) (15 points) Read​     ​ the docstrings​​ to understand how this function should work.​    Understand​     why​     the​       ​ given friends are ​​recommended in the examples​​ below including why no​        friend is recommended​        ​ for 0 in ​​net2 and 112 in​​ net 3.

>>> recommend(6,net1) 7

>>> ​ ​recommend(4,net2)

>>> recommend(0,net2)

>>> recommend(114, net3) 100

>>> ​ ​recommend(112,net3)

>>> recommend(217,net4) 163

### 4.​​k_or_more_friends(network, ​ k)​ ​ (5​ ​ points)​

>>> k_or_more_friends(net1, 5)​ ​

>>> k_or_more_friends(net2, 8)

>>> k_or_more_friends(net3, 12)

>>> k_or_more_friends(net4, 70) 33

### 5.​​maximum_num_friends(network) ​ (5​ ​ points)​

>>> maximum_num_friends(net1) 5

>>> ​ ​maximum_num_friends(net2) 9

>>> maximum_num_friends(net3)

>>> maximum_num_friends(net4) 347

### 6.​​people_with_most_friends(network)​​(5​​points)

>>> people_with_most_friends(net1) [1, 2, ​ ​8]

>>> people_with_most_friends(net2) [0]​

>>> people_with_most_friends(net3) [0]

>>> people_with_most_friends(net4) [0]

### 7.​​average_num_friends(network)​ (5​ ​​points)

>>> average_num_friends(net1) 3.8

>>> average_num_friends(net2) 5.0

>>> average_num_friends(net3) 4.153846153846154

>>> ​ ​average_num_friends(net4) 19.78

### 8.​ knows_everyone(network)​              ​ (5​         ​ points)​

>>> knows_everyone(net1) False  >>> knows_everyone(net2) True

>>> knows_everyone(net3) False

>>> ​ ​knows_everyone(net4) False

### 9.​​get_uid(network)​​(10​​points)

>>> get_uid(net1)

Enter an integer for a user ​ ​ID:alsj

That was not an integer. Please try again.

Enter an integer for a user ID: twenty  That was​         not​         an​        ​               integer. Please​​ try again.

Enter an integer ​ ​for a​​ user ID:9aslj​

That was​           not​       an​        integer.​               ​​Please try​        ​ ​again.   Enter an integer​           for​        a user ​ ​ID:100000         That user​         ​ ID does​              ​ not exist. Try again.

Enter an​ ​ integer for a user ID:4.5​

That was not an integer. ​​Please     try ​ ​again.

Enter an ​ ​integer for a user ID: -10

That user ID does not ​​exist.      Try ​ ​again.

Enter ​ ​an integer​ ​ for a user ​ ​ID:-1

That user ID does not exist. Try again.

Enter an integer for a user ID:7

7

1.1 Bonus (10 points) This assignment offers up to 10% bonus.

1. She needs to correctly solve/code create_network and getCommonFriends functions. She will​                know that​          that​      is the ​​case   ​  by​        waiting​               ​  for        the​       grading​              to​          ​               be​ ​ completed        ​and seeing​       ​ ​that      ​ she​      did​       ​  ​not       loose any ​ ​points on these​​  ​2 ​ ​functions; and

2. She needs to solve getCommonFriends(user1, user2, network) with running time​ ​  O(n1​          +n2

+logn) were n is the the total number of users​               in the​ ​  network,​           ​ n1 is ​ ​the number ​​of friends  of user1 and​         n2​        is ​ ​        the        number ​ ​             of  friends​           of​         ​ ​user2.                In​          ​  ​other   ​  ​words,  ​  ​n1        ​ ​= len(user1),  n2​          ​  ​= len(user2) and n =len(network). Note that on a typical network O(n1+n2+logn) is much​             better than​    O(n)​    since a network like Facebook has n roughly 2 billion and​      ​  the       ​ ​               ​average number​           of​         ​ ​friends               ​ ​per       user is 338. Thus the number of operations an O(n)​       solution​             ​  would do,​       ​ ​would be in ​​the ​​order of a billion,roughly.​     ​ While​   ​ the​ ​ number of operations an​         ​ ​              O(num_friends_user1 + ​​num_friends_user2

+ log​     n)​         solution​             would do,​       ​               ​would be           in​​  the order​  ​               of, ​​O(338          ​  ​+  ​338        ​​+  ​         21),  thousand,​                ​  ​roughly.            ​ ​Thus   O(n) solutions​                ​ will not be accepted for the​         bonus.​               To​        determine​        the​       ​ ​running              ​ times ​ ​of Python’s functions on​            lists you​      can​      use​      ​  ​this      ​  ​link (although ​ ​it is​ ​ not quite correct as it is ​​amortized, which they incorrectly call​      average,​           analysis​            and​       ​​              not  ​the worst case​​ analysis).

https://wiki.python.org/moin/TimeComplexity Again​  ​ you cannot use sets nor dictionaries nor deque nor bisect module.

Customer Feedback

"Thanks for explanations after the assignment was already completed... Emily is such a nice tutor! "

Order #13073

Find Us On