# Coding Mini Project

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

# 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

#### 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

#### 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 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

#### 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).

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 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

#### 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).

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 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

#### 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).

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 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 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
├── 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:

1. list_clients [list of client IDs] is a list of all clients in $C$
2. bandwidths [dict: node IDs (int) -> bandwidth (int)] maps $u\in V$ to $b_u$
3. alphas [dict: client IDs (int) -> alphas (float)] maps $c\in C$ to $\alpha_c$
4. payments [dict: client IDs (int) -> payments (float)] maps $c\in C$ to $\text{pmt}_c$
5. betas [dict: client IDs (int) -> betas (float)] maps $c\in C$ to $\beta_c$
6. 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$
7. 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$.
8. rho1 [float] same as $\rho_{\text{lawsuit}}$
9. rho2 [float] same as $\rho_{\text{fcc}}$
10. lawsuit [float] same as $A$
11. fcc_fine [float] same as $B$
12. 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

#### 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

#### 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!

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. 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.

#### 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

#### 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!

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. 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

#### 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!

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. 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

#### 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!

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. 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 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

#### 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.

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

#### 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!

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 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

#### 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.

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

#### 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!

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 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

#### 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!

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 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.

#### 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