Description
1 Introduction
Pyramid schemes1 are large scale scam operations that fool ordinary people with little to no experience in
investment or marketing. Such organizations promise new members that if they can convince other
people to join, they will receive commissions or other bonuses. This idea benefits people who joined early
(usually the directors of the organization) but leaves most members with great losses, simply because no
new member will join after some time. There are also some variations that try to make it look legal, such
as advertising themselves as a marketing company that sells collectibles, which do not have any real value.
Recently2
, Toronto police uncovered a pyramid scheme network in Toronto. The information came from
John Doe, a recently arrested criminal who was the main bookkeeper of the network. While Doe was
arrested on drug charges, police found evidence of a running pyramid network on his computer. He kept
detailed logs of who joined the network, how and when, as well as how much assets they currently have.
Toronto police is now planning for Operation Sahure3
to crack down on this pyramid scheme. However,
due to recent budget cuts, there is only one unit to be sent to make arrests. So, they can only arrest one
person at a time. After arresting a person, all of their illegal assets will be seized. Considering that the
news of arrest will be public in a few hours after the first arrest, the police only have time to arrest at
most a specific number of suspects. They want to maximize the amount of assets that they seize from
suspects.
Furthermore, they do not have the location of members. The Crown Attorney prepared a deal for any
arrested member to receive reduced charges when they reveal the location of another member to police.
However, each member only knows a few other members in the network, a policy that was strictly
enforced to protect the network from mass arrests. Every arrested member will accept the deal, if offered.
Doe also accepted a deal from the Crown Attorney to disclose the location of one member to the police
in exchange for a reduced sentence. Now the police want to decide which group member they should
select to arrest, to maximise the seized assets considering all limitations. So, they are asking you to help
them find the answer.
1 For more information, take a look at https://en.wikipedia.org/wiki/Pyramid scheme
2Note that this is a fictional scenario, and all names and events are not real.
3 Sahure is an ancient pharaoh, which built a great pyramid for himself. You can read more about him on
https://en.wikipedia.org/wiki/Sahure
2
2 Network Structure
The pyramid network has a hierarchical structure, and uses special terms to refer to users. Consider the
sample network topology shown in Figure 1. The number under each name is the illegal asset that the
member has and can be seized if police arrested that member.
Figure 1: Sample Network Topology
There is one great boss (Liam in Figure 1) that has created and ruled the network. Other than him, each
person who joined the network is sponsored by a network member. For example, Emma and Jacob are
sponsored by Liam, to join the network. A new member is called a child of their sponsor in the network.
For example, Emma and Jacob are Liam’s children in Figure 1.
When a new person joins the network, another member is appointed as their mentor and will teach the
new member different techniques of recruiting more people. If the new member is the first child of their
sponsor, the sponsor will also act as the mentor. As examples, Alexander is the first (and only) child of
James, so James is both the sponsor and the mentor of Alexander; or, Emma is the first child of Liam, so
Liam is both her sponsor and mentor.
If a member is not the first child of the sponsor, then the youngest child of the sponsor (the child who
joined the network more recently) will be the mentor. For example, Emma is Jacob’s mentor as she has
been the last person sponsored by Liam when Jacob joined the network. Similarly, Mason is Sophia’s
mentor, and Sophia is Olivia’s mentor. (In Figure 1, the left-to-right order of children represents the order
that they joined the network).
Liam
20
Emma
32
Jacob
50
Sophia
5
Mason
14
Olivia
8
William
42
Ethan
5
James
10
Alexander
60
3
In this topology, each member knows the location of their sponsor, that of their mentor, and those of
their children. When police arrest a member, that member—as part of the Crown Attorney deal—may be
asked to reveal the location of either one of their children, their sponsor, or their mentor. Recall that the
mentor of the first-child members is their sponsor.
3 Arrest Operation
The police will ask Doe to reveal the location of a network member, called “target zero”. They will arrest
target zero first, and ask him/her to reveal the location of another member (either their sponsor, mentor,
or one of their children). Then, they will arrest that member, and continue the operation in the same
manner until either they arrest the maximum members that they can arrest (due to time limit on overall
operation), or the last arrested member cannot reveal the location of any other member that is not
arrested already.
For example, consider Figure 1. Assume the maximum number of arrests is 4. Then, police may start by
arresting Mason, then arrest Emma, Liam, and Jacob. However, if they arrest Mason, Emma and Sophia,
they cannot arrest any fourth member, because Sophia cannot help them to arrest any new member: she
does not have any child, and she only knows the location of Emma (her sponsor) and Mason (her mentor),
both of whom are already arrested.
The police goal is to maximize the amount of seized money. So, if they follow the Mason, Emma, Liam,
and Jacob scenario, they will seize a total of 116 = 14 + 32 + 20 + 50. But, by the Mason, Emma, and Sophia
scenario, the seized asset will be 51 = 14 + 32 + 5. In this case, the best scenario is Alexander, James,
William, and Jacob that will seize 162 = 60 + 10 + 42 + 50. Your goal in this assignment is to help the police
find the best scenario.
4 Network Log Format
Here, we describe the format of network log that police found on Doe’s computer. Each line of the file
describes one member: i.e. the lines represent the order that members joined the network: the first line
represents the first member, and the last line is the newest member of the network. Each line provides
three pieces of information about the user: user name, their sponsor, and their illegal asset. The great
boss does not have any sponsor, so that field is not present for him. These three parts are separated by a
number sign (“#”). Here is the network log of the network shown in Figure 1:
Liam#20
Emma#Liam#32
Mason#Emma#14
Jacob#Liam#50
Sophia#Emma#5
William#Jacob#42
James#William#10
Ethan#Jacob#5
Olivia#Emma#8
Alexander#James#60
4
5 Starter Code
In this assignment, you should implement one class named Network in the file “network.py”. The
starter code has signature of the class methods that you should complete. Here is a short description of
what each function does:
load_log: This function reads the network log file and prepares the network object for future
operations.
sponsor: This function returns the name of the sponsor of the specified member. For example, calling
sponsor(“Emma”) will return “Liam”. This function should return None if it is called for the great boss.
mentor: Similar to the sponsor function, this function returns the name of the mentor for the requested
member. For example, mentor(“Mason”) returns “Emma”, and mentor(“Sophia”) returns “Mason”.
assets: This function returns the current assets of a member. For example, assets(“Emma”) returns
32, and assets(“Olivia”) returns 8.
children: This function returns a list of all children’s name for a user. For example, children(“Emma”)
returns [“Mason”, “Sophia”, “Olivia”]. If the member does not have any children, it returns an empty list.
Best_arrest_seize: This function returns the maximum amount that police can seize for the given
maximum number of allowed arrests. For example, best_arrest_seize(4) returns 162 (as discussed
previously). As more examples, best_arrest_seize(2) returns 92 (by arresting Jacob and William),
and best_arrest_seize(1) returns 60 (arresting Alexander).
best_ arrest_order: This function returns a list of members that should be arrested in order to achieve
the maximum possible seized assets. For example, best_arrest_order(4) should return [“Alexander”,
“James”, “William”, “Jacob”]. Note that there may be more than one way to achieve the maximum seized
assets, and this function should return one of them. For example, we may arrest members in a different
order to achieve the same output: [“Jacob”, “William”, “James”, “Alexander”]. As another example,
best_arrest_order(2) returns [“Jacob”, “William”].
6 Declaring your assignment team
You may do this assignment alone or in a team of 2 students. Your teammate should be different from
any other partners that you have had (or going to have) in the labs (tutorials) and Assignment 1. You must
declare your team (even if you are working solo) using the MarkUs online system. Assignment and team
declaration will be active from June 30. Teams are required to be declared from June 30th to July 16th
.
Navigate to the MarkUs page for the assignment and find “Group Information”. If you are working solo,
say so. If you are working with other(s):
First: one of you needs to “invite” the other to be a partner, providing MarkUs with their CDF user name.
Second: the invited student must accept the invitation.
Important: there must be only one inviter, and the other group member accepts after being invited, if you
want MarkUs to set up your group properly.
5
To accept an invitation, find “Group Information” on the appropriate Assignment page, find the invitation
listed there, and click on “Join”.
7 Submitting your work
Submit the following file on MarkUs by 4:30 p.m. July 22:
network.py
Click on the “Submissions” tab near the top. Click “Add a New File” and either type the file name or use
the “Browse” button to choose one. Then, click “Submit”. You can submit a new version of a file later
(before the deadline, of course); look in the “Replace” column.
8 Special Office Hours
There will be special office hours for this assignment on July 15, from 1 to 5, in BA3201. This will be the
best time to discuss your questions in person with the Assignment Lead TA. In particular, we will NOT
answer questions asked one day before the deadline (in person or online).
Start Early!