Coding Mini Project

Material Developed by: Sanchit Batra, Elijah Einstein, Sean Mackay, Supratik Neupane, Tom Sherwood, Veronica Vitale and Atri Rudra.

Acknowledgment

The development of the coding component of the mini-project was supported by a Mozilla Responsible Computer Science award . The support is gratefully acknowledged.

Some Suggestions and Warnings

While this coding mini-project is somewhat similar to Question 3s on the homework, there are some crucial differences and we wanted to highlight few things for y'all upfront:

Form groups of size $\le 3$

This is a group project (unlike Q3s on the HWs that had to be done individually) and you can work in groups of size at most 3. The submissions will be on Autolab and everyone in the group will get the same grade. The project will be challenging so we highly recommend that you form a group of size at least 2 to make the workload reasonable.

Groups should agree on one programming language

While the submission in this project can be done in any of C++,Java and Python like in Question 3s on the homework, we highly recommend that the group agrees on one programming language for the group. This will make it much easier for your group to make progress and collaborate.

The same group for ALL problems

You are expected to work in the same group for ALL problems in the coding project. Not doing so will be considered to be an academic integrity violation. Please note that you will have to sign up your group separately for each problem on Autolab and we will check for group consistency at the end of the semester. So please make sure you follow this rule.

There is ONE exception to the above rule: It is OK if the group becomes smaller (e.g. if a group member resigns) but in that case another student cannot be added to group. If you need clarification on this, please get in touch with Atri.

There are no optimal algorithms known!

Other than the first problem, we do not know of optimal algorithms to solve the rest of the problems and we suspect that doing so is not possible (definitely not within a semester). Note that this is unlike the HW Q3s where your code is supposed to always output the optimal/correct solution: i.e. you will have to think of algorithms where you might not be able to prove any guarantee on how good your output is.

Start early!

There is a reason we are giving y'all about two months to do this project. If your group starts even the week before the project is due, your group will be in trouble especially beyond the first problem. Also for most problems you will have to think of algorithms beyond what we cover in class, so the more time your spend on this, the better.

Optimizing the runtime of your code is NOT the main objective

Unlike the HW Q3s, there will be no timeouts for individual inputs (though there will be one overall per submission). This is because unlike the HW Q3s, the main goal in this coding project submissions will be to generate as much "revenue" as possible (read on for more details on this)-- optimizing the runtime would/should be a secondary object but again there is an overall timeout so really inefficient implementations (and definitely not polynomial runtime algorithms) will not make the cut.

Background

Today reliable internet service is not a luxury, it is a necessity . In February 2017, a lawsuit was filed by New York states Attorney General Eric Schneiderman against Spectrum , which is a telecommunications company and also the largest provider of residential internet services in New York state. See e.g. the following from the AG's summons and complaint page 6 and point 2:

....Spectrum-TWC is the largest provider of residential Internet services in New York State. It provides Internet service to approximately 2.5 million New York households and earns well over a billion dollars in revenue annually from selling Internet services in New York.

Spectrum was accused of fraudulently misleading its Internet services customers by promising internet speeds that it knew it could not provide. Spectrum provided its customers with old generation modems and routers that it knew were incapable of achieving the promised internet speeds. Moreover, they are also accused of capping the bandwidth of routers in order to cut down on expenses and maximize their profit. There were more allegations against Spectrum. Here is the official lawsuit complaint against Spectrum with all the allegations.

Click here to see a summary of the allegations

Promised internet speeds differed from actual internet speeds, Spectrum made false advertisements and repeatedly assured its customers that they could achieve the same results with wireless as with a wired connection (even though wireless connection has other real world limitations).
Leased out older models of routers that were incapable of achieving the promised speeds (D1 and D2 as opposed to D3) due to “budget constraints” (maximizing profit).
Charged customers based on the prices advertised for the higher speed plans (the motive for said advertisement was to prevent subscribers from switching ISPs).
Promised to upgrade the routers without additional charges when tech improved but didn’t despite complaints from customers about the slow internet speed.
Even the current generation routers did not deliver the speed they had promised, since too many subscribers were grouped into the same service group (less bandwidth available per subscriber) and the number of channels did not increase (which could have increased the bandwidth). Only made modifications when the situation was dire. This led to an abysmal performance during peak hours.
Deceived the FCC by benchmarking speed during non-peak hours (and hence overestimating performance).
Changed modems for the FCC panelists doing the benchmarking but not for customers. The FCC results, as a result, painted them in a better light.
Did not invest in additional ports (cost per Gbps) to content providers which could have decreased latency/buffering/downtimes despite promising the opposite to consumers. In fact, leveraged their access to subscribers by extracting fees from content providers and delivering nothing in return, throttled the rate of content delivery in the absence of payments.
Started charging a monthly leasing fee for the same modems for which there had previously been no charge.
Customers were allowed to upgrade their modems to D3 but were subjected to long call hold times, the notice that was sent to customers conveniently left out the fact that their current modems were a bottleneck, there was a fee to install the modem, they had to return the D2 modem or pay an unreturned equipment fee in order to upgrade to D3 modems.
Programmed D2 routers to cap speeds at 20 Mbps but did not switch the pricing tier to a lower one.
Rejected recommendation to deploy newer 802.11ac routers for higher speed tiers to save costs.
Manipulated FCC results, temporarily give more ports to Cogent so as to improve their score.
League of Legends by Riot games requires low latency and packet loss, both were high (and higher compared to other NY ISPs) before Riot agreed to pay Spectrum.
Cherry picked other online content besides League to slow down more than others.

The Basic Problem

The Problem

Essentially, Spectrum was alleged to have used unethical and fraudulent ways to make profits. Now imagine that you just graduated from UB with a bachelor's degree in Computer Engineering/Computer Science and got hired by ForProfitOnly Internet provider. You're recruited into ForProfitOnly as a junior software engineer. It's your first day at work and your first assignment/task is to come up with routing algorithms to generate paths that will be used to route packets in ForProfitOnly's network topology. Since it's your first day at work, you're very eager to please your superiors by delivering as much revenue as possible to ForProfitOnly. Below is a detailed description of your task and the various problems that you need to solve.

Simplifications galore!

To make the problem more manageable, we have made many simplifying assumptions that at the same time hopefully capture the "essence" of the related fact in real-life. Wherever possible, we will provide more details that we are sweeping under the rug and if necessary provide a reference for further reading.

Notation Table

The project description is a bit notation heavy. If you start losing track, here is the notation page (opens in a new window) that might be useful.

The Graph

You are given an undirected communication graph $G = (V,E)$ of the ForProfitOnly network, where a designated node $i \in V$ is the content provider (think of a service like Netflix). Every other node $u \in V$ is a router. $C$ is the set of clients and $C \subseteq V \setminus \{i\}$.

Clients vs. Routers

For this project, clients can still route packets but routers cannot be clients.

Every edge $e \in E$ has a delay $d_e$ associated with it, which is the amount of time it takes for a packet of data to traverse through an edge $e \in E$.

$d_e=1$ for all edges $e$

For all the problems, you can assume that for every $e \in E$, $d_e = 1$.

This is a simplification as in real life networks different edges can have different delays. We make this simplification to make the problems in this project easier.

Every client node in $C$ requests a packet of data from the content provider node $i \in V$. The packet addressed to a client $c \in C$ is denoted by $\text{pkt}_c$.

Packets are different

The packets $\text{pkt}_c$ for different clients $c$ are different. I.e. you cannot combine packets for different clients together.

One packet per client

We made the simplifying assumption that there is only one packet per client $c$. Unlike some of the other simplifications we make in this project, this is not such a big simplification.

For each of the problems 1-5 (see below), you will need to come up with an algorithm that outputs a path to route packets from the content provider node $i \in V$ to every client in $C$ with some given constraints.

Routing is centralized

In this project, there is a central algorithm that chooses an $i-c$ path for each client $c$. This is not how routing happens on the Internet. In particular, the TCP/IP protocol is a distributed protocol. However, distributed algorithms are out of the scope of this course.

Every problem will have an objective that you need to optimize.

Let $P$ be any path from the content provider node $i \in V$ to some client node $c \in C$. We define $D(P)$ to be the sum of the delay of all edges in path $P$. That is, $D(P) = \sum_{e \in P} d_e$.

For every client $c\in C$, let $d(c)$ be the minimum of $D(P_c)$ among all $i-c$ paths $P_c$. Let $P'_c$ be the actual $i-c$ path determined by your algorithm for client $c$. As defined above $D(P'_c) = \sum_{e \in P'_c} d_e$.

Every node $u\in V$ has a bandwidth $b_u$, a bound on the number of packets it can send in each time step.

No bound on incoming traffic

Note that we are not putting any restriction on how many packets a router can receive in each time step. We make this simplification so that the problems are a bit simpler.

We will assume that the bandwidth of the ISP node is very large. That is, $b_i$ is a very large value

Routing of packets

Every client $c \in C$ has a priority, which is given by $\text{priority(c)}$.

Larger value is higher priority

$\text{priority(c)}$ is a positive integer and a larger value implies a higher priority.

By default, for all $c \in C$, $\text{priority(c)}$ = PRIORITY_DEFAULT = 0. You are not allowed to change/set the priority unless it is explicitly allowed in a problem.

The content provider node $i$ will send out a packet to all clients simultaneously. This packet will be routed through the path $P'_c$ for each client $c$ that your algorithm outputs.

All packets are sent out of $i$ at the same time

We make the simplifying assumption that packets $\text{pkt}_c$ for all clients $c$ are ready to be routed out of $i$ at the same time. This in real-life is not necessary since different clients might request their packets at different times. Again, this simplification makes the problems easier.

The routing will take place in time steps. That is, at every time step the packet will be transmitted to the next node in $P'_c$ until it reaches $c$. During the routing, if there is some router $u \in P'_c$ s.t. $u \neq c$ and $b_u$ is less than the number of packets that need to be transmitted a timestep, then $|b_u|$ number of packets belonging to clients of higher priority are transmitted in that timestep. Once the packet requested by client $c$ reaches it, $c$ will accept the packet.

Algorithm Idea

The routing simulator will proceed iteratively, with each iteration mapping directly to a time ‘tick’. Inside each time tick, all the clients are processed and time is advanced only once this processing is finished.

The list of clients, initially maintained as an array (since linked list sorting is slow), will first be sorted by priority, which ensures only the highest priority packets get forwarded if there are bandwidth restrictions. The list is then converted to a Linked List so that as soon as a packet has reached, the client can be removed from the list.

The simulation iterates until all the packets have reached the end of their path. This condition is true when the list of clients is empty.

At each time tick, check if a packet has reached its destination. If it has, remove the client from the list of clients. The client’s delay is set to either the packet delay or infinity depending on whether the packet reached its intended client or not (respectively). Finally, skip to processing the next client.

If the packet is still in transit, its delay is incremented. It is then “forwarded” if the node it is currently at has enough bandwidth and after checking that the corresponding edge is valid. Forwarding comprises incrementing its location by 1 and decrementing the current node’s available bandwidth.

After each time tick, the bandwidth is reset to the router’s $b_u$ value for all routers that participated in the forwarding.

Once we are done processing the entire list, each client’s delay can be retrieved using the corresponding member variable.

Algorithm Details

Sort list_clients, key = client.priority and in descending order
Convert list_clients to a Linked List
active = set()
While list_clients is not empty:
- For client in list_clients:
  - current_node = node that the packet is currently at
  - If the client's packet has reached the end of it's path:
    - Remove client from list_clients
    - Client's delay is set to the packet delay if the current_node is the packet's intended client, otherwise it is set to ∞
    - Continue to next iteration
  - Increment packet delay
  - If current_node's bandwidth > 0:
    - If the current node and the next in the packet's path are not neighbors:
      - Remove client from list_clients
      - Client's delay = ∞
      - Continue to next iteration
    - Decrement current_node's bandwidth
    - Increment packet's current node to the next node in the packet's path
    - Add current_node to active
- For node in active:
  - Set node's bandwidth to node's original bandwidth
  - Clear all elements from active

Payments and Revenue

Every client $c \in C$ makes a payment $\text{pmt}_c$ to ForProfitOnly and also has a tolerance threshold $\alpha_c$, which represents $c$'s tolerance to slow internet. Please see Problem 1 for a detailed description.

Clients payments can vary

In this project we assume that the payment $\text{pmt}_c$ for different $c$ could be all different (unlike in real-life where typically there are "tiers" of payment).

Example 0

Let's look at a small example graph (please see the figure below) with $11$ nodes. Each node in this graph has a node id which is an integer. In this graph nodes $1,3,6,7,8$ are clients, node $0$ is the ISP node and the remaining nodes $2,4,5,9,10$ are routers. Also, every node's bandwidth is denoted as $b_{\text{<node id>}}$.

Let's say that the clients in this graph have the following payments: $\text{pmt}_1 = \$30, \text{pmt}_3 = \$40, \text{pmt}_6 = \$35, \text{pmt}_7 = \$40, \text{pmt}_8 = \$45$.

$d(c)$ in the above graph $G$

For the graph above, we have $d(1)=2, d(3)=2, d(6)=3, d(7)=4, d(8)=3$.

Below are five problems for you to solve. Problems 1-5 are cumulative. That is they build upon the previous problem and get progressively harder to solve.

The Problem

You just remembered what you learned in CSE 331 when trying to solve a problem: try to reduce it to a known problem that you've already seen. So this problem is a toy version of the actual problem and thus the constraints are not very harsh.

Now, each router "bandwidth" is set to infinity. In other words, routers can transmit as many packets concurrently as needed. All $\alpha_c$ is set to $1$, implying clients are not very tolerant of slow Internet. See the part on penalty for more details.

Input

You are given ForProfitOnly's communication graph $G = (V,E)$, the content provider node $i$, a set of clients $C\subseteq V \setminus \{i\}$, bandwidth size $b_u$ for every router $u$, and for all clients you are given their tolerance threshold, the payment they make, and their priorities (which are set to a default value). In summary, following is the input:

$G = (V, E)$
$i \in V$
$C$ s.t. $C \subseteq V \setminus \{i\}$
For all $u \in V \setminus \{i\}$, $b_u$ s.t. $b_u = \infty$
For all $c \in C$, $\alpha_c$ s.t. $\alpha_c = 1$
For all $c \in C$, $\text{priority(c)} =$ PRIORITY_DEFAULT

Penalty

The notion of penalty for this problem is the revenue loss that ForProfitOnly has to face. In this problem, it is possible to lose money only if some clients unsubscribe from ForProfitOnly due to its poor service (slow internet). A client $c \in C$ may unsubscribe from ForProfitOnly if $c$'s internet is slow enough to "beat" $c$'s tolerance threshold $\alpha_c$.

More precisely, let $P'_c$ be the $i-c$ path generated by your algorithm to route packets from $i$ to $c$. Then if $D(P'_c)$ exceeds $\alpha_c \cdot d(c)$, then $c$ unsubscribes from ForProfitOnly, and ForProfitOnly does not receive $c$'s payment $\text{pmt}_c$. This causes a drop in ForProfitOnly's revenue. Thus, the penalty that ForProfitOnly faces from client $c$ is either $\text{pmt}_c$ or nothing (which is 0). This calculation is done by the $pen_0$ function for each client $c \in C$. Below is a formal description of penalty function:

$pen_0(c, D(P'_c),\alpha_c, d(c),\text{pmt}_c)$ is the penalty function that accounts for the client/revenue loss that ForProfitOnly faces due to client $c \in C$. $pen_0$ has five inputs:
- client $c \in C$
- $D(P'_c)$ which is the total delay of $i-c$ path generated by your algorithm
- $\alpha_c$ which is the tolerance of client $c$
- $d(c)$ which is the minimum delay of any $i-c$ path
- $\text{pmt}_c$ for $c \in C$

If $D(P'_c) > \alpha_c \cdot d(c)$, then client $c$ unsubscribes from ForProfitOnly(and subscribes to some other ISP or say uses their cell phone as a way of connecting to the internet). So you lose their portion of the revenue. Otherwise, $pen_0(c,D(P'_c),\alpha_c,d(c),\text{pmt}_c)$ outputs $0$.

Thus, for this problem, $pen_0(c,D(P'_c),\alpha_c,d(c),\text{pmt}_c) = \begin{cases} \text{pmt}_c &\text{if} \quad D(P'_c) >\alpha_c \cdot d(c) \\ 0 &\text{ otherwise} \end{cases}$

Revenue

ForProfitOnly receives a payment $\text{pmt}_c$ from every client $c \in C$ unless $c$ has unsubscribed from ForProfitOnly's services. This means that ForProfitOnly receives nothing or a $0$ payment from any client $c$ who has unsubscribed from its services. Thus, we can define revenue from client $c$ as the payment received from $c$ minus the penalty faced due to $c$. This is calculation is done by the $rev$ function for each client $c \in C$. Below is a formal description of $rev$ function:

Let $rev(c, D(P'_c),\alpha_c,d(c),\text{pmt}_c)$ be the revenue received from client $c$. Here, $rev(c, D(P'_c),\alpha_c,d(c),\text{pmt}_c) = \text{pmt}_c - pen_0(c,D(P'_c),\alpha_c,d(c),\text{pmt}_c)$

Now that we defined revenue for each $c \in C$, we define total revenue to be the sum of the revenue received from each $c \in C$.

Thus, total revenue = $\sum_{c\in C} rev(c,D(P'_c),\alpha_c,d(c),\text{pmt}_c)$

Output

You need to come up with an algorithm that generates one $i-c$ path to route packets from $i$ to $c$, for each $c \in C$. You should output a list of $i-c$ paths for all $c \in C$. There can be multiple $i-c$ paths from $i$ to $c$, but your algorithm should generate an $i-c$ path that contributes towards satisfying the objective (see below) for this problem. To put it formally, you need to output:

$L_{P'}$ which is a list of $P'_c$ for all $c \in C$

Objective

Maximize total revenue (over all possible choices of $i-c$ paths for each $c\in C$).

Hint

The optimal solution for this problem is very closely related to a homework problem that y'all have already seen in this course.

Example 1

A Solution

If the graph $G$ for this problem is our graph from Example 0, then here is a valid output (see the figure below):

That is, the output $L_{P'} = [P'_1,P'_3,P'_6,P'_7,P'_8]$. Where, $P'_1 = [0,10,1], P'_3 = [0,9,3], P'_6 = [0,9,3,6], P'_7 = [0,10,1,4,7], P'_8 = [0,9,3,8]$.

Since each $b_c = \infty$ ,for $c \in \{1,3,6,7,8\}$, the optimal routing protocol will incur a delay $d(c)$ for each $c$. This is because for each path P’_c, we will have $D(P'_c) = d(c)$ (see below for bit more details). Thus, for all $c \in C$, $pen_0(c) = 0$ because $D(P'_c) = d(c)$. So $rev(c) = \text{pmt}_c$, and thus total revenue would simply be the sum of payments from each client.

Justification for claim on revenue

Since all $b_c = \infty$, the routing protocol will incur a delay of $d(c)$. This is because for each path $P’_c$, we will have $D(P’_c)$ is the number of edges in $P'_c$ and further, for each $P’_c$ above, this is also $d(c)$. Thus, in this case we have $pen_0(c) = 0$. For example, we have $d(1)=2$, which is also the number of edges in $P'_2$: i.e. $D(P’_1) = 2$. Since $d(1)$ is the shortest possible delay we have found an optimal solution for path $P'_1$ and experience no penalty. A similar argument works for the rest of the clients.

Note that:

$D(P’_1) = 2 = d(1) $
$D(P’_3) = 2 = d(3) $
$D(P’_6) = 3 = d(6) $
$D(P’_7) = 4 = d(7) $
$D(P’_8) = 3 = d(8) $

So, total revenue $= \$30+ \$40 + \$35 + \$40 + \$45 = \$190$, which is the maximum possible revenue.

The Problem

Consider the allegation made by the NY AG against Spectrum on page 6 and point 4 from the AG's allegations

....Spectrum-TWC failed to deliver on this promise by leasing to a large number of its subscribers older-generation modems and wireless (or "WiFi") routers that it knew were incapable of achieving the promised Internet speeds. In addition, Spectrum-TWC failed to make adjustments to its network, such as reducing the size of service groups and increasing the number of channels for each service group, that would enable a subscriber to achieve the promised speeds. Not only did Spectrum-TWC fail to deliver the promised Internet speeds, it repeatedly assured subscribers that they could achieve the same results with wireless as with a wired connection, even when it knew that the wireless connection suffered from unavoidable, real-world limitations.

From the above allegation, Spectrum's routers seem to have had limited bandwidths that were incapable of providing the promised internet speeds to its customers.

In the previous toy problem, every router had an infinite bandwidth. This was a hypothetical assumption because there are some real-world limitations to the data transfer capacity (bandwidth). So for this problem, the bandwidth for each router will be limited.

Capturing bandwidth by a single number

As mentioned above there are many factors that determine the bandwidth for a client. In this project, we will capture this by a single number, i.e. the value $b_u$ for all $u\in V$.

Also, to be more realistic, the tolerance threshold for any client need not be 1, since different people have varying levels of patience.

Perfect knowledge of $\alpha_c$

In this project we will assume the prefect knowledge of $\alpha_c$ (as well as the related quantity $\beta_c$ that we will introduce in Problem 3), which is not possible in real life. We made this simplifying assumption to model the case that in real-life companies have data about their customers, which they can use to glean various information about them.

The allegation also says that Spectrum failed to make some necessary adjustments in its network that was necessary for it to deliver the promised internet speeds to its customers. Thus, the $i-c$ paths for all $c \in C$ that your algorithm generates could also determine how many of ForProfitOnly's clients are satisfied with its services.

Input

The input for the problem is the same as the previous one except for the bandwidth being limited and the tolerance threshold for every client being an arbitrary value greater than or equal to $1$. To put it formally, following is the input:

$G = (V, E)$
$i \in V$
$C$ s.t. $C \subseteq V \setminus \{i\}$
For all $u \in V \setminus \{i\}$, $b_u$ s.t. $b_u < \infty$
For all $c \in C$, $\alpha_c$ s.t. $\alpha_c \ge 1$
For all $c \in C$, $\text{pmt}_c$
For all $c \in C$, $\text{priority(c)} =$ PRIORITY_DEFAULT

Note

The highlighted input, is the part of the input that is different from the previous problem.

Penalty

Same as Problem 1

Revenue

Same as Problem 1

Output

Now given these real-world limitations, you should come up with an algorithm that generates $i-c$ paths for each client $c \in C$, in a way that contributes towards achieving the objective. Just like Problem 1, you should output a list of $i-c$ paths for all $c \in C$. That is, you need to output:

$L_{P'}$ which is a list of $P'_c$'s for all $c \in C$

Objective

Same as Problem 1.

Example 2

A Solution

If the graph $G$ for this problem is our graph from Example 0, then here is a valid output:

Note

The $\alpha$ values given above will be used in the example graph for the remaining problems also (except for a small change to $\alpha_3$ in Problem 5).

That is, the output $L_{P'} = [P'_1,P'_3,P'_6,P'_7,P'_8]$. Where, $P'_1 = [0,10,1], P'_3 = [0,10,1,2,3], P'_6 = [0,10,1,5,6], P'_7 = [0,10,1,4,7], P'_8 = [0,9,3,8]$.

We will consider the paths given above to compute the penalties for each client. So for path $1$, $\alpha_1\cdot d(1)$ is $1 \cdot 2$, which is $2$. Next we compare that to our $D(P’_1)$, by finding the number of edges in each path and making sure that there is enough bandwidth to transfer packets each tick. If our $D(P’_c)$ is less than or equal to $\alpha_c\cdot d(c)$ value we receive no penalty. For notational convenience (in our worked out calculation below), if $D(P’_c) \leq \alpha_c \cdot d(c)$ we say “accept”, else “reject”.

Total Revenue

We claim that the revenue generated from the above solution is $\$155$ while the solution from Example 1 will generate a total revenue of $\$110$ for this input. Click the button below to see more details

See calculations for total revenue generated by above solution (as well as that for Example 1) for this problem

Determining $D(P')$ for every client

We claim that: $D(P’_1) = 2, D(P’_3) = 4, D(P’_6) = 4, D(P’_7) = 4, D(P’_8) = 3$. We verify this by tracing each time step in the routing simulation:

`At Time Tick $0$:`

Current: All packets at 0.

Passed on: All

`At Time Tick $1$:`

Current:

$\text{pkt}_1$ at node $10$
$\text{pkt}_3$ at node $10$
$\text{pkt}_6$ at node $10$
$\text{pkt}_7$ at node $10$
$\text{pkt}_8$ at node $9$

Passed on: All

`At Time Tick $2$:`

Current:

$\text{pkt}_1$ at node $1$
$\text{pkt}_3$ at node $1$
$\text{pkt}_6$ at node $1$
$\text{pkt}_7$ at node $1$
$\text{pkt}_8$ at node $3$

Reached: $\text{pkt}_1$

Passed on: $\text{pkt}_3, \text{pkt}_6, \text{pkt}_7,\text{pkt}_8$

`At Time Tick $3$:`

Current:

$\text{pkt}_3$ at node $2$
$\text{pkt}_6$ at node $5$
$\text{pkt}_7$ at node $4$
$\text{pkt}_8$ at node $8$

Reached: $\text{pkt}_8$

Passed on: $\text{pkt}_3, \text{pkt}_6, \text{pkt}_7$

`At Time Tick $4$:`

Current:

$\text{pkt}_3$ at node $3$
$\text{pkt}_6$ at node $6$
$\text{pkt}_7$ at node $7$

Reached: All packets have reached their destination so routing terminates.

Determining Penalty and Calculating total revenue

Now lets see what $pen_0$ function outputs for each client:

$pen_0(1) = 0$

$D(P’_1) = 2 , d(1) \cdot \alpha_1 = 2, 2 \leq 2$, so accept

$pen_0(3) = 0$

$D(P’_3) = 4 , d(3) \cdot \alpha_3 = 8, 4 \leq 8$, so accept

$pen_0(6) = 35$

$D(P’_6) = 4 , d(6) \cdot \alpha_6 = 3, 4 > 3$, so reject

$pen_0(7) = 0$

$D(P’_7) = 4 , d(7) \cdot \alpha_7 = 4, 4 \leq 4$, so accept

$pen_0(8) = 0$

$D(P’_8) = 3 , d(8) \cdot \alpha_8 = 3, 3 \leq 3$, so accept

Our total revenue is calculated by subtracting the summation of all penalties from our total possible revenue.

Total revenue $= 190 - 35 = 155$

Example 1 solution

The solution to Problem 1 is a worse solution for this problem. We will go through the calculations to see what total revenue generated by using Example 1's solution for this problem.

Solution to Example 1

In the above picture we use Example 1's solution to solve this problem. Now we will see, why this solution is worse for this problem.

Determining $D(P')$ for every client

We claim that: $D(P’_1) = 2, D(P’_3) = 2, D(P’_6) =4, D(P’_7) = 4, D(P’_8) = 5$. Let's now trace each time tick in the routing simulation:

`At Time Tick $0$:`

Current: All packets at 0.

Passed on: All

`At Time Tick $1$:`

Current:

$\text{pkt}_1$ at node $10$
$\text{pkt}_3$ at node $9$
$\text{pkt}_6$ at node $9$
$\text{pkt}_7$ at node $10$
$\text{pkt}_8$ at node $9$

Passed on: $\text{pkt}_1, \text{pkt}_3, \text{pkt}_7$

Delayed: $\text{pkt}_6, \text{pkt}_8$

`At Time Tick $2$:`

Current:

$\text{pkt}_1$ at node $1$
$\text{pkt}_3$ at node $3$
$\text{pkt}_6$ at node $9$
$\text{pkt}_7$ at node $1$
$\text{pkt}_8$ at node $9$

Reached: $\text{pkt}_1, \text{pkt}_3$

Passed on: $\text{pkt}_6, \text{pkt}_7$

Delayed: $\text{pkt}_8$

`At Time Tick $3$:`

Current:

$\text{pkt}_6$ at node $3$
$\text{pkt}_7$ at node $4$
$\text{pkt}_8$ at node $9$

Passed on: $\text{pkt}_6, \text{pkt}_7, \text{pkt}_8$

`At Time Tick $4$:`

Current:

$\text{pkt}_6$ at node $6$
$\text{pkt}_7$ at node $7$
$\text{pkt}_8$ at node $3$

Reached: $\text{pkt}_6, \text{pkt}_7$

Passed on: $\text{pkt}_8$

`At Time Tick $5$:`

Current:

$\text{pkt}_8$ at node $8$

Reached: $\text{pkt}_8$

NOTE: Some of the $D(P'_c)$ values have changed from the previous solution due to bandwidth restrictions.

Determining Penalty and Calculating total revenue

Now let us see what $pen_0$ function outputs for each client:

$pen_0(1) = 0$

$D(P’_1) = 2 , d(1) \cdot \alpha_1 = 2, 2 \leq 2$, so accept

$pen_0(3) = 0$

$D(P’_3) = 2 , d(3) \cdot \alpha_3 = 8, 2 \leq 8$, so accept

$pen_0(6) = 35$

$D(P’_6) = 4 , d(6) \cdot \alpha_6 = 3, 4 > 3$, so reject

$pen_0(7) = 0$

$D(P’_7) = 4 , d(7) \cdot \alpha_7 = 4, 4 \leq 4$, so accept

$pen_0(8) = 45$

$D(P’_8) = 5 , d(8) \cdot \alpha_8 = 3, 5 > 3$, so reject

So the total revenue $ = \$190 - (\$35 + \$45) = \$110$. Hence, this is definitely worse than the previous solution for this problem.

The Problem

Now consider this allegation made by the NY AG against Spectrum on page 9 and point 14 from the AG's allegations:

Spectrum-TWC fraudulently induced at least 640,000 subscribers in New York State to sign up for high-speed plans that it knew it could not provide. SpectrumTWC knowingly failed to allocate sufficient bandwidth to subscribers, which it could have done either by reducing the size of its service groups or adding more channels to each service group.

Thus for this problem, you are allowed to increase the bandwidth for every router, that is you can increase $b_u$ for all $u \in V \setminus \{i\}$ at a cost of $\$Z$ per increase in bandwidth.

Simplification/Motivation for $Z$

As alluded to above, increase the bandwidth for a node actually means changing the hardware and hence, this change has a real life cost. However, to simplify the problem we are assuming that there is a per-unit cost associated with increasing the bandwidths while in real life, these cost increases comes in quantums.

Let $X$ be the total increase of bandwidths over all routers. For any router $u \in V \setminus \{i\}$, let $b_u$ be its original bandwidth. And let $b'_u$ be the new increased bandwidth of $u$. If you chose not to increase the bandwidth of $u$, then $b_u = b'_u$. We define $X$ to be \[\sum_{u \in V \setminus \{i\}} \max(0,b'_u - b_u).\]

Why the $\max$ term?

The $\max$ term above seems un-necessary because one would expect $b'_u\ge b_u$. However, since your code will be outputting the $b'_u$ values, the $\max$ above makes it so that y'all have no incentive to make $b'_u<b_u$.

For this problem, we also introduce an additional parameter, $\beta_c$ which is the complaint threshold ($\beta_c \le \alpha_c$). A client $c$ may "complain" if $\beta_c \cdot d(c) < D(P'_c)$.

Can a client Complain and Unsubscribe at the same time?🤔

In a particular case where $D(P'_c) > \beta_c \cdot d(c)$ and $D(P'_c) > \alpha_c \cdot d(c)$, means that here the client $c$ both complains and unsubscribes from ForProfitOnly's services. In this case its a double whammy for ForProfitOnly.

Let $S$ be a subset of clients, and let $\rho_{\text{fcc}}$ and $\rho_{\text{lawsuit}}$ be a real numbers between $0$ and $1$. Let $Comp$ be a subset of clients in $S$ ($Comp \subseteq S$) that complain, that is for all $c \in Comp$, $D(P'_c) > \beta_c \cdot d(c)$ (and for $c\not\in Comp$, they do not satisfy this constraint).

If the size of $Comp$ is big enough, then it is safe to assume that the Office of the Attorney General will also have received a sizable number of complaints, prompting it to investigate potential wrongdoing and to consider filing a lawsuit to enforce laws that prohibit fraudulent or deceptive business practices and false advertising. In Spectrum's case, where since 2015 the OAG fielded over 2,800 reports from Spectrum's subscribers who complained about Spectrum's poor internet service.

A relevant allegation from the AG's summons and complaints that states this on page 12 and point 24:

Since 2015, the OAG has fielded over 2,800 reports from Spectrum-TWC subscribers who complained that they did not receive the Internet service promised to them in Spectrum-TWC advertisements.

And ultimately, a lawsuit was filed against Spectrum. In case you're curious about what the complaints from Spectrum's subscribers looked like, please see page 12 and point 25 of the AG's allegations . Now, this brings us to the first case of this problem.

Case 1 (Lawsuit): If $|Comp| \ge \lfloor \rho_{\text{lawsuit}} \cdot |C| \rfloor$, then a lawsuit will be filed against ForProfitOnly, and ForProfitOnly would end up paying an amount $\$A$ for settlement. (Also note that in this case we set $S=C$.)

When does OAG start an investigation?

The basic idea is that as the number of customer complaints increases, the likelihood of an enforcement action (lawsuit) by the Attorney General increases. This makes intuitive sense and seems to capture an important piece of how agencies decide whether to take action in the real world. That said, there are many other factors that influence a decision to bring a lawsuit – e.g. the possibility of deterrence by taking on a “high profile” target, the agency leadership’s idiosyncratic priorities, the political benefit to the agency, desire for good headlines, etc. So it can certainly happen that an enforcement action begins with only a few complaints—or even with none, if someone in the AG’s office chooses to undertake an investigation for some other reason. We stress that the above is a stylized model and that you shouldn’t assume that you can get away with breaking the law if you somehow manage to avoid complaints being filed.

Did you know? 🤔

In the real world, as per the way the deceptive-business-practice laws are structured, the court could impose non-monetary remedies (i.e. “injunctions”) for the victim (clients) if the company is found to have violated the law. That is the court could issue a court-order requiring the company to implement specific measures going forward in order to fix the deceptive/fraudulent practice. (E.g. ordering the company to swap out all D2 modems for D3 in Spectrum's case). These kinds of court-ordered changes will often be costly to implement, but the company must comply irrespective of how much it costs to do so. In the context of this problem, it is very likely (in the real world) for the court to order ForProfitOnly to increase the bandwidth of all routers if ForProfitOnly was found to have violated the law.

Did you know? 🤔

The court (in the real-world) may also impose a "flat rate" civil penalty of $\$5,000$ per violation of the the deceptive-business-practice laws. (Depending on what counts as a single "violation", this could theoretically end up being a huge number.)

Settlement

As noted above, the court has many options in how it could rule in a deceptive business practices case. In this project, we made the simplifying assumption that an out of court settlement would be reached. Indeed Spectrum ended up paying $\$174$ million on a lawsuit settlement .

We now move to the second case. In early 2013, the FCC administered internet speed tests and found that Spectrum did not deliver internet speeds that it promised. Here is the AG's allegation that states it (page 8 and point 10):

To conceal this failure, Spectrum-TWC assured the FCC in or about July 2013, that it would replace its older-generation modems for all of its subscribers, but in fact it did not. The FCC relied on that commitment to exclude the poor results of the speed tests on those modems in the FCC's subsequent public reports. Had these modems' results been included in the FCC's testing program, they would have revealed Spectrum-TWC's deceptive practices.

FCC's authority

We will assume that the FCC has separate legal authority to impose fines/penalties if it finds that an ISP is not delivering promised internet speeds, and further assume that the FCC is very strict about imposing such fines.

This brings us to case 2.

Case 2 (FCC testing): Now, the subset of clients $S$ is used by the FCC to test internet speeds. If $|Comp| \ge \lfloor \rho_{\text{fcc}} \cdot |S| \rfloor$, then the FCC would impose a legal fine amount $\$B$ that ForProfitOnly would have to pay.

Input

In addition to the input from the previous problem, you are given the subset $S$ of clients as an input, the complaint threshold $\beta_c$ for all $c \in C$, $\rho_{\text{lawsuit}}$ and $\rho_{\text{fcc}}$ corresponding to the two cases above, $\$A$ which is the lawsuit settlement amount, $\$B$ which is the FCC fine amount, and $\$Z$ as stated in the problem definition above. In summary, following is the input:

$G = (V, E)$
$i \in V$
$C$ s.t. $C \subseteq V \setminus \{i\}$
$S$ s.t. $S \subseteq C$
For all $u \in V \setminus \{i\}$, $b_u$ s.t. $b_u < \infty$
For all $c \in C$, $\alpha_c$ and $\beta_c$ s.t. $\alpha_c \geq \beta_c \geq 1$
For all $c \in C$, $\text{pmt}_c$
For all $c \in C$, $\text{priority(c)} =$ PRIORITY_DEFAULT
$\rho_{\text{lawsuit}}$, s.t. $0 \leq \rho_{\text{lawsuit}} \leq 1$
$\rho_{\text{fcc}}$, s.t. $0\leq \rho_{\text{fcc}}\leq 1$
$\$A$, which is the lawsuit amount.
$\$B$, which is the FCC fine amount
$\$Z$, which is the cost of unit increase in bandwidth

Note

The highlighted input is the part of the input that is different from the previous problem.

Penalty

The notion of penalties for this problem is two-fold. In addition to the loss of revenue if $D(P'_c)$ exceeds $\alpha_c \cdot d(c)$, if at least $\lfloor \rho \cdot |T| \rfloor$ number of clients in $T$ complain, then ForProfitOnly might have to pay a lawsuit settlement amount $\$A$ due to case 1 or a legal fine amount $\$B$ to the FCC due to case 2. The actual definition of $T$ will depend on which of the two cases is under consideration.

For $pen_0(c,D(P'_c),\alpha_c,d(c),\text{pmt}_c)$, please refer to Problem 1.

$pen_1(T,L_{P'},L_{\beta},L_{D},\rho, L)$ is the second penalty function that accounts for the additional penalty if the lawsuit is filed or FCC imposes a fine. $pen_1(T,L_{P'},L_{\beta},L_{D},\rho, L)$, has six input parameters:
- $T$ which is a subset of clients ($T \subseteq C$)
- $L_{P'}$ which is a list of $i-c$ paths for all $c \in S$
- $L_{\beta}$ which is a list of $\beta_c$ values for all $c \in S$
- $L_{D}$ which is a list of $d(c)$ values for all $c \in S$
- $\rho$ is a real number between $0$ and $1$.
- $L$ which is the legal penalty amount.
If at least $\lfloor \rho \cdot |T| \rfloor$ clients in $T$ complain (recall $c\in T$ complains if $D(P'_c) > \beta_c\cdot d(c)$), then $pen_1$ outputs $L$. Else $pen_1$ outputs $0$. We will use the same function $pen_1$ to model the penalties in both case 1 and case 2.

Revenue

The revenue obtained from each client is determined by the same rev function from Problem 1. Now, total revenue is defined separately for case 1 and case 2. For case 1, total revenue is defined as the sum of revenue obtained from each $c \in C$, minus the possible lawsuit settlement amount $\$A$ (here the set "$T$" needed in $pen_1$ is $C$) and $\$(X \cdot Z)$ which is the cost of increasing bandwidth (with $\rho=\rho_{\text{lawsuit}}$). For case 2, total revenue is defined as the sum of revenue obtained from each $c \in C$, minus the possible fine amount $\$B$ (here the set "$T$" is $S$ and $\rho=\rho_{\text{fcc}}$) imposed by the FCC and $\$(X \cdot Z)$ which is defined above. Below is a mathematical description of total revenue for both cases:

$rev(c,D(P'_c),\alpha_c,d(c),\text{pmt}_c)$ is the same as in Problem 1.

Total Revenue for case 1: $\left[ \sum_{c \in C} rev(c,D(P'_c),\alpha_c,d(c),\text{pmt}_c) \right] - \left[ pen_1(C,L_{P'},L_{\beta},L_{D},\rho_{\text{lawsuit}}, A) + (X \cdot Z) \right]$

Total Revenue for case 2: $\left[ \sum_{c \in C} rev(c,D(P'_c),\alpha_c,d(c),\text{pmt}_c) \right] - \left[ pen_1(S,L_{P'},L_{\beta},L_{D},\rho_{\text{fcc}}, B) + (X\cdot Z) \right]$
Total Revenue for both cases: For some inputs your code will have to handle both cases together, in which case the revenue will be $\left[ \sum_{c \in C} rev(c,D(P'_c),\alpha_c,d(c),\text{pmt}_c) \right] - \left[pen_1(C,L_{P'},L_{\beta},L_{D},\rho_{\text{lawsuit}}, A) + pen_1(S,L_{P'},L_{\beta},L_{D},\rho_{\text{fcc}}, B) + (X\cdot Z) \right]$

Note that we used the same $pen_1$ function (though with different parameters) to model the penalty due to lawsuit and FCC fines.

Output

As before you need to come up with an algorithm that generates $i-c$ paths for each $c \in C$, so you should output a list of $i-c$ paths for all $c \in C$. But for this problem you also need to output a list of bandwidth values for all routers (since you might have increased the bandwidth of some/all/no routers). To put it formally, you need to output:

$L_{P'}$ which is a list of $P'_c$'s for all $c \in C$

$L_{b'}$ which is a list of (updated) bandwidth $b'$ values for all $u \in V \setminus \{i\}$. Note that $X = \sum_u (b'_u-b_u)$.

What if $b'_u< b_u$ for some $u$?

The way $X$ is defined, if you make $b'_u<b_u$, then you will not "make" money by reducing the bandwidth. On the other hand, when computing the delays of your paths, the routing algorithm will use the smaller $b'_u$ value, which means your path might end up with a higher delay, which can only hurt you.

Objective

Same as Problem 1.

Example 3

Sample Input and Output

Now assume the input graph $G$ to be our example graph from Example $0$. Let's say that $\rho_{\text{fcc}} = 0.5, \rho_{\text{lawsuit}} = 0.4, B = \$70, A = \$100, Z = \$15, S = \{3,6\}$.

Then, here is a valid output for this problem with the given constraints:

That is, the output $L_{P'} = [P'_1,P'_3,P'_6,P'_7,P'_8]$. Where, $P'_1 = [0,10,1], P'_3 = [0,9,3], P'_6 = [0,9,3,6], P'_7 = [0,10,1,4,7], P'_8 = [0,9,3,8]$.

Updated Bandwidths: $(8,7,4,2,2,4,1,1,5,2,7)$. That is, the bandwidth of nodes $3$ and $9$ is increased by one unit.

Penalties and delays are calculated in the same way as before. In order to find our total we sum together all of the penalties received from each customer.

Total Revenue

The total revenue for the solution above is $\$160$ while the total revenue for the solutions from Examples 1 and 2 are -$\$60$ and $\$85$ respectively. Please click the button below for the details.

Click here to see the revenue generated by above solutions (as well as those from Example 1 and 2) for this problem

Determining $D(P')$ for every client

We claim that: $D(P’_1) = 2, D(P’_3) = 4, D(P’_6) =3, D(P’_7) = 4, D(P’_8) = 3$. Let's now trace each timestep in the routing of the packets.

`At Time Tick $0$:`

Current: All packets at 0.

Passed on: All

`At Time Tick $1$:`

Current:

$\text{pkt}_1$ at node $10$
$\text{pkt}_3$ at node $10$
$\text{pkt}_6$ at node $9$
$\text{pkt}_7$ at node $10$
$\text{pkt}_8$ at node $9$

Passed on: All

`At Time Tick $2$:`

Current:

$\text{pkt}_1$ at node $1$
$\text{pkt}_3$ at node $1$
$\text{pkt}_6$ at node $3$
$\text{pkt}_7$ at node $1$
$\text{pkt}_8$ at node $3$

Reached: $\text{pkt}_1$

Passed on: $\text{pkt}_3, \text{pkt}_6, \text{pkt}_7, \text{pkt}_8$

`At Time Tick $3$:`

Current:

$\text{pkt}_3$ at node $2$
$\text{pkt}_6$ at node $6$
$\text{pkt}_7$ at node $4$
$\text{pkt}_8$ at node $8$

Reached: $\text{pkt}_6, \text{pkt}_8$

Passed on: $\text{pkt}_3, \text{pkt}_7$

`At Time Tick $4$:`

Current:

$\text{pkt}_3$ at node $3$
$\text{pkt}_7$ at node $7$

Reached: All packets have reached their destination so routing terminates.

Determining Penalty

Now lets see what $pen_0$ function outputs for each client:

$pen_0(1) = 0$

$D(P’_1) = 2 , d(1) \cdot \alpha_1 = 2, 2 \leq 2$, so accept

$pen_0(3) = 0$

$D(P’_3) = 4 , d(3) \cdot \alpha_3 = 8, 4 \leq 8$, so accept

$pen_0(6) = 0$

$D(P’_6) = 3 , d(6) \cdot \alpha_6 = 3, 3 \leq 3$, so accept

$pen_0(7) = 0$

$D(P’_7) = 4 , d(7) \cdot \alpha_7 = 4, 4 \leq 4$, so accept

$pen_0(8) = 0$

$D(P’_8) = 3 , d(8) \cdot \alpha_8 = 3, 3 \leq 3$, so accept

Now let's see what the $pen_1$ function outputs. In order to discover whether or not a customer complains, we will first multiply $d(c)$ with the $\beta_c$ modifier. For path $d(1)$ that is $\beta_1 \cdot d(1) = 1 \cdot 2$, which is $2$. Next we compare that to our $D(P’_1)$ which is $2$. Since our $D(P’_1)$ is not less than our $\beta_1 \cdot D(1)$, the customer does not complain. In the same way, we can check this for all other clients:

Client Node 1	$D(P'_1)=2, \beta_1 \cdot d(1)=2$	does not complain
Client Node 3	$D(P'_3)=4, \beta_3 \cdot d(3)=4$	does not complain
Client Node 6	$D(P'_6)=3, \beta_6 \cdot d(6)=3$	does not complain
Client Node 7	$D(P'_7)=4, \beta_7 \cdot d(7)=4$	does not complain
Client Node 8	$D(P'_8)=3, \beta_8 \cdot d(8)=3$	does not complain

Calculating total revenue

Total Complains:

FCC: 0

Lawsuit:0

Now that we have our total of complaining customers we find the fraction of the group they represent and compare it to our $\rho$ values (i.e. $\rho_{\text{lawsuit}}$ and $\rho_{\text{fcc}}$ for the two cases). If the fraction of complaining clients $> \rho$, then no fine is awarded.

FCC: $\frac{0}{5} < 0.5$, i.e., NO fine

Lawsuit: $\frac{0}{5} < 0.4$, i.e., NO lawsuit

Thus, $pen_1 = 0$ (for both cases).

Now, in order to calculate the revenue we subtract $pen_0$ and $pen_1$, and our bandwidth changes from our total possible revenue.

So, total revenue $= \$190 - \$0 - \$0 - (2 \cdot \$15) = \$160 $

Example 1 solution

Both Example 1 and Example 2 solutions will be a worse solutions for this problem.

The figure below shows Example 1's solution being used to solve this problem.

NOTE: In problem 1 there was no increase of bandwidth for any router.

Now here is a quick reference to Example 1's solution: $P'_1 = [0, 10, 1], P'_3 = [0, 9, 3], P'_6 = [0, 9, 3, 6], P'_7 = [0, 10, 1, 4, 7], P'_8 = [0, 9, 3, 8]$ and $D(P’_1) = 2, D(P’_3) = 2, D(P’_6) =4, D(P’_7) = 4, D(P’_8) = 4$

The total $pen_0$ across all clients remains the same as Problem 2: $\$80$ ($pen_0(1)=0,pen_0(3)=0,pen_0(6)=35,pen_0(7)=0,pen_0(8)=45$). Now, $pen_1$ outputs the following:

Client Node 1	$D(P'_1)=2, \beta_1 \cdot d(1)=2$	does not complain
Client Node 3	$D(P'_3)=2, \beta_3 \cdot d(3)=4$	does not complain
Client Node 6	$D(P'_6)=4, \beta_6 \cdot d(6)=3$	Complains!
Client Node 7	$D(P'_7)=4, \beta_7 \cdot d(7)=4$	does not complain
Client Node 8	$D(P'_8)=4, \beta_8 \cdot d(8)=3$	Complains!

Calculating Revenue

Now let's compare our results with the corresponding $\rho$ values and see if fines occur:

FCC: $\frac{1}{2} \ge 0.5$

Lawsuit: $\frac{2}{5} \ge 0.4$

Thus, both the settlement amount and FCC fine have to be paid and this, $pen_1 = \$170$, so total revenue $= \$190 - \$170 - \$80 -\$0= -\$60$.

Example 2 solution

The figure below shows Problem 2's example solution being used to solve this problem.

NOTE: In problem 2 there was no increase of bandwidth for any router.

For a quick reference, these were the delay's produced by our solution algorithm for Problem 2's example: $D(P’_1) = 2, D(P’_3) = 4, D(P’_6) = 4, D(P’_7) = 4, D(P’_8) = 3$. And the output of the $pen_0$ function for clients in Problem 2 was: $pen_0(1) = 0, pen_0(3) = 0, pen_0(6) =35, pen_0(8) = 0$.

Problem 2 did not have the $pen_1$ function unlike this problem. So let's see what $pen_1$ outputs with our solutions for Problem 2.

Client Node 1	$D(P'_1)=2, \beta_1 \cdot d(1)=2$	does not complain
Client Node 3	$D(P'_3)=4, \beta_3 \cdot d(3)=4$	does not complain
Client Node 6	$D(P'_6)=4, \beta_6 \cdot d(6)=3$	Complains!
Client Node 7	$D(P'_7)=4, \beta_7 \cdot d(7)=4$	does not complain
Client Node 8	$D(P'_8)=3, \beta_8 \cdot d(8)=3$	does not complain

Calculating total revenue

Total Complains

Lawsuit: 1 and FCC = 1. Now, by comparing the corresponding $\rho$ values we get:

FCC: $\frac{1}{2} \ge 0.5$, i.e., there is a fine.

Lawsuit: $\frac{1}{5} < 0.4$, i.e., there is no lawsuit. Thus, $pen_1$ outputs $\$70$. So the total revenue $ = \$190 - \$70 - \$35 - \$0 = \$85$.

Another Input

Currently, we are able to avoid both the FCC fine and the lawsuit fines. This will not always be the case, consider if $Z = \$45$ and $B = \$40$. In this case the total revenue for the Example 3 solution becomes $=\$190-2\cdot\$45=\$100$. By contrast Example 2 solution becomes the better solution.

Click here to see how Example 2 solution will be a better solution for this problem with the $Z$ and $B$ values given above

Below is a picture showing Example 2 solution being used to solve the above updated problem:

Problem 2 did not have the $pen_1$ function unlike this problem. So let's see what $pen_1$ outputs with our solutions for Problem 2. (This is the same calculation that we did above for the earlier input-- nothing changes.)

Client Node 1	$D(P'_1)=2, \beta_1 \cdot d(1)=2$	does not complain
Client Node 3	$D(P'_3)=4, \beta_3 \cdot d(3)=4$	does not complain
Client Node 6	$D(P'_6)=4, \beta_6 \cdot d(6)=3$	Complains!
Client Node 7	$D(P'_7)=4, \beta_7 \cdot d(7)=4$	does not complain
Client Node 8	$D(P'_8)=3, \beta_8 \cdot d(8)=3$	does not complain

Calculating total revenue

Lawsuit: 1 and FCC = 1. Now, by comparing the corresponding $\rho$ values we get:

FCC: $\frac{1}{2} \ge 0.5$, i.e., there is a fine.

Lawsuit: $\frac{1}{5} < 0.4$, i.e. there is no lawsuit. Thus, $pen_1$ outputs $\$40$. So the total revenue $ = \$190 - \$40 - \$35 - \$0 = \$115$, which is better than the revenue of $\$100$ from the Example 3 solution.

The Problem

For this problem, you are allowed to set/change $\text{priority(c)}$ for all $c \in C$.

Coming back to the story of Spectrum, NY AG alleged Spectrum knowingly took full advantage of the fact that its subscribers had very few choices for some other ISP. Thus, this essentially forced many of Spectrum's subscribers to stick with Spectrum. But nevertheless, Spectrum continued to deceive its subscribers. Here is the relevant allegation against Spectrum by the AG that states it (page 12 and point 23):

Throughout the Relevant Period, Spectrum-TWC consistently failed to make the investments necessary to provide its subscribers with the Internet speeds and reliable online content that it had promised. Capitalizing on the fact that its subscribers had few, if any, other choices for an ISP, Spectrum-TWC placed profits ahead of the interests of its subscribers, and collected billions of dollars in fees from New York subscribers for providing Internet service.

Now, for this problem, you are given a subset $R$ of clients that live in rural areas where ForProfitOnly is a monopoly. Thus, every rural client has an infinite tolerance threshold, because rural clients will never unsubscribe from ForProfitOnly's services even if they are unhappy with the service because they simply do not have any other choice. However, rural clients can still complain. As per the above AG's allegation, Spectrum took advantage of the fact that it was a monopoly in the region.

Did you know? 🤔

The court may also order for the disgorgement of revenues that resulted from fraudulent and illegal practices (i.e. company has to turn over illegally gotten gains). In our problem, although the rural clients cannot unsubscribe (but of course they can complain) from ForProfitOnly's services, in the real-world if these complains are forwarded to the Office of the Attorney General (OAG), then it is very much likely that ForProfitOnly would have to turn over illegally gotten gains with interest to those affected by the action.

Input

In addition to the input from the previous problem, you are given the subset $R$ of rural clients such that, for each client $c \in R$, $\alpha_c$ is set to $\infty$. In summary, following is the input for this problem:

Graph $G = (V, E)$
$i \in V$
For all $u \in V \setminus \{i\}$, $b_u$ s.t. $b_u < \infty$
For all $c \in C$, $\alpha_c$ and $\beta_c$ s.t. $\alpha_c \geq \beta_c \geq 1$
For all $c \in C$, $\text{pmt}_c$
$S$ s.t. $S \subseteq C$
$\rho_{\text{lawsuit}}$ s.t. $0 \leq \rho_{\text{lawsuit}} \leq 1$
$\rho_{\text{fcc}}$ s.t. $0 \leq \rho_{\text{fcc}} \leq 1$
$\$A$, which is the lawsuit settlement amount
$\$B$, which is the FCC fine amount
$R$, the set of rural clients s.t. $R \subseteq C$
For all $c \in R$, $\alpha_c = \infty$.
For all $c \in C$, $\text{priority(c)} =$ PRIORITY_DEFAULT
$\$Z$, which is the cost of unit increase in bandwidth

Note

The highlighted input is the part of the input that is different from the previous problem.

Penalty

Same as Problem 3.

Revenue

Same as Problem 3.

Output

Again, for this problem you should output a list of $i-c$ paths for all $c \in C$ generated by your algorithm, a list of $\text{priority(c)}$ for all $c \in C$ (since you might have changed the priority of some/all/no clients in $C$), and like the previous problem a list of bandwidth values for all routers. To put it formally, you should output:

$L_{P'}$, which is a list of $P'_c$'s for all $c \in C$
$L_{priority}$, which is a list of $\text{priority(c)}$ values for all $c \in C$
$L_{b'}$, which is a list of new bandwidth values $b'_u$ values for all $u \in V \setminus \{i\}$. As in Problem 3, $X = \sum_u (b'_u-b_u)$

Objective

Same as Problem 1.

Did you know? 🤔

All the possible monetary and non-monetary remedies (that can possibly be imposed by the court for a violation of the deceptive-business-practice laws ) described in all the Did you know's can also be imposed cumulatively by the court!

Example 4

Sample Input and Output

Now assume the input graph $G$ to be our example graph. Let's say that $\rho_{\text{fcc}} = 0.5, \rho_{\text{lawsuit}} = 0.4, B = \$70, A = \$100, Z = \$15, S = \{3,6\}$ same as our example for Problem 3. And now, let's say that $R = \{8\}$.

Then, here is a valid output for this problem with the given constraints (no bandwidth values are changed and neither are the packets' priorties):

That is, the output $L_{P'} = [P'_1,P'_3,P'_6,P'_7,P'_8]$. Where, $P'_1 = [0,10,1], P'_3 = [0,10,1,2,3], P'_6 = [0,9,3,6], P'_7 = [0,10,1,4,7], P'_8 = [0,10,1,5,8]$.

Delays and penalties are calculated almost the same as before, with one caveat, if a rural client complains they do not drop service and thus, no penalty is felt for $pen_0$.

Total Revenue

The total revenue generated from the above solution is $\$190$ while the solutions from Examples 1, 2 and 3 generate total revenues of $-\$15$, $\$95$ and $\$160$ respectively. Please click the button below for the detailed calculations.

Click here to see the revenue calculation for the above solution as well as those from Examples 1, 2 and 3

Determining $D(P')$ values

We claim that: $D(P’_1) = 2, D(P’_3) = 4, D(P’_6) =3, D(P’_7) = 4, D(P’_8) = 4$. Let's now trace each timestep in the routing of the packets.

`At Time Tick $0$:`

Current: All packets at 0.

Passed on: All

`At Time Tick $1$:`

Current:

$\text{pkt}_1$ at node $10$
$\text{pkt}_3$ at node $10$
$\text{pkt}_6$ at node $9$
$\text{pkt}_7$ at node $10$
$\text{pkt}_8$ at node $10$

Passed on: All

`At Time Tick $2$:`

Current:

$\text{pkt}_1$ at node $1$
$\text{pkt}_3$ at node $1$
$\text{pkt}_6$ at node $3$
$\text{pkt}_7$ at node $1$
$\text{pkt}_8$ at node $1$

Reached: $\text{pkt}_1$

Passed on: $\text{pkt}_3, \text{pkt}_6, \text{pkt}_7, \text{pkt}_8$

`At Time Tick $3$:`

Current:

$\text{pkt}_3$ at node $2$
$\text{pkt}_6$ at node $6$
$\text{pkt}_7$ at node $4$
$\text{pkt}_8$ at node $5$

Reached: $\text{pkt}_6$

Passed on: $\text{pkt}_3, \text{pkt}_7, \text{pkt}_8$

`At Time Tick $4$:`

Current:

$\text{pkt}_3$ at node $3$
$\text{pkt}_7$ at node $7$
$\text{pkt}_8$ at node $8$

Reached: All packets have reached their destination so routing terminates.

Determining Penalty

Now lets see what $pen_0$ function outputs for each client:

NOTE: For any client $c$, if $c \in R$, then $pen_0(c) = 0$ since we have $\alpha_c=\infty$

$pen_0(1) = 0$

$D(P’_1) = 2 , d(1) \cdot \alpha_1 = 2, 2 \leq 2$, so accept

$pen_0(3) = 0$

$D(P’_3) = 4 , d(3) \cdot \alpha_3 = 8, 4 \leq 8$, so accept

$pen_0(6) = 0$

$D(P’_6) = 3 , d(6) \cdot \alpha_6 = 3, 3 \leq 3$, so accept

$pen_0(7) = 0$

$D(P’_7) = 4 , d(7) \cdot \alpha_7 = 4, 4 \leq 4$, so accept

$pen_0(8) = 0$

$D(P’_8) = 4 , d(8) \cdot \alpha_8 = \infty, 4 \le \infty$. So accept.

Now let's see what the $pen_1$ function outputs. The $pen_1$ function works in the same way as Problem 3

Client Node 1	$D(P'_1)=2, \beta_1 \cdot d(1)=2$	does not complain
Client Node 3	$D(P'_3)=4, \beta_3 \cdot d(3)=4$	does not complain
Client Node 6	$D(P'_6)=3, \beta_6 \cdot d(6)=3$	does not complain
Client Node 7	$D(P'_7)=4, \beta_7 \cdot d(7)=4$	does not complain
Client Node 8	$D(P'_8)=4, \beta_8 \cdot d(8)=3$	complains

Calculating total revenue

Below are the total number of complaints for the two cases:

FCC: $0$

Lawsuit: $1$

Now that we have our total of complaining customers we find the fraction of the group they represent and compare it to our $\rho$ values. If the fraction of complaining clients < $\rho$ , then no fine is awarded.

FCC: $\frac{0}{5} < 0.5$, i.e., NO fine

Lawsuit: $\frac{1}{5} < 0.4$, i.e., NO lawsuit

Thus, $pen_1 = 0$ (for both cases).

Now, in order to calculate the revenue we subtract $pen_0$ and $pen_1$, and our bandwidth changes from our total possible revenue.

So, total revenue $= \$190 - \$0 - \$0 = \$190 $

Note

If we change $\rho_{\text{lawsuit}}$ to be $0.2$ (the remaining input is unchanged). Then $pen_1$ would result in the following:

FCC: $\frac{0}{2} > 0.5$, i.e., no fine is levied.

Lawsuit: $\frac{1}{5} \ge 0.2$, i.e., a lawsuit occurs.

So total revenue $ = \$190 - \$0 - \$100 = \$90 $

Example 1 solution

Now let's see how our results from previous examples compare on the same input as above. For examples 1 and 2 we will use just the paths and there will be no bandwidth changes or priorities taken into account since this was not defined in their example. Example 3 will have bandwidths increases but no priorities are changed.

To start with, let's use Example 1's solution for this problem (see figure below):

$pen_0$ will be calculated exactly the same way as we computed it for Example 1's solution for problem in Example 2 except as $8$ is a rural client, the penalty is only $\$35$. And for $pen_1$:

Client Node 1	$D(P'_1)=2, \beta_1 \cdot d(1)=2$	does not complain
Client Node 3	$D(P'_3)=2, \beta_3 \cdot d(3)=4$	does not complain
Client Node 6	$D(P'_6)=4, \beta_6 \cdot d(6)=3$	complains
Client Node 7	$D(P'_7)=4, \beta_7 \cdot d(7)=4$	does not complain
Client Node 8	$D(P'_8)=5, \beta_8 \cdot d(8)=3$	complains

Now, lets compare the results with the corresponding $\rho$ values to see if a fine occurs:

FCC: $\frac{1}{2} \ge 0.5$, i.e., there is a fine.

Lawsuit: $\frac{2}{5} \ge 0.4$, i.e., a lawsuit occurs.

So, $pen_1 = \$100 + \$70 = \$170$. And thus the total revenue $= \$190 - \$170 - \$35 = -\$15$. This is clearly a worse solution for this problem.

Example 2 solution

The picture below shows Example 2's solution being used to solve this problem:

Like Example 2 only $pen_0(6)=\$35$, and $pen_0$ for all other clients outputs $0$. Let's now see what $pen_1$ outputs:

Client Node 1	$D(P'_1)=2, \beta_1 \cdot d(1)=2$	does not complain
Client Node 3	$D(P'_3)=4, \beta_3 \cdot d(3)=4$	does not complain
Client Node 6	$D(P'_6)=4, \beta_6 \cdot d(6)=3$	complains
Client Node 7	$D(P'_7)=4, \beta_7 \cdot d(7)=4$	does not complain
Client Node 8	$D(P'_8)=3, \beta_8 \cdot d(8)=3$	does not complain

Now, lets compare the results with the corresponding $\rho$ values to see if a fine occurs:

FCC: $\frac{1}{2} \ge 0.5$, i.e., a fine is levied.

Lawsuit: $\frac{1}{5} < 0.4$, i.e., no lawsuit happens.

So, $pen_1 = \$70$. And thus the total revenue $= \$190 - \$70 - \$35 = \$95$. This is clearly a worse solution for this problem.

Example 3 solution

The picture below shows Example 3's solution being used to solve this problem:

$pen_0$ and $pen_1$ both turn out to be $\$0$ as in Example 3 so total revenue $ = \$190 - \$0 -\$0 - (2 \cdot \$15) = \$160$. Again this is worse than our solution for Example 4.

The Problem

Like Spectrum, ForProfitOnly gets hit with multiple lawsuits and you decide it is a good time to work for another company where profit is not the only motive. Luckily for you, a new startup EthicalInternet promises to keep customers first and then worry about profit. More precisely, EthicalInternet will guarantee that no customer would complain/drop-out. You apply for a position at EthicalInternet and you get the job: congratulations! You have a similar problem to solve as you did when you were at ForProfitOnly but now your objectives are different.

For this problem, there is no notion of a complaining client (but see the definition of penalty for how we will ensure that no customer would dropout). You are still allowed to set/change the priority for every client, and increase the bandwidth for any router at a cost of $\$Z$ per increase in bandwidth like before.

Input

$G = (V, E)$
$i \in V$
$C$ s.t. $C \subseteq V \setminus \{i\}$
For all $u \in V \setminus \{i\}$, $b_u$ s.t. $b_u < \infty$
For all $c \in C$, $\alpha_c$ s.t. $\alpha_c \ge 1$
For all $c \in C$, $\text{pmt}_c$
For all $c \in C$, $\text{priority(c)} =$ PRIORITY_DEFAULT
$\$Z$, which is the cost of unit increase in bandwidth

Penalty

The notion of penalty for this problem is different from all the previous problems. If there exists even one client $c \in C$ s.t. $D(P'_c) > \alpha_c \cdot d(c)$, then EthicalInternet will not charge any of its clients -- i.e. its revenue would be $0$.

Keeping customers first

The condition of making sure for every $c$ we have $D(P'_c)\le \alpha_c\cdot d(c)$ is probably a strong guarantee-- we picked it because of its simplicity. One could envision another version of this problem, where one could charge customers proportional to $\frac{d(c)}{D(P'_c)}$. This way you do get some revenue if some customer gets a slow service but in that case customers with slower speeds would pay less compared with those who get faster speeds. However, in the latter case there might still be an incentive to say give no service to some clients at all, if it sped up other customer's service.

Here is a questions for y'all to ponder on: if you owned EthicalInternet, what metric would you use to ensure a "minimum happiness" for your customers?

Unlike the previous problem, we will directly define the revenue without explicitly defining a penalty function since it makes the description much simpler.

Revenue

Total revenue is defined as the sum of payments received from each client $c \in C$ (minus $X\cdot Z$, where $X$ is as defined in Problem 3) if there is no client $c \in C$ such that $D(P'_c)> \alpha\cdot d(c)$. But if there is a client $c \in C$ with this property, then the total revenue would be $-X\cdot Z$. To put it mathematically:

Total Revenue $= \begin{cases} \sum_{c \in C} \text{pmt}_c -X\cdot Z &\text{if there is no} \quad c \in C \quad \text{s.t.} \quad D(P'_c) > \alpha_c \cdot d(c) \\ -X\cdot Z &\text{ otherwise} \end{cases}$

Output

Same as Problem 4.

Objective

Same as Problem 1.

Example 5

Note

We use the same graph as the previous examples, though we no longer care about $\beta$ values or if a client is rural or not. Please also note that $\alpha_3$ has been reduced from $4$ to $1.75$. We realize this is not an integer (as the $\alpha$ values are supposed to be but we make this change for illustration purposes only-- as otherwise we'll need to change more things. In your submission can and should assume that all $\alpha_c$ values are positive integers.

Now assume the input graph $G$ to be our example graph. Then here (see figure below) is a valid output for this problem with the given constraints:

NOTE:We use the same $Z=\$15$ value as stated in the example solution for Problem 3.

That is, the output $L_{P'} = [P'_1,P'_3,P'_6,P'_7,P'_8]$. Where, $P'_1 = [0,10,1], P'_3 = [0,9,3], P'_6 = [0,9,3,6], P'_7 = [0,10,1,4,7], P'_8 = [0,9,3,8]$.

Updated Bandwidths: $(8,7,4,2,2,4,1,1,5,2,7)$. That is, the bandwidth of nodes $3$ and $9$ is increased by one unit.

Priorities: $\text{priority(1)} = 1, \text{priority(3)} = 0, \text{priority(6)} = 2, \text{priority(7)} = 3, \text{priority(8)} = 4 $. (Recall that larger values implies higher priority.)

Total Revenue

For the solution above, we get a total revenue of $\$160$ while the solutions from Examples 1, 2, 3 and 4 get revenues of $\$0$, $\$0$, $-\$30$ and $\$0$ respectively. Please click on the button below to see details of the calculations.

Click here to see the revenue calculation for the above solution (as well as those of Example 1, 2, 3 and 4 solutions)

Determining $D(P')$ for every client

Since we now take into account priority, $D(P’_c)$ will be calculated a little differently. At every tick of the simulator we will attempt to pass on as many packets as possible starting with those of highest priority and moving to those with lowest priority. If we don’t have enough bandwidth, the lower priority packet is delayed another tick adding one to its total delay. Now, let's track each time tick of the routing of the packets:

`At Time Tick $0$:`

Current: All packets at 0.

Passed on: All

`At Time Tick $1$:`

Current:

$\text{pkt}_1$ at node $10$
$\text{pkt}_3$ at node $9$
$\text{pkt}_6$ at node $9$
$\text{pkt}_7$ at node $10$
$\text{pkt}_8$ at node $9$

Passed on: $\text{pkt}_1, \text{pkt}_6, \text{pkt}_7, \text{pkt}_8$

Delayed: $\text{pkt}_3$ (as $3$ has lower priority than $6$ and $8$)

`At Time Tick $2$:`

Current:

$\text{pkt}_1$ at node $1$
$\text{pkt}_3$ at node $9$
$\text{pkt}_6$ at node $3$
$\text{pkt}_7$ at node $1$
$\text{pkt}_8$ at node $3$

Reached: $\text{pkt}_1$

Passed on: $\text{pkt}_3, \text{pkt}_6, \text{pkt}_7, \text{pkt}_8$

`At Time Tick $3$:`

Current:

$\text{pkt}_3$ at node $3$
$\text{pkt}_6$ at node $6$
$\text{pkt}_7$ at node $4$
$\text{pkt}_8$ at node $8$

Reached: $\text{pkt}_3, \text{pkt}_6, \text{pkt}_8$

Passed on: $\text{pkt}_7$

`At Time Tick $4$:`

Current:

$\text{pkt}_7$ at node $7$

Reached: All packets reached.

The delay of the path is now equivalent to the tick that it reached its destination, i.e. $D(P'_1)=2, D(P'_3)=3, D(P'_6)=3, D(P'_7)=4, D(P'_8)=3$.

Revenue Calculation

If $D(P’_c) \leq \alpha_c \cdot d(c)$ then accept, else reject. Reject means the customer complains, so if we experience any rejections we earn no revenue from clients. Now let us see if there is an client $c \in \{1,3,6,7,8\}$ such that $c$ would be rejected:

$D(P’_1) = 2$

$d(1) \cdot \alpha_1 = 2 \cdot 1$
$2 \leq 2$, accept

$D(P’_3) = 3$

$d(3) \cdot \alpha_3 = 2 \cdot 1.75$
$3 \lt 3.5$, accept

$D(P’_6) = 3$

$d(6) \cdot \alpha_6 = 3 \cdot 1$
$3 \leq 3$, accept

$D(P’_7) = 4$

$d(7) \cdot \alpha_7 = 4 \cdot 1$
$4 \leq 4$, accept

$D(P’_8) = 3$

$d(8) \cdot \alpha_8 = 3 \cdot 1$
$3 \leq 3$, accept

Thus, total revenue $ = \left[ \sum_{c \in \{1,3,6,7,8\}} \text{pmt}_c \right] - \text{bandwidth increase} = \$190 - (2 \cdot \$15) = \$160$

Alternate Solution with different priorities

Now, let’s say we shift the priorities such that (among others) client $3$ now has the highest priority:

Changed Priorities: $\text{priority(1)} = 0, \text{priority(3)} = 4, \text{priority(6)} = 2, \text{priority(7)} = 1, \text{priority(8)} = 3 $.

Redetermining $D(P')$ for every client after changing priorities

Let us re-run the routing of the packets with the new priorities to compute the new delays:

`At Time Tick $0$:`

Current: All packets at 0.

Passed on: All

`At Time Tick $1$:`

Current:

$\text{pkt}_1$ at node $10$
$\text{pkt}_3$ at node $9$
$\text{pkt}_6$ at node $9$
$\text{pkt}_7$ at node $10$
$\text{pkt}_8$ at node $9$

Passed on: $\text{pkt}_1, \text{pkt}_3, \text{pkt}_7, \text{pkt}_8$

Delayed: $\text{pkt}_6$ since now $6$ has lower priority than $3$ and $8$

`At Time Tick $2$:`

Current:

$\text{pkt}_1$ at node $1$
$\text{pkt}_3$ at node $3$
$\text{pkt}_6$ at node $9$
$\text{pkt}_7$ at node $1$
$\text{pkt}_8$ at node $3$

Reached: $\text{pkt}_1, \text{pkt}_3$

Passed on: $\text{pkt}_6, \text{pkt}_7, \text{pkt}_8$

`At Time Tick $3$:`

Current:

$\text{pkt}_6$ at node $3$
$\text{pkt}_7$ at node $4$
$\text{pkt}_8$ at node $8$

Reached: $\text{pkt}_8$

Passed on: $\text{pkt}_6, \text{pkt}_7$

`At Time Tick $4$:`

Current:

$\text{pkt}_6$ at node $6$
$\text{pkt}_7$ at node $7$

Reached: $\text{pkt}_6, \text{pkt}_7$

Thus, the delays for the chosen paths are $D(P'_1)=2, D(P'_3)=2, D(P'_6)=4, D(P'_7)=4, D(P'_8)=3$.

Recalculating total revenue

Now, again let's check if there is a client $c \in \{1,3,6,7,8\}$ such that $D(P'_c) \gt \alpha_c \cdot d(c)$:

$D(P’_1) = 2$

$d(1) \cdot \alpha_1 = 2 \cdot 1$
$2 \leq 2$, accept

$D(P’_3) = 2$

$d(3) \cdot \alpha_3 = 2 \cdot 1.75$
$2 \leq 3.5$, accept

$D(P’_6) = 4$

$d(6) \cdot \alpha_6 = 3 \cdot 1$
$4 > 3$, reject

$D(P’_7) = 4$

$d(7) \cdot \alpha_7 = 4 \cdot 1$
$4 \leq 4$, accept

$D(P’_8) = 3$

$d(8) \cdot \alpha_8 = 3 \cdot 1$
$3 \leq 3$, accept

Since at least one customer complained we make no money, and on top of that we end up losing money since we must still pay for the bandwidth increase.

So, total revenue$= \$0 - (2 \cdot \$15) = -\$30$.

Comparing with previous solutions

Now we will compare our current solution, to those for previous examples. For the previous examples we will only alter the bandwidth or priority if our original solution altered either.

Example 1

Please refer to Example 2 for delay calculations (for the Example 1 solution above). Now, again let's check if there is a client $c \in \{1,3,6,7,8\}$ such that $D(P'_c) \gt \alpha_c \cdot d(c)$:

$D(P’_1) = 2$

$d(1) \cdot \alpha_1 = 2 \cdot 1$
$2 \leq 2$, accept

$D(P’_3) = 2$

$d(3) \cdot \alpha_3 = 2 \cdot 1.75$
$2 \leq 3.5$, accept

$D(P’_6) = 4$

$d(6) \cdot \alpha_6 = 3 \cdot 1$
$4 > 3$, reject

$D(P’_7) = 4$

$d(7) \cdot \alpha_7 = 4 \cdot 1$
$4 \leq 4$, accept

$D(P’_8) = 5$

$d(8) \cdot \alpha_8 = 3 \cdot 1$
$5 > 3$, reject

Since customers have complained we make no money. So, total revenue $ = \$0$ (recall we did not change the bandwidths so our overall revenue does not go below zero).

Example 2

For the delay calculations, please see Example 2. Now, again let's check if there is a client $c \in \{1,3,6,7,8\}$ such that $D(P'_c) \ge \alpha_c \cdot d(c)$:

$D(P’_1) = 2$

$d(1) \cdot \alpha_1 = 2 \cdot 1$
$2 \leq 2$, accept

$D(P’_3) = 4$

$d(3) \cdot \alpha_3 = 2 \cdot 1.75$
$4 > 3.5$, reject

$D(P’_6) = 4$

$d(6) \cdot \alpha_6 = 3 \cdot 1$
$4 > 3$, reject

$D(P’_7) = 4$

$d(7) \cdot \alpha_7 = 4 \cdot 1$
$4 \leq 4$, accept

$D(P’_8) = 3$

$d(8) \cdot \alpha_8 = 3 \cdot 1$
$3 \leq 3$, accept

Since at least one customer has complained we make no money. So,total revenue $ = \$0$ (recall we did not change the bandwidths so our overall revenue does not go below zero).

Example 3

Please see Example 3 for delay calculations. Since in Example 3 we increased the bandwidth at nodes $3$ and $9$, we propagate that change to here.

For delay calculation, please see Example 3. Now, again let's check if there is a client $c \in \{1,3,6,7,8\}$ such that $D(P'_c) \gt \alpha_c \cdot d(c)$:

$D(P’_1) = 2$

$d(1) \cdot \alpha_1 = 2 \cdot 1$
$2 \leq 2$, accept

$D(P’_3) = 4$

$d(3) \cdot \alpha_3 = 2 \cdot 1.75$
$4 > 3.5$, reject

$D(P’_6) = 3$

$d(6) \cdot \alpha_6 = 3 \cdot 1$
$3 \leq 3$, accept

$D(P’_7) = 4$

$d(7) \cdot \alpha_7 = 4 \cdot 1$
$4 \leq 4$, accept

$D(P’_8) = 3$

$d(8) \cdot \alpha_8 = 4 \cdot 1$
$3 \leq 4$, accept

Since at least one customer has complained we make no money and lose money for increasing bandwidth. So,total revenue $ = \$0 - (2 \cdot \$15) = -\$30$.

Example 4

For delay calculation, please see Example 4. Now, again let's check if there is a client $c \in \{1,3,6,7,8\}$ such that $D(P'_c) \gt \alpha_c \cdot d(c)$:

$D(P’_1) = 2$

$d(1) \cdot \alpha_1 = 2 \cdot 1$
$2 \leq 2$, accept

$D(P’_3) = 4$

$d(3) \cdot \alpha_3 = 2 \cdot 1.75$
$4 > 3.5$, reject

$D(P’_6) = 3$

$d(6) \cdot \alpha_6 = 3 \cdot 1$
$3 \leq 3$, accept

$D(P’_7) = 4$

$d(7) \cdot \alpha_7 = 4 \cdot 1$
$4 \leq 4$, accept

$D(P’_8) = 4$

$d(8) \cdot \alpha_8 = 3 \cdot 1$
$4 > 3$, reject

Since at least one customer has complained we make no money. So,total revenue $ = \$0$ (recall we did not change the bandwidths so our overall revenue does not go below zero).

Submitting as a group on Autolab

As mentioned above, you will be working on this project as a group. This mean y'all will also submit your solution file as a group. Here is a quick primer on how to form a group on Autolab and to submit as a group (opens in a new page).

The Coding Details

Note

Both the input and output parsers in each of the three languages are already written for you.
Note that you have to work with the input data structures provided (which will come pre-loaded with the data from an input file).

Addition is the only change you should make

Irrespective of what language you use, you will have to submit just one file. That file will come pre-populated with some stuff in it. You should not change any of those things because if you do you might break what the grader expects and end up with a zero on the question. You should of course add stuff to it (including helper functions and data structures as you see fit).

Make sure to output valid $i-c$ paths

Make sure that for each client $c$, your code outputs a valid $i-c$ path (including the fact that the first node in the path is $i$ and the last node in the path is $c$). If these conditions are not satisfied, then the grader code will silently set the delay of that path during routing to be $\infty$ (i.e. this error will not be flagged in the Autolab feedback).

Directory Structure

                                ├── src
                                │   ├── ub
                                │       ├── cse
                                │           ├── algo
                                │               ├── util
                                |                   ├── Pair.java
                                │               ├── Driver.java
                                │               ├── Globals.java
                                │               ├── Graph.java
                                │               ├── Info.java
                                │               ├── MPUtility.java
                                │               ├── Objects.java
                                │               ├── Revenue.java
                                │               ├── Simulator.java
                                │               ├── Solution.java
                                │               ├── Traversals.java
                                │
                                ├── testcases/
                                │   ├── input1.txt
                                │   ├── input1.txt-info

You are given eleven coding files: Pair.java, Driver.java, Globals.java, Graph.java, Info.java, MPUtility.java,Objects.java, Revenue.java, Simulator.java, Solution.java, and Traversals.java.

Driver.java implicitly calls methods in MPUtility.java. MPUtility.java reads the input files, and encapsulates all the data read from the input file into an Info object (Info class is in Info.java). This Info object is passed on to Solution.java, and you may access all the data needed from this Info object. In Solution.java you should implement the outputPaths() method which returns a SolutionObject object, and of course you can add your own data structures in Solution.java.

Objects.java has all the necessary object's defined: Client and Packet (but you may not have to use this). And Graph.java is the Graph represented as an adjacency list (HashMap<Integer,ArrayList<Integer>>).

Please make sure that you take a good look at Info.java, as it has 11 member variables:

Graph graph: is the input graph which also includes the ISP
ArrayList<Client> clients: is the list of Client objects for all client nodes $c \in C$.
ArrayList<Integer> bandwidths: is a mapping between node id's and their corresponding bandwidths. That is, the value of an index, represents the bandwidth of a node whose id is same as the index. Essentially, this is a mapping between each node $u \in V$ and $b_{u}$.
HashMap<Integer, Integer> shortestDelays: is a mapping between client id's and the shortest possible delays to the ISP. (This is only used by the grader and can be safely ignored.)
SolutionObject solutionObject: the SolutionObject object that will contain your solution returned from outputPaths() (see below for more).
float rho1 same as $\rho_{\text{lawsuit}}$
float rho2 same as $\rho_{\text{fcc}}$
float lawsuit: same as $A$.
float fccFine: same as $B$.
float costBandwidth: same as $Z$.

Your code will return a SolutionObject (defined in Objects.java), which contains a HashMap<Integer, ArrayList<Integer>> of paths (make sure your paths start from the content provider); a HashMap<Integer, Integer>, holding your priorities for each client and an ArrayList<Integer> holding your bandwidths after they have been increased.

Finally, the Solution class has four instance variables:

info which is an instance of Info class, and encapsulates all the data read from the input files.
graph which is an instance of the Graph class the represents the network (note that information is also part of info and it copied over for your convenience)
clients which is a list of Client objects (note that information is also part of info and it copied over for your convenience)
bandwidths which is a mapping of ids to node bandwidths (note that information is also part of info and it copied over for your convenience)

Compiling and executing from command line:

Assuming you're in the same directory level as src/. Run javac src/ub/cse/algo/util/*.java src/ub/cse/algo/*.java to compile.

To execute your code on input1.txt, run java -cp "src" ub.cse.algo.Driver testcases/input1.txt. The output will be printed to stdout.

Note

You should not pass input1.txt-info as a command line argument.

Submission

You only need to submit Solution.java to Autolab.

You are not provided any output!

There is no output.txt file for any problem, as it would happen if you were working at ForProfitOnly.

Simulator.java could be helpful

Simulator.java contains the code for running the routing simulator as described above. You might find the following methods useful:

    /**
     * Simulate the solution to find the delays to each
     * Client and return them in a HashMap
     *
     * @param graph: Graph Object representing the network
     * @param clientList: List of Client Objects
     * @param sol: Solution to Simulate
     * @return a map of Client IDs to packet delays
     */
    static HashMap run(Graph graph, ArrayList clientList, SolutionObject sol)

Revenue.java could be helpful

Revenue.java contains the code for calculating the total revenue as described in the mathematical formulation. You might find the following methods useful:

    /**
     * Static method that will compute the revenue generated from
     * the given solution given the boolean variables
     *
     * @param info: data parsed from the input file
     * @param solutionObject: the "optimal" solution
     * @param delays: Map of the delays the packets took to reach the clients
     * @param pen_1: should the first penalty be applied?
     * @param pen_2: should the second penalty be applied?
     * @param updated_bandwidths: have the bandwidths been changed?
     * @return the calculated revenue
     */
    static float revenue(Info info, SolutionObject solutionObject, HashMap delays,
                  boolean pen_1, boolean pen_2, boolean updated_bandwidths)

Problem 1

Download Java Skeleton Code

Method you need to write:

/**
* This method must be implemented by you. You may add other methods and subclasses as you see fit,
* but they must remain within the Solution class.
* @return A SolutionObject object that encapsulates the paths and other data generated by you
*/
public SolutionObject outputPaths(){
    SolutionObject sol = new SolutionObject();
    /* TODO: Your solution goes here */
    return sol;
}

What to Change in the SolutionObject Object?

For this problem you are only required to generate paths for routing packets from the content provider to each client. This would be represented as a HashMap<Integer,List<Integer>>, that is the keys of the HashMap<Integer,List<Integer>> are the client node id's and the corresponding values are the paths (that start from the content provider).

Once you generate this HashMap<Integer,List<Integer>> of paths, you should set the paths member of the returned SolutionObject object equal to the HashMap<Integer,List<Integer>> generated by you.

You are provided the entire test suite

For the first problem, there is only one testcase on Autolab, which is provided to you.

There is an additional file for this problem

For this problem, take a look at Traversals.java. This includes code for running BFS that you might find useful.

Do not modify the output!

Please do not change the return statement for any method. For all problems, outputPaths() method outputs a SolutionObject.

This is an easy problem

Once you understand the problem and get familiar with the template, to get full points you only will need to add a couple of lines of code to Solution.java.

Problem 2

Download Java Skeleton Code

Method you need to write:

/**
* This method must be implemented by you. You may add other methods and subclasses as you see fit,
* but they must remain within the Solution class.
* @return A SolutionObject object that encapsulates the paths and other data generated by you
*/
public SolutionObject outputPaths(){
    SolutionObject sol = new SolutionObject();
    /* TODO: Your solution goes here */
    return sol;
}

What to Change in the SolutionObject Object?

You are provided a subset of the test suite!

For the second problem, there are two testcases on Autolab. The first one, input1.txt in conjunction with input1.txt-info is provided to you. The second testcase will use the same graph from input1.txt but with a different info file, input2.txt-info

Do not modify the output!

Please do not change the return statement for any method. For all problems, outputPaths() method outputs a SolutionObject object.

What's the difference in the zips?

The templates for the different problem are essentially the same except that Driver.java sets the appropriate problem value. So while you can modify the zip from another problem to work for Problem 2, to be on the safe side, we still encourage y'all to download the zip for this problem and work on it separately from your work on other problems.

Problem 3

Download Java Skeleton Code

Method you need to write:

/**
* This method must be implemented by you. You may add other methods and subclasses as you see fit,
* but they must remain within the Solution class.
* @return A SolutionObject object that encapsulates the paths and other data generated by you
*/
public SolutionObject outputPaths(){
    SolutionObject sol = new SolutionObject();
    /* TODO: Your solution goes here */
    return sol;
}

What to Change in the SolutionObject Object?

For this problem you are required to generate paths for routing packets from the content provider to each client. This would be represented as a HashMap<Integer,List<Integer>>, that is the keys of the HashMap<Integer,List<Integer>> are the client node id's and the corresponding values are the paths (that start from the content provider).

You should also update the bandwidths as well (if your code does decide to do this). To do so set the bandwidths member of the returned SolutionObject object to the updated bandwidths.

You are provided a subset of the test suite!

For the third problem, there are four testcases on Autolab. The first one, input1.txt in conjunction with input1.txt-info is provided to you. The other testcases will use the same graph from input1.txt but with different info files.

Do not modify the output!

Please do not change the return statement for any method. For all problems, outputPaths() method outputs a SolutionObject object.

What's the difference in the zips?

The templates for the different problem are essentially the same except that Driver.java sets the appropriate problem value. So while you can modify the zip from another problem to work for Problem 3, to be on the safe side, we still encourage y'all to download the zip for this problem and work on it separately from your work on other problems.

Problem 4

Download Java Skeleton Code

Method you need to write:

/**
* This method must be implemented by you. You may add other methods and subclasses as you see fit,
* but they must remain within the Solution class.
* @return A SolutionObject object that encapsulates the paths and other data generated by you
*/
public SolutionObject outputPaths(){
    SolutionObject sol = new SolutionObject();
    /* TODO: Your solution goes here */
    return sol;
}

What to Change in the SolutionObject Object?

You should also update the bandwidths/priorties as well (if your code does decide to do this). To do so set the bandwidths/priorities member of the returned SolutionObject object to the updated bandwidths/priorities.

You are provided a subset of the test suite!

For the fourth problem, there are five testcases on Autolab. The first one, input1.txt in conjunction with input1.txt-info is provided to you. The other testcases will use the same graph from input1.txt but with different info files.

Do not modify the output!

Please do not change the return statement for any method. For all problems, outputPaths() method outputs a SolutionObjet object.

What's the difference in the zips?

The templates for the different problem are essentially the same except that Driver.java sets the appropriate problem value. So while you can modify the zip from another problem to work for Problem 4, to be on the safe side, we still encourage y'all to download the zip for this problem and work on it separately from your work on other problems.

Problem 5

Download Java Skeleton Code

Method you need to write:

/**
* This method must be implemented by you. You may add other methods and subclasses as you see fit,
* but they must remain within the Solution class.
* @return A SolutionObject object that encapsulates the paths and other data generated by you
*/
public SolutionObject outputPaths(){
    SolutionObject sol = new SolutionObject();
    /* TODO: Your solution goes here */
    return sol;
}

What to Change in the SolutionObject Object?

You are provided a subset of the test suite!

For the fifth problem, there are eight testcases on Autolab. The first one, input1.txt in conjunction with input1.txt-info is provided to you. The other testcases will use the same graph from input1.txt but with different info files.

Do not modify the output!

Please do not change the return statement for any method. For all problems, outputPaths() method outputs a SolutionObject object.

What's the difference in the zips?

The templates for the different problem are essentially the same except that Driver.java sets the appropriate problem value. So while you can modify the zip from another problem to work for Problem 5, to be on the safe side, we still encourage y'all to download the zip for this problem and work on it separately from your work on other problems.

Directory Structure

                                    ├── Driver.py
                                    ├── Enums.py
                                    ├── Graph.py
                                    ├── LinkedList.py
                                    ├── Objects.py
                                    ├── Revenue.py
                                    ├── Simulator.py
                                    ├── Solution.py
                                    ├── Traversals.py
                                    ├── Utility.py
                                    ├── testcases/
                                    │   ├── input1.txt
                                        ├── input1.txt-info

You are given ten coding files. Out of these, you can safely ignore Enums.py and LinkedList.py. These files are merely required to do some processing in the background. For example, Enums.py is used in conjunction with the file I/O code. LinkedList.py is an implementation of a linked list in Python since there is no standard one.

Driver.py takes the input file, parses it using Utility.py and calls your Solution.py class' output_paths() method on data structures it creates. The $i-c$ paths output by you (along with, depending on the question, the updated bandwidths and packet priorities) are passed in to the routing simulator inside Simulator.py, which processes them and determines the routing delay faced by each client. Finally, these delays are passed into the revenue calculation function inside Revenue.py. It then prints the revenue you gathered based on your routing decisions. You only need to update the Solution.py file. You may write your own helper methods and data structures in it.

The Solution class contains four data structures.

problem, which simply contains the problem number of the current template as a member variable on the Solution class. You DO NOT need to worry about this variable.
isp which is the ID of the ISP node. Note that this is the same as content provider or $i$ as mentioned in the problem description.
graph which is the input graph $G$ in the adjacency list representation that you are familiar with. The key is a node ID (not client, there are nodes that may not be clients) and the value is the list of nodes it is connected to.
info which is a mapping between a string representing the various input parameters and the corresponding data structure. For example, info["bandwidths"] lets you access the mapping between node IDs and their bandwidths. More details on info below.

As outlined in the problem descriptions, there are various additional input parameters provided to you besides the graph, which you can use to influence the routing. These are available through the info data structure available as a member variable of the Solution class. The parameters are listed as follows:

list_clients [list of client IDs] is a list of all clients in $C$
bandwidths [dict: node IDs (int) -> bandwidth (int)] maps $u\in V$ to $b_u$
alphas [dict: client IDs (int) -> alphas (float)] maps $c\in C$ to $\alpha_c$
payments [dict: client IDs (int) -> payments (float)] maps $c\in C$ to $\text{pmt}_c$
betas [dict: client IDs (int) -> betas (float)] maps $c\in C$ to $\beta_c$
is_rural [dict: client IDs (int) -> is_rural ({0, 1})] if is_rural[$c$]= 0, then $c\not\in R$ and if =1, then $c\in R$
is_fcc [dict: client IDs (int) -> is_fcc ({0, 1})] if is_fcc[$c$] =0, then $c\in S$ and if =1, then $c\in S$.
rho1 [float] same as $\rho_{\text{lawsuit}}$
rho2 [float] same as $\rho_{\text{fcc}}$
lawsuit [float] same as $A$
fcc_fine [float] same as $B$
cost_bandwidth [float] same as $Z$

To access each parameter, use the name exactly as given above as a key for the info data structure. For eg. info["bandwidths"] is a map from node IDs to their bandwidths, info["lawsuit"] is a floating point representing the amount of the lawsuit fine and so on. Note that not all parameters are available for each problem, for eg. Problem 1 and Problem 2 only have the first four available for use.

Your method is expected to return a dictionary indexed by client IDs with their $i$-$c$ path as the value. For problems 3, 4, 5 you also need to return a dictionary indexed by node IDs with their updated bandwidth as the value. For problems 4 and 5 you further need to return a dictionary indexed by client IDs with their priorities as the value. As a reminder if you return an object you are not supposed to, for eg. priorities in problem 2, it will be ignored by the grader.

Executing from command line:

Assuming you're in the same directory level as Driver.py and you want to run your code on the input1.txt. Run python Driver.py testcases/input1.txt.

Note

Note that you do not need to pass in input1.txt-info as a parameter.

Submission

You only need to submit Solution.py to Autolab.

You are not provided any output!

There is no output.txt file for any problem, as it would happen if you were working at ForProfitOnly.

`Simulator.py` could be useful

Simulator.py contains the code for running the routing simulator as described above. You might find the following method useful:

    def run(self, graph, isp, list_clients, paths, bandwidths, priorities, is_rural):
        """
        Runs the simulation based on the paths provided by the student
        """

    def get_delays(self, list_clients):
        """
        Returns the delay experienced by each client after the simulation has
        run its course
        """

`Revenue.py` could be useful

Revenue.py contains the code for retrieving the revenue obtained as described above. You might find the following methods useful:

    def revenue(self, client_list, alphas, betas, optimal_dict, payments, lawsuit, rho_lawsuit, fcc_fine, rho_fcc, is_fcc,
                pen_1, pen_2, updated_bandwidths, original_bandwidths, update_cost):
        """
        determines overall revenue
         
        :param client_list: list of client objects
        :param alphas: mapping of clients to their alpha values
        :param betas: mapping of clients to their beta values
        :param optimal_dict: mapping of clients to their optimal delays
        :param payments: mapping of clients to their payment values
        :param lawsuit: lawsuit cost
        :param rho_lawsuit: lawsuit factor
        :param rho_fcc: fcc factor
        :param is_fcc: mapping of nodes to either 0 or 1
        :param fcc_fine: fcc penalty
        :param pen_1: if the lawsuit should be taken into account
        :param pen_2: if the fcc should be taken into account
        :param updated_bandwidths mapping of nodes to new bandwidths as set by the solution
        :param original_bandwidths mapping of nodes to original bandwidths as provided by the problem
        :param cost to upgrade the bandwidth by 1

        :return: the total revenue
        """

Problem 1

Download Python Skeleton Code

Method you need to write:

                                    def output_paths(self):
                                        """
                                        This method must be filled in by you. You may add other methods and subclasses as you see fit,
                                        but they must remain within the Solution class.
                                        """
                                        paths, bandwidths, priorities = {}, {}, {}

                                        return (paths, bandwidths, priorities)

You are provided the entire test suite

For the first problem, there is only one testcase on Autolab, which is provided to you.

There is an additional file for this problem

For this problem, take a look at Traversals.py. This includes code for running BFS that you might find useful.

Do not modify the output!

Please do not change the return statement. All the problems return the same tuple, but bandwidths and priorities should be set to the empty dictionary for this problem. You need to assign a value to the paths variable as your solution.

This is an easy problem

Once you understand the problem and get familiar with the template, to get full points you only will need to add up to a couple of lines of code to Solution.py.

Problem 2

Download Python Skeleton Code

Method you need to write:

                                    def output_paths(self):
                                        """
                                        This method must be filled in by you. You may add other methods and subclasses as you see fit,
                                        but they must remain within the Solution class.
                                        """
                                        paths, bandwidths, priorities = {}, {}, {}

                                        return (paths, bandwidths, priorities)

You are provided a subset of the test suite!

Do not modify the output!

What's the difference in the zips?

The templates for the different problem are essentially the same except that Driver.py sets the appropriate problem value. So while you can modify the zip from another problem to work for Problem 2, to be on the safe side, we still encourage y'all to download the zip for this problem and work on it separately from your work on other problems.

Problem 3

Download Python Skeleton Code

Method you need to write:

                                    def output_paths(self):

                                        """
                                        This method must be filled in by you. You may add other methods and subclasses as you see fit,
                                        but they must remain within the Solution class.
                                        """
                                        paths, bandwidths, priorities = {}, {}, {}

                                        return (paths, bandwidths, priorities)

You are provided a subset of the test suite!

Do not modify the output!

Please do not change the return statement. All the problems return the same tuple, but priorities should be set to the empty dictionary for this problem. You need to assign a value to the paths and bandwidths variables as your solution.

What's the difference in the zips?

The templates for the different problem are essentially the same except that Driver.py sets th e appropriate problem value. So while you can modify the zip from another problem to work for Problem 3, to be on the safe side, we still encourage y'all to download the zip for this problem and work on it separately from your work on other problems.

Problem 4

Download Python Skeleton Code

Method you need to write:

                                    def output_paths(self):
                                        """
                                        This method must be filled in by you. You may add other methods and subclasses as you see fit,
                                        but they must remain within the Solution class.
                                        """

                                        paths, bandwidths, priorities = {}, {}, {}

                                        return (paths, bandwidths, priorities)

You are provided a subset of the test suite!

Do not modify the output!

Please do not change the return statement. All the problems return the same tuple, but in this problem, you need to assign a value to the paths, bandwidths and priorities variables as your solution.

What's the difference in the zips?

The templates for the different problem are essentially the same except that Driver.py sets th e appropriate problem value. So while you can modify the zip from another problem to work for Problem 4, to be on the safe side, we still encourage y'all to download the zip for this problem and work on it separately from your work on other problems.

Problem 5

Download Python Skeleton Code

Method you need to write:

    def output_paths(self):
        """
        This method must be filled in by you. You may add other methods and subclasses as you see fit,
        but they must remain within the Solution class.
        """
        paths, bandwidths, priorities = {}, {}, {}
        return (paths, bandwidths, priorities)

You are provided a subset of the test suite!

Do not modify the output!

What's the difference in the zips?

The templates for the different problem are essentially the same except that Driver.py sets th e appropriate problem value. So while you can modify the zip from another problem to work for Problem 5, to be on the safe side, we still encourage y'all to download the zip for this problem and work on it separately from your work on other problems.

Directory Structure

                                    ├── Driver.cpp
                                    ├── Solution.cpp
                                    ├── Graph.h
                                    ├── Objects.h
                                    ├── Revenue.cpp
                                    ├── Revenue.h
                                    ├── Simulator.cpp
                                    ├── Simulator.h
                                    ├── Traversals.cpp
                                    ├── Traversals.h
                                    ├── MPUtility.h
                                    ├── Utility.h
                                    ├── testcases/
                                    │   ├── input1.txt
                                    │   ├── input1-info.txt

You are given twelve coding files.

Driver.cpp takes the input file, parses it, using MPUtility.h and creates an instance of the class Solution and calls the outputDistances() method on it to determine the $i-c$ paths (and possibly bandwidths/ priorities). Then it uses those paths (and priorities/bandwidths where applicable) to run the Simulator.cpp, which processes them and determines the routing delay faced by each client. Finally these delays are passed into the revenue calculations in Revenue.cpp. It then prints the revenue you gathered based on your routing decisions. You only need to update the Solution.cpp file. You may write your own helper methods and data structures in it.

The Solution class has six member variables:

problem, which represents the problem number you are working on. You DO NOT need to worry about this variable.
graph which is the input graph. It has a unordered_map that is the adjacency list representation of $G$, where the keys are the nodes and the values is a vector of its neighbors. There is also an int, contentProvider representing the content provider, or $i$.
clients which represents a vector of all clients, or $C$. This will be explained more below.
bandwidths which is a vector that maps $u\in V$ to $b_u$.
fines which is a map that holds the fcc and lawsuit $\rho$ values and fines. The key is either "fcc" or "lawsuit". The values are a pair where the first is the corresponding $\rho$ value and the second is the fine amount (or $A$ and $B$ respectively)
band_incr_cost holds how much it costs to increase a bandwidth by one, or $Z$.

Now for an explanation of the Client Object (which is in Objects.h):

idrepresents the client's id $c$
alpha is the client $c$'s $\alpha_c$ value
beta is the client $c$'s $\beta_c$ value
payment is the client $c$'s $pmt_c$ value.
is_rural is set to true if $c\in R$, otherwise $c\not\in R$
is_fcc is set to true if $c\in S$, otherwise $c\not\in S$
priority is the client's priority.

The output for this function must output a Solution_Object (defined in Objects.h), which contains an unordered_map of <int, vector<int>> , holding your paths (make sure all paths start with the content provider); a vector of <int>, holding your bandwidths after they have been increased; and an unordered_map of <int, int>, holding your priorities for each client. Make sure that the order is correct.

Compiling and executing from command line:

Assuming you're in the same directory level as Driver.cpp. Run g++ -std=c++11 Driver.cpp to compile.

To execute your code on input1.txt, run ./a.out testcases/input1.txt. Do not worry about passing input1.txt-info, Driver.cpp will generate this name for you.

Submission

You only need to submit Solution.cpp to Autolab.

You are not provided any output!

There is no output.txt file for any problem.

`Simulator.cpp` could be useful!

Simulator.cpp contains the code for running the simulator as described above. You might find the following method useful:

                                          unordered_map<int, int> Simulator(Graph &g, Solution_Object &sol, const vector<Client> &clients_vec){ 
                                             /*
                                              *Runs the simulator with the graph, list of clients, 
                                              *determined paths, bandwidths and priorities as the inputs. 
                                              *It outputs a map of the clients with their delays
                                              */
                                           }

`Revenue.cpp` could be useful!

Revenue.cpp contains the code for retrieving the revenue obtained as described above. You might find the following methods useful:

                                          int pen_0(Graph &input, vector<Client> &clients, unordered_map<int, int> &calc_delays, bool count_rural, bool five){
                                                /* 
                                                 *determines whether or not a client will pay their internet fee.
                                                 */
                                          }

                                          int pen_1(Graph &input, vector<Client> &clients, unordered_map<int, int> &delays, unordered_map<string, pair<float, int>> &fine_info){
                                                /*
                                                 * Determines whether or not the ISP takes on the FCC and/or Lawsuit fines
                                                 */
                                          }

                                        int bandwidth_increase(vector<int> &old_bandwidths, vector<int> &new_bandwidths, int increase_amount){
                                               /*
                                                * Determines the amount it costs to increase the bandwidths for problems 4 and 5
                                                */
                                        }

Problem 1

Download C++ Skeleton Code

Method you need to write:

   Solution_Object outputPaths() {

        Solution_Object solution = Solution_Object();     

        return solution;
    }

You are provided the entire test suite!

For the first problem, there is only one testcase on Autolab, which is provided to you.

There is an additional file for this problem.

For this problem, take a look at Traversals.cpp. This includes code for running BFS that you might find useful.

Be careful about your output!

Do not change the bandwidths or priorities in your output Solution_Object. But do change the paths appropriately.

This is an easy problem

Once you understand the problem and get familiar with the template, to get full points you only will need to add up to a couple of lines of code to Solution.cpp.

Problem 2

Download C++ Skeleton Code

Method you need to write:

    Solution_Object outputPaths() {


        Solution_Object solution;
        /*
         * TODO: Implement the solution
         */



        return solution;
    }

You are provided a subset of the test suite!

Be careful about your output!

Do not change the bandwidths or priorities in your output Solution_Object. But do change the paths appropriately.

What's the difference in the zips?

The templates for the different problem are essentially the same except that Driver.cpp sets the appropriate problem value. So while you can modify the zip from another problem to work for Problem 2, to be on the safe side, we still encourage y'all to download the zip for this problem and work on it separately from your work on other problems.

Problem 3

Download C++ Skeleton Code

Method you need to write:

    Solution_Object outputPaths() {

        Solution_Object solution;
        // change both solution.paths and solution.bandwidths for this problem
        /*
         * TODO: Implement the solution
         */



        return solution;
    }

You are provided a subset of the test suite!

For the second problem, there are four testcases on Autolab. The first one, input1.txt in conjunction with input1.txt-info is provided to you. The other testcases will use the same graph from input1.txt but with different info files.

Be careful about your output!

Do not change the priorities in your output Solution_Object. But do change the paths and/or bandwidths appropriately.

What's the difference in the zips?

The templates for the different problem are essentially the same except that Driver.cpp sets the appropriate problem value. So while you can modify the zip from another problem to work for Problem 3, to be on the safe side, we still encourage y'all to download the zip for this problem and work on it separately from your work on other problems.

Problem 4

Download C++ Skeleton Code

Method you need to write:

    Solution_Object outputPaths() {

        Solution_Object solution;
        // change solution.paths, solution.bandwidths and solution.priorities for this problem
        /*
         * TODO: Implement the solution
         */



        return solution;
    }

You are provided a subset of the test suite!

Be careful about your output!

Do change the paths and/or bandwidths and/or priorities of solution appropriately.

What's the difference in the zips?

The templates for the different problem are essentially the same except that Driver.cpp sets the appropriate problem value. So while you can modify the zip from another problem to work for Problem 4, to be on the safe side, we still encourage y'all to download the zip for this problem and work on it separately from your work on other problems.

Problem 5

Download C++ Skeleton Code

Method you need to write:

    Solution_Object outputPaths() {

        Solution_Object solution;
        // you might have to change all three of
        // solution.paths, solution.bandwidhts and solution.priorities for this problem
        /*
         * TODO: Implement the solution
         */

        return solution;
    }

You are provided a subset of the test suite!

Be careful about your output!

Do change the paths and/or bandwidths and/or priorities of solution appropriately.

What's the difference in the zips?

The templates for the different problem are essentially the same except that Driver.cpp sets the appropriate problem value. So while you can modify the zip from another problem to work for Problem 5, to be on the safe side, we still encourage y'all to download the zip for this problem and work on it separately from your work on other problems.

Grading Guidelines

The grading works a little differently for this project.

Each testcase is worth 5 points. The number of testcases for each problem depends on the maximum points ($max\_points$) achievable, and is equal to $\frac{max\_points}{5}$. For eg. Problem 1 has one testcase, since it is worth 5 points, Problem 2 has two testcases, since it is worth 10 points and so on.

For Problem 1, you get the full 5 points if your revenue matches ours and 0 otherwise.

Except for Problem 1, there is partial grading for each testcase. The number of points awarded to you depend on how well your solution's revenue compares with our revenue.

For other problems, the thresholds are outlined below, the numbers on the left indicate the ratio of (your solution's revenue - revenue of optimal Solution for Problem 1) and (our revenue - revenue from optimal Solution for Problem 1) in percentage, and the right half indicates the points achieving that ratio will award you.

$[100, 80]$ -> 5 points
$[80, 60)$ -> 4 points
$[60, 40)$ -> 3 points
$[40, 20)$ -> 2 points
$[20, 5)$ -> 1 points
$[0, 5]$ -> 0 points

Coding Mini Project

Acknowledgment

Some Suggestions and Warnings

Form groups of size $\le 3$

Groups should agree on one programming language

The same group for ALL problems

There are no optimal algorithms known!

Start early!

Optimizing the runtime of your code is NOT the main objective

Background

The Basic Problem

The Problem

Simplifications galore!

Notation Table

The Graph

Clients vs. Routers

$d_e=1$ for all edges $e$

Packets are different

One packet per client

Routing is centralized

No bound on incoming traffic

Routing of packets

Larger value is higher priority

All packets are sent out of $i$ at the same time

Algorithm Idea

Algorithm Details

Payments and Revenue

Clients payments can vary

Example 0

$d(c)$ in the above graph $G$

Show All Problems

Problem 1 [5 points]

The Problem

Input

Penalty

Revenue

Output

Objective

Hint

Example 1

A Solution

Justification for claim on revenue

Problem 2 [10 points]

The Problem

Capturing bandwidth by a single number

Perfect knowledge of $\alpha_c$

Input

Note

Penalty

Revenue

Output

Objective

Example 2

A Solution

Note

Total Revenue

Determining $D(P')$ for every client

At Time Tick $0$:

At Time Tick $1$:

At Time Tick $2$:

At Time Tick $3$:

At Time Tick $4$:

Determining Penalty and Calculating total revenue

Example 1 solution

Solution to Example 1

Determining $D(P')$ for every client

At Time Tick $0$:

At Time Tick $1$:

At Time Tick $2$:

At Time Tick $3$:

At Time Tick $4$:

At Time Tick $5$:

Determining Penalty and Calculating total revenue

Problem 3 [20 points]

The Problem

Simplification/Motivation for $Z$

Why the $\max$ term?

Can a client Complain and Unsubscribe at the same time?🤔

When does OAG start an investigation?

Did you know? 🤔

`At Time Tick $0$:`

`At Time Tick $1$:`

`At Time Tick $2$:`

`At Time Tick $3$:`

`At Time Tick $4$:`

`At Time Tick $0$:`

`At Time Tick $1$:`

`At Time Tick $2$:`

`At Time Tick $3$:`

`At Time Tick $4$:`

`At Time Tick $5$:`

`At Time Tick $0$:`

`At Time Tick $1$:`

`At Time Tick $2$:`

`At Time Tick $3$:`

`At Time Tick $4$:`

`At Time Tick $0$:`

`At Time Tick $1$:`

`At Time Tick $2$:`

`At Time Tick $3$:`

`At Time Tick $4$:`

`At Time Tick $0$:`

`At Time Tick $1$:`

`At Time Tick $2$:`

`At Time Tick $3$:`